Solving Chess Kickstarter

[ambrooks1]

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]

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]

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

--Jon

[lucasart]

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.

[Henk]

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

[ZirconiumX]

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

[ZirconiumX]

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(n):
     i = 64*6
     n -= 1
     if n > 0:
             while n > 0:
                     i *= (64-n)*6
                     n -= 1
     return i
 
for n in range(0, 32):
     print "%d positions in a %d man database" % (positions(n+1), n+1)

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

[Sven]

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]

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

[Edmund]

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.