Home 
Search 
Today's Posts 
#1




solve for chess
In Matiyasevich's book on Hilbert's 10th problem, there was a passage on how it was undecidable for a result of a game to be determined from an arbitrary game. Is it still possible for a unavoidable algorithm/gambit for a win/loss/stalemat for either black or white to be determined. If so, what is computational complexity of solving chess?

#2




Of course, strictly speaking chess can be solved. It is a finite game,
with a specific starting point and a limited set of moves that can be made from any position. Therefore, it is POSSIBLE to determine best play for any position by analyzing the tree of all possible moves for that position all the way out to their gameending state, exactly like endgame databases do now. However, EGDBs are at this time only created for up to 6 pieces on the board. It's a VERY LONG WAY until we have the answer for all 32 pieces. It's taken about 68 years just to go from 5 to 6 pieces as being the "state of the art", because of the necessary computation time and storage requirements. How long will it take to get to 32 pieces? Even if progress is linear (and it won't be), at best it's going to take close to 200 years before chess is solved! jm 
#3




ContentTransferEncoding: 8Bit wrote: However, EGDBs are at this time only created for up to 6 pieces on the board. It's a VERY LONG WAY until we have the answer for all 32 pieces. It's taken about 68 years just to go from 5 to 6 pieces as being the "state of the art", because of the necessary computation time and storage requirements. I wasn't aware of the entire 6 man Nalimov tablebases being completed. Do you have a source and a hard figure for how many bytes it takes to hold all of the 3man, 4man, 5man and 6man Nalimov tablebases? How long will it take to get to 32 pieces? Even if progress is linear (and it won't be), at best it's going to take close to 200 years before chess is solved! Complete 3 man Nalimov Tablebase...80 kB (measured) Complete 3+4 man Nalimov Tablebases...30 MB (measured) Complete 3+4+5 man Nalimov Tablebases...7.5 GB (measured) Complete 3+4+5+6 man Nalimov Tablebases...12 TB (estimated) Complete 3+4+5+6+7 man Nalimov Tablebases...200600 TB (estimated) Complete 3+4+5+6+7+8 man Nalimov Tablebase...40180 PB (estimated) .... Complete 3+4+5+...+30+31+32 man Nalimov Tatablebases...???? I welcome any estimates that are better than the ones above, and I especially welcome anyone who has the courage to give me an estimate to replace the ??? above. I would also very much like some data on how long it takes/took to generate each set.  Guy Macon http://www.guymacon.com/  BTW, Here is a handy reference for expressing large numbers: ************************************************** *********** SHORT VERSION: k kilo 1.0E+3 x1,000 Thousand(US,UK) M mega 1.0E+6 x1,000,000 Million (US,UK) G giga 1.0E+9 x1,000,000,000 Billion(US) T tera 1.0E+12 x1,000,000,000,000 Trillion(US), Billion(UK) P peta 1.0E+15 x1,000,000,000,000,000 Quadrillion(US) E exa 1.0E+18 x1,000,000,000,000,000,000 Quintillion(US), Trillion(UK) Z zetta 1.0E+21 x1,000,000,000,000,000,000,000 Sextillion(US) Y yotta 1.0E+24 x1,000,000,000,000,000,000,000,000 Septillion(US), Quadrillion(UK) Note: vendeka, xenna, xenno, and vendeko are bogus. Before you try using them, please read these pages: [ http://home.att.net/~numericana/answer/units.htm#prefix ] [ http://home.att.net/~numericana/answ...re.htm#zillion ] [ http://physics.nist.gov/cuu/Units/prefixes.html ] [ http://physics.nist.gov/cuu/Units/binary.html ] LONG VERSION: ************************************************** *********** NAMED POWERS OF TEN  US VERSION   N/A 1.0E+36 N/A 1 000 000 000 000 000 000 000 000000 000 000 000  N/A 1.0E+33 decillion 1 000 000 000 000 000 000 000 000000 000 000  N/A 1.0E+30 N/A 1 000 000 000 000 000 000 000 000000 000  N/A 1.0E+27 octillion 1 000 000 000 000 000 000 000 000000 Y yotta 1.0E+24 septillion 1 000 000 000 000 000 000 000 000 Z zetta 1.0E+21 sextillion 1 000 000 000 000 000 000 000 E exa 1.0E+18 quintillion 1 000 000 000 000 000 000 P peta 1.0E+15 quadrillion 1 000 000 000 000 000 T tera 1.0E+12 trillion 1 000 000 000 000 G giga 1.0E+9 billion 1 000 000 000 M mega 1.0E+6 million 1 000 000 k kilo 1.0E+3 thousand 1 000 h hecto 1.0E+2 hundred 100 da deca 1.0E+1 ten 10 d deci 1.0E1 tenth 0.1 c centi 1.0E2 hundredth 0.01 m milli 1.0E3 thousandth 0.001 µ micro 1.0E6 millionth 0.000 001 n nano 1.0E9 billionth 0.000 000 001 p pico 1.0E12 trillionth 0.000 000 000 001 f femto 1.0E15 quadrillionth 0.000 000 000 000 001 a atto 1.0E18 quintillionth 0.000 000 000 000 000 001 z zepto 1.0E21 sextillionth 0.000 000 000 000 000 000 001 y yocto 1.0E24 septillionth 0.000 000 000 000 000 000 000 001  N/A 1.0E27 octillionth 0.000 000 000 000 000 000 000 000 001  N/A 1.0E30 N/A 0.000 000 000 000 000 000 000 000 000 001  N/A 1.0E33 decillionth 0.000 000 000 000 000 000 000 000 000 000 001  N/A 1.0E36 N/A 0.000 000 000 000 000 000 000 000 000 000 000 001 Note: vendeka, xenna, xenno, and vendeko are bogus. Before you try using them, please read these pages: [ http://home.att.net/~numericana/answer/units.htm#prefix ] [ http://home.att.net/~numericana/answ...re.htm#zillion ] [ http://physics.nist.gov/cuu/Units/prefixes.html ] [ http://physics.nist.gov/cuu/Units/binary.html ] ************************************************** *********** NAMED POWERS OF TEN  UK VERSION   N/A 1.0E+36 sextillion 1 000 000 000 000 000 000 000 000000 000 000 000  N/A 1.0E+33 N/A 1 000 000 000 000 000 000 000 000000 000 000  N/A 1.0E+30 quintillion 1 000 000 000 000 000 000 000 000000 000  N/A 1.0E+27 N/A 1 000 000 000 000 000 000 000 000000 Y yotta 1.0E+24 quadrillion 1 000 000 000 000 000 000 000 000 Z zetta 1.0E+21 N/A 1 000 000 000 000 000 000 000 E exa 1.0E+18 trillion 1 000 000 000 000 000 000 P peta 1.0E+15 N/A 1 000 000 000 000 000 T tera 1.0E+12 billion 1 000 000 000 000 G giga 1.0E+9 milliard 1 000 000 000 M mega 1.0E+6 million 1 000 000 k kilo 1.0E+3 thousand 1 000 h hecto 1.0E+2 hundred 100 da deca 1.0E+1 ten 10 d deci 1.0E1 tenth 0.1 c centi 1.0E2 hundredth 0.01 m milli 1.0E3 thousandth 0.001 µ micro 1.0E6 millionth 0.000 001 n nano 1.0E9 milliardh 0.000 000 001 p pico 1.0E12 billionthh 0.000 000 000 001 f femto 1.0E15 N/A 0.000 000 000 000 001 a atto 1.0E18 trillionth 0.000 000 000 000 000 001 z zepto 1.0E21 N/A 0.000 000 000 000 000 000 001 y yocto 1.0E24 quadrillionth 0.000 000 000 000 000 000 000 001  N/A 1.0E27 N/A 0.000 000 000 000 000 000 000 000 001  N/A 1.0E30 quintillionth 0.000 000 000 000 000 000 000 000 000 001  N/A 1.0E33 N/A 0.000 000 000 000 000 000 000 000 000 000 001  N/A 1.0E36 sextillionth 0.000 000 000 000 000 000 000 000 000 000 000 001 Note: vendeka, xenna, xenno, and vendeko are bogus. Before you try using them, please read these pages: [ http://home.att.net/~numericana/answer/units.htm#prefix ] [ http://home.att.net/~numericana/answ...re.htm#zillion ] [ http://physics.nist.gov/cuu/Units/prefixes.html ] [ http://physics.nist.gov/cuu/Units/binary.html ] ************************************************** ***********  Guy Macon http://www.guymacon.com/ 
#4




