Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: P vs NP problem
Replies: 6   Last Post: Jun 6, 2012 5:31 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Graham Cooper

Posts: 4,237
Registered: 5/20/10
Re: P vs NP problem
Posted: Jun 6, 2012 5:31 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.C-H-E-S-S.com (plain old minimax)
- about as many as Kasparov must have been using.

Herc



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.