Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: P vs NP problem
Posted:
Jun 6, 2012 5:31 AM


On Jun 6, 5:24 pm, Martin Brown <newspam...@nezumi.demon.co.uk> wrote: > On 02/06/2012 15:08, Jesse F. Hughes wrote: > > > " E R C"<herc.of.z...@gmail.com> writes: > > >> i.e. my Javascript Chess Engine Vs Deep Blue. > > >> I can look 30 moves ahead  2^30< 16^20 > >> more than 20 moves ahead that Deep Blue can do. > > > Keen! Let's see that competition! > > Deep blue is a bit long in the tooth now (and was anyway dismantled > after the famous match against Kasparov). I expect Stockfish or any > other top *free* engine could beat a Javascript engine hollow. > > (and possibly also do it at queen odds with more difficulty) > >  > Regards, > Martin Brown
Last I heard the Grandmasters were challenging Fritz.
But it doesn't matter how much you tweak AlphaBeta, the search width is only half as wide as MiniMax!
About 15 moves to check every ply!
That's 15 X 15 X 15 X 15 X 15 X 15 X 15 ... X 15
You only have 30GB of memory so you run out after 1 billion board positions, so you only get about 15 ply deep!
When Kasparov beat Deep Blue he wasn't using 30GB of photographic memory and 100 nanosecond board updates!
Kasparov was searching
2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2 X 2
16 PLY DEEP! Still an amazing memory for a perosn, but not a billion board positions!
He was COMPARING 2 Plans at a time!
SPACE O(2^n) for MINIMINIMAX
<PLAN1 PLAN2> BBBBBBBB BBBBBBBB WWWW WWWW BB BB W W THE "WINDSCREEN WIPER" ALGORITHM
I use 100,000 board positions at www.CHESS.com (plain old minimax)  about as many as Kasparov must have been using.
Herc