I wasn't aware of the entire 6 man Nalimov tablebases being completed.
Do you have a source and a hard figure for how many bytes it takes to hold all of the 3man, 4man, 5man and 6man Nalimov tablebases? IIRC, the entire 6man tablebases in De Koning format were completed quite some time ago (meaning, possibly as much as a year ago) by Marc Bourzutschky. I do not know how much space they take up, but I have a vague memory of somebody saying that it was around 1.7 TB. I don't even know if he kept all of them, as his main goal was to produce the most interesting ones to verify certain wellknown studies. I'm pretty sure that Nalimov has personally completed all of the TBs in his format, but hasn't published them all yet. Guy Haworth, who keeps abreast of these things, might know more of the particulars. jm 
#5




Thanks for the information, can someone describe what method of encoding the Nalimov databases use for moves, pieces, games.
Last edited by entropy : September 10th 05 at 10:52 PM 
#6




entropy wrote:
Thanks for the information, can someone describe what method of encoding the Nalimov databases use for moves, pieces, games. None. They're endgame databases: they provide the 'score' for positions. The position is encoded to a number  that number is used to look up the score corresponding to that position: won in N moves, lost in N moves, or drawn. The positiontonumber transformation is as far as I know not documented,  Anders Thulin ath*algonet.se http://www.algonet.se/~ath 
#8




P.S. To further clarify what I have written below: It is not even
theoretically possible to solve chess, no matter what the computing power involved. Until a position is reached where a forced mate is guaranteed, there is no move sequence proven to win; and because such positions are always in advance of the starting position, a computer will never be able to determine whether it (or its opponent) can force mate until *after* some unknown (and unknowable) future move of its opponent places the board in such a position. wrote: wrote: Of course, strictly speaking chess can be solved. It is a finite game, with a specific starting point and a limited set of moves that can be made from any position. Therefore, it is POSSIBLE to determine best play for any position by analyzing the tree of all possible moves for that position all the way out to their gameending state, exactly like endgame databases do now. It isn't possible, for two reasons: first, because there is no meaningful definition of "best play" for *every* position; and second, because even deciding what a "good" move is, in any provable sense, requires full advance knowledge of the response of one's opponent under every possible variation from that position onward; this is not forthcoming from human players, and even chess engines may employ partial move randomization. A move in chess is frequently only potentially good or bad, depending upon the subsequent sequence, and some moves that are bad in the short term may end up being good, or even decisive, in the long term, in ways that are unpredictable at the time they are made (because the subsequent move sequence is unknown and unknowable). Even the blunder of a piece may result in the repositioning of other pieces in a way that permits the blunderer to force mate in some future position, i.e., a blunder may inadvertently place the right piece in the right place at what (in a future position) will be the right time; this is equivalent to a very long range combination, except that it is inadvertent. Let the position to be analyzed be the opening of the game from the starting position, before White moves. There is no "best play" for White. What criterion does one use for "best"? To achieve checkmate in the shortest number of moves? The shortest mate possible is not a static figure because subsequent moves alter the position and thus the figure, and it is not generally possible ahead of time to know which moves will be made by one's opponent; therefore nothing can be proven except provisionally, and the conditions upon which this provisional proof are predicated may change with subsequent moves. Furthermore, there are many ways to checkmate in, say, 20 moves. Which of them is "best"? Even in the case where a forced mate exists from a given position, more than one forced mate of the same (shortest) number of moves may be possible from that position. Furthermore, not every position is guaranteed to result in a forced mate, and there may also be many ways to draw in cases where it is possible to force a draw  not to mention many ways to lose in cases where it is possible to lose! For all of these reasons, it is not possible to "solve" chess. Mark Adkins 
#9




