Solving Chess Kickstarter

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
ambrooks1
Posts: 2
Joined: Wed Feb 26, 2014 3:31 pm
Location: United States

Re: Solving Chess Kickstarter

Let's say that you cannot come up with a simple elegant mathematical argument to avoid doing computation.

Generating the full game tree is computationally impossible with current hardware, as every game programmer knows.

So you are going to need some kind of mathematical argument to justify pruning the tree to some manageable breadth.

Aren't you going to still have to come up with some kind of theory to be able to do this?

To me, this is not a programming project at all. This is a MATH project.

syzygy
Posts: 4451
Joined: Tue Feb 28, 2012 10:56 pm

Re: Solving Chess Kickstarter

ambrooks1 wrote:Let's say that you cannot come up with a simple elegant mathematical argument to avoid doing computation.

Generating the full game tree is computationally impossible with current hardware, as every game programmer knows.

So you are going to need some kind of mathematical argument to justify pruning the tree to some manageable breadth.
Well, you can at least hope that the proof tree is of manageable size. That the state space of chess is huge is not necessarily a problem as the example of suicide chess shows.

The proof tree indeed won't be of manageable size, but this is not something that every (general) programmer can know. You have to have had some experience with tree searching algorithms specifically applied to chess.
Aren't you going to still have to come up with some kind of theory to be able to do this?

To me, this is not a programming project at all. This is a MATH project.
It is programming. The algorithms mostly exist. Some new heuristics and clever ideas might help. I wouldn't call this mathematics as after all it is a problem of finite size, hence mathematically completely trivial. (The four colour theorem is of infinite size, at least before it was mathematically reduced to a finite computational problem: in principle there are infintely many maps to consider.) I can easily write a relatively small program that takes the start position as input and produces the game theoretic result as output, guaranteed in finite time, and that will run on an old Commodore 64. You need to be very patient, though.

Checkers has been solved. The state space of checkers is smaller than that of chess, but still huge. The solution involved programming and a lot of computation. No mathematics.

Many other games have been solved as well through computation with the help of smart algorithms.

Again, I do not believe that regular chess can be solved using the hardware of today and also not using the hardware of the coming centuries unless some very significant technological breakthrough is made. The OP is just naive.

jdart
Posts: 3816
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Solving Chess Kickstarter

You might as well say, "At this point, a miracle occurs."

--Jon

lucasart
Posts: 3037
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Solving Chess Kickstarter

Just ignore this thread. He's a fool.

A guy who's never written a chess engine in his life, announcing that he's about to build a 32-men bitbase.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Henk
Posts: 5799
Joined: Mon May 27, 2013 8:31 am

Re: Solving Chess Kickstarter

Maybe we can extrapolate. How many records does a 1,2,3,4,5 or 6 men endgames chess database table have ?

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Solving Chess Kickstarter

Henk wrote:Maybe we can extrapolate. How many records does a 1,2,3,4,5 or 6 men endgames chess database table have ?
If I remember correctly for 1 man it is 64x6. For two men it is 64x6x63x6 etc.

So we have 64*6*63*6*62*6...32*6 possible positions in chess. Of course, not all are legal, but it's still a huge number.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Solving Chess Kickstarter

ZirconiumX wrote:
Henk wrote:Maybe we can extrapolate. How many records does a 1,2,3,4,5 or 6 men endgames chess database table have ?
If I remember correctly for 1 man it is 64x6. For two men it is 64x6x63x6 etc.

So we have 64*6*63*6*62*6...32*6 possible positions in chess. Of course, not all are legal, but it's still a huge number.

Matthew:out
I rustled up a quick Python program to work this out:

Code: Select all

``````def positions&#40;n&#41;&#58;
i = 64*6
n -= 1
if n > 0&#58;
while n > 0&#58;
i *= &#40;64-n&#41;*6
n -= 1
return i

for n in range&#40;0, 32&#41;&#58;
print "%d positions in a %d man database" % &#40;positions&#40;n+1&#41;, n+1&#41;
``````
I won't put the whole output on this page, but according to the program, there are:
3837824955509396206205398894933217531649406893072749958129150771163299840000000 positions in a 32 man database
Or put in a shorter form, 3.8378249555093959e+78 possible positions.

If we store this with a 256 bit key and a 16 bit move, then we will use up 1.0793552951736499e+56 yottabytes of storage.

It simply isn't possible.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Solving Chess Kickstarter

ZirconiumX wrote:
Henk wrote:Maybe we can extrapolate. How many records does a 1,2,3,4,5 or 6 men endgames chess database table have ?
If I remember correctly for 1 man it is 64x6. For two men it is 64x6x63x6 etc.

So we have 64*6*63*6*62*6...32*6 possible positions in chess. Of course, not all are legal, but it's still a huge number.

Matthew:out
Although your numbers are not correct, your point "a huge number" is fully valid.

Henk
Posts: 5799
Joined: Mon May 27, 2013 8:31 am

Re: Solving Chess Kickstarter

Maybe one could store records of dedicated algorithms that generate many winning positions.

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Solving Chess Kickstarter

ZirconiumX wrote:If we store this with a 256 bit key and a 16 bit move, then we will use up 1.0793552951736499e+56 yottabytes of storage.
256 bit is clearly too much. With a proper index scheme you can definitly get down to around 150. Even less if you leave out obviously lost material configurations. And furthermore there is no need to store position move pairs, just knowing about positions is sufficient.