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.
Solving Chess Kickstarter
Moderators: hgm, Rebel, chrisw
-
- Posts: 2
- Joined: Wed Feb 26, 2014 4:31 pm
- Location: United States
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Solving Chess Kickstarter
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.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.
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.
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.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.
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.
-
- Posts: 4367
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: Solving Chess Kickstarter
You might as well say, "At this point, a miracle occurs."
--Jon
--Jon
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
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.
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.
-
- Posts: 7220
- Joined: Mon May 27, 2013 10: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 ?
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Solving Chess Kickstarter
If I remember correctly for 1 man it is 64x6. For two men it is 64x6x63x6 etc.Henk wrote:Maybe we can extrapolate. How many records does a 1,2,3,4,5 or 6 men endgames chess database table have ?
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.
I believe in the almighty printf statement.
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Solving Chess Kickstarter
I rustled up a quick Python program to work this out:ZirconiumX wrote:If I remember correctly for 1 man it is 64x6. For two men it is 64x6x63x6 etc.Henk wrote:Maybe we can extrapolate. How many records does a 1,2,3,4,5 or 6 men endgames chess database table have ?
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
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)
Or put in a shorter form, 3.8378249555093959e+78 possible positions.3837824955509396206205398894933217531649406893072749958129150771163299840000000 positions in a 32 man database
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.
I believe in the almighty printf statement.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Solving Chess Kickstarter
Although your numbers are not correct, your point "a huge number" is fully valid.ZirconiumX wrote:If I remember correctly for 1 man it is 64x6. For two men it is 64x6x63x6 etc.Henk wrote:Maybe we can extrapolate. How many records does a 1,2,3,4,5 or 6 men endgames chess database table have ?
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
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Solving Chess Kickstarter
Maybe one could store records of dedicated algorithms that generate many winning positions.
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Solving Chess Kickstarter
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.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.