wrote: wrote: Of course, strictly speaking chess can be solved. It is a finite game, with a specific starting point and a limited set of moves that can be made from any position. Therefore, it is POSSIBLE to determine best play for any position by analyzing the tree of all possible moves for that position all the way out to their gameending state, exactly like endgame databases do now. It isn't possible, for two reasons: first, because there is no meaningful definition of "best play" for *every* position; and second, because even deciding what a "good" move is, in any provable sense, requires full advance knowledge of the response of one's opponent under every possible variation from that position onward; this is not forthcoming from human players, and even chess engines may employ partial move randomization. A move in chess is frequently only potentially good or bad, depending upon the subsequent sequence, and some moves that are bad in the short term may end up being good, or even decisive, in the long term, in ways that are unpredictable at the time they are made (because the subsequent move sequence is unknown and unknowable). Even the blunder of a piece may result in the repositioning of other pieces in a way that permits the blunderer to force mate in some future position, i.e., a blunder may inadvertently place the right piece in the right place at what (in a future position) will be the right time; this is equivalent to a very long range combination, except that it is inadvertent. Let the position to be analyzed be the opening of the game from the starting position, before White moves. There is no "best play" for White. What criterion does one use for "best"? To achieve checkmate in the shortest number of moves? The shortest mate possible is not a static figure because subsequent moves alter the position and thus the figure, and it is not generally possible ahead of time to know which moves will be made by one's opponent; therefore nothing can be proven except provisionally, and the conditions upon which this provisional proof are predicated may change with subsequent moves. Furthermore, there are many ways to checkmate in, say, 20 moves. Which of them is "best"? Even in the case where a forced mate exists from a given position, more than one forced mate of the same (shortest) number of moves may be possible from that position. Furthermore, not every position is guaranteed to result in a forced mate, and there may also be many ways to draw in cases where it is possible to force a draw  not to mention many ways to lose in cases where it is possible to lose! For all of these reasons, it is not possible to "solve" chess. Mark Adkins You're wrong, and it's very simple to prove. But, to start with the definition of "best play" that you asked for:  For any position that can be shown as won by the side to move, it is the move(s) that result in the shortest mate.  For any position that is drawn, it is any move that does not turn the position into a lost game.  For any position that can as lost by the side to move, it is the move(s) that result in forcing the opponent to take the longest path to mate. This is exactly how DTM endgame databases define it, and they work very well for that purpose. But your argument about requiring "full advance knowledge of the response of one's opponent" is completely beside the point. If you have a won position, it doesn't matter what your opponent plays as long as you still have a won position after your move. The same is true for a drawn position. You also say that "a move in chess is frequently only potentially good or bad, depending upon the subsequent sequence", but if there are 6 pieces left on the board, and I have all 6man EGDB files, there is no "potential" about it  the move is not only either "good or bad", but is actually "best play or not best play". The entire set of legal moves for every position involving 6 men HAS been determined to be either "best play or not best play". Additionally, I never said that "solving chess" meant "finding a move that wins". Your clarification in your followup post seems to imply that this is something that I stated. But it is not true. I'm only talking about finding "best play" from the starting position  not a WIN from the starting position. So, if it has been already done for 6 pieces, why not 7, or 8, or 16 or 32? The exact same mechanism that has SOLVED chess for 6 pieces can solve it for a larger number of pieces. And once it is done for all 32 pieces, (and it "only" needs to be solved from the starting position), chess will be solved. Whether the final result of chess is that it is drawn or won for White remains to be seen. jm p.s. And, yes, I'm aware of all the technical issues involving computing and storing the necessary data to get to this solution. That's not part of this discussion. In a mathematical sense, but not necessarily in a practical sense, chess can be solved. 
#10





Reply 
Thread Tools  
Display Modes  


Similar Threads  
Thread  Forum  
How long will it take to solve chess  please post a thousand replies  rec.games.chess.computer (Computer Chess)  
What do you do when you can't solve a chess book problem? Advice please.  rec.games.chess.misc (Chess General)  
No computer programs can solve this study! (and no, it is not retrograde)  rec.games.chess.computer (Computer Chess)  
stuck trying to solve mate in 1 puzzle  rec.games.chess.misc (Chess General)  
Fritz 8  Solve for mate  rec.games.chess.computer (Computer Chess) 