Home 
Search 
Today's Posts 
#1




Perfect Chess
Hi,
Are there any sources available online that discuss the mathematics of calculating every possible chess board position and linking the positions with every possible move. Obviously the number is far beyond what computers are capable today, but I am interested in some exact numbers to predict how much longer we will have to wait to see a computer play a 'perfect' game of chess. After much time and work, I believe I have calculated the exact number of possible board positions. Has anyone else calculated such a number? Cheers, Dan 
#2




Perfect Chess
"Death Eater Dan" wrote in message ... Hi, Are there any sources available online that discuss the mathematics of calculating every possible chess board position and linking the positions with every possible move. Obviously the number is far beyond what computers are capable today, but I am interested in some exact numbers to predict how much longer we will have to wait to see a computer play a 'perfect' game of chess. After much time and work, I believe I have calculated the exact number of possible board positions. Has anyone else calculated such a number? I'd be impressed if you did! Sure you could calculate the number of possible piece positions with basic arithmetic but that wouldn't be the whole answer. You would have to throw out positions where the king is in check, and other impossible positions. You'd also need to account for the 50 move rule, and 3 move repetition  boards with identical arangement of pieces are not neccesary identical positions (eg has the rook or king moved). But you did say after much time and work, so perhaps you have done it! Whats the answer? Please show your working Regards, Will McGugan 
#3




Perfect Chess
Best of luck on your 'much time and work'  see this:
http://mathworld.wolfram.com/Chess.html How does your answer compare? "Death Eater Dan" wrote in message ... Hi, Are there any sources available online that discuss the mathematics of calculating every possible chess board position and linking the positions with every possible move. Obviously the number is far beyond what computers are capable today, but I am interested in some exact numbers to predict how much longer we will have to wait to see a computer play a 'perfect' game of chess. After much time and work, I believe I have calculated the exact number of possible board positions. Has anyone else calculated such a number? Cheers, Dan 
#4




Perfect Chess
On Tue, 2 Mar 2004, Nanga Parbat wrote:
Death Eater Dan wrote: Are there any sources available online that discuss the mathematics of calculating every possible chess board position and linking the positions with every possible move. Obviously the number is far beyond what computers are capable today, but I am interested in some exact numbers to predict how much longer we will have to wait to see a computer play a 'perfect' game of chess. After much time and work, I believe I have calculated the exact number of possible board positions. Has anyone else calculated such a number? I've once read an article that said that such a program was already developped 50 years ago. Any correctly programmed chess program which is based on full width search and given infinite time and memory will do. Evaluation function needs to care only for mate, stalemate, threefold rep. and 50move rule. Mikko Nummelin 
#5




Perfect Chess
"Death Eater Dan" wrote in message u...
Hi, Are there any sources available online that discuss the mathematics of calculating every possible chess board position and linking the positions with every possible move. Obviously the number is far beyond what computers are capable today, but I am interested in some exact numbers to predict how much longer we will have to wait to see a computer play a 'perfect' game of chess. After much time and work, I believe I have calculated the exact number of possible board positions. Has anyone else calculated such a number? I can't believe that one can calculate it (correctly and accurately) in a time less than 8 years. Anyway i may be wrong and you may succeeded it in a much shorter time. But what correctly means? It means it has to be definitely a legal position. So which are the illegal positions you should exclude? There are the positions where one player is in check and it's not his move. Also other countless types of illegal positions like: 8/8/5K2/8/2k5/1p6/1P6/B7 w   that can't be reached with legal play. BUT also you have to define if you will handle the positions, taking into account the "En Passant" rule, or the "50 Move Rule", or the "3 Move Repetition" rule, or the "Stalemate"(??) rule, or the "Castle" rule or the player turn. And this is important. What this means? ###It means that if in one position X a player can "Castle" and in the same position X the same player can't "Castle", then how do you treat these 2 positions? Like one or like two? ###It means that if in one position X a player can capture "En Passant" and in the same position X the same player can't capture "En Passant", then how do you treat these 2 positions? Like one or like two? ###It means that if in one position X a player can "Castle" and capture "En Passant" and in the same position X the same player can't "Castle", and can't capture "En Passant" then how do you treat these 2 positions? Like one or like 2? ###It means that if in one position X a player can make a move and draw with the "50 move rule" and in the same position X the same player can't draw with the "50 move rule", then how do you treat these 2 positions? Like one or like 2? ###And generally all the combinations between them. So although it's a matter of definition of: "possible positions in chess" and one can ignore the above rules, i think one should take into account the above chess rules to be more general. So you should first give how did you define the "possible positions in chess" you are about to count(or that you have counted them), and then calculate them. Although i suspect that by saying "possible board positions" you refer to only the possible legal positions and not taking account the rules like "50 move rule", "Castle rule", etc... , if your number is something like 10^40 then you can write here the method and the number of course. 
#6




Perfect Chess
George wrote:
But what correctly means? It means it has to be definitely a legal position. So which are the illegal positions you should exclude? There are the positions where one player is in check and it's not his move. Also other countless types of illegal positions like: 8/8/5K2/8/2k5/1p6/1P6/B7 w   that can't be reached with legal play. Just because a position can't be reached from the initial position doesn't mean that it isn't a position. It could be set as a problem, for example. BUT also you have to define if you will handle the positions, taking into account the "En Passant" rule, or the "50 Move Rule", or the "3 Move Repetition" rule, or the "Stalemate"(??) rule, or the "Castle" rule or the player turn. And this is important. The 50move rule and threefold repetition are irrelevant. Any position that can be reached after repetitions can be reached without those repetitions. Even taking this into account, these two rules only _allow_ the claim of a draw; they do not mandate it. Stalemate is irrelevant: just because one of the players is stalemated in a position doesn't make it any less of a position. Castling and enpassant are relevant: the FIDE laws of chess define two positions as being different if they allow different combinations of castling and en passant. Dave.  David Richerby Crystal Drink (TM): it's like a www.chiark.greenend.org.uk/~davidr/ refreshing juice beverage but it's completely transparent! 
#7




Perfect Chess
I think, no matter how strong a chess engine can become, or how far it
can see ahead, it will be limited by the quantum laws of nature and a maybe small but always present biterrorrate as applied to the computer itself. In other words, even after an exhausting 100 ply search it will occasionally make a random error on its final choice of move. This random error may mask a truley decisive move later in the search. 
#8




Perfect Chess
[snips]
On Tue, 02 Mar 2004 20:27:37 +0200, Mikko Nummelin wrote: Any correctly programmed chess program which is based on full width search and given infinite time and memory will do. Evaluation function needs to care only for mate, stalemate, threefold rep. and 50move rule. Actually... infinite time and memory don't apply. A chess game has an upper bound on the number of turns involved (I *think* I recall Levy suggesting the limit was 3150 moves) and there's a finite number of options per move. One estimate suggests an upper bound of some 10^120 positions. Assuming the computer can examine one position per nanosecond, this would take about a trillion, trillion [6 more of these] trillion times longer than the universe has existed, it is not, technically, infinite. On the other hand, you'll have plenty of time to bone up on opening theory while the computer ponders its first move. 
#9




Perfect Chess
Kelsey Bjarnason wrote:
One estimate suggests an upper bound of some 10^120 positions. 10^40ish is the number I've heard. 10^120 is vastly too big: the crudest possible upper bound comes from the observation that each of the sixty four squares is either empty or has one of twelve different types of piece on it. 13^64 is about 10^71. And that includes the `position' where every square has a white king on it. :) On the other hand, you'll have plenty of time to bone up on opening theory while the computer ponders its first move. Research was done recently that said that, if you want to buy a computer to do a computation that will take longer than two years (I think), it is better to invest the money that you were going to spend on the computer and come back in a year. Then, the combination of the interest on the investment (which means you have more money to spend on computers) with the decreased price of higherperformance computers means that the computation will finish sooner than it would have done if you'd bought the best computer you could afford on day one. Dave.  David Richerby Dangerous Love Bulb (TM): it's like www.chiark.greenend.org.uk/~davidr/ a light bulb that you can share with someone special but it could explode at any minute! 
#10




Perfect Chess
David Richerby wrote:
10^40ish is the number I've heard. 10^120 is vastly too big: Depends entirely on what state you include. 10^40 is on the order of how many ways you can place the pieces in the original array on a chess board without taking the laws of chess into consideration  and it's high, as it includes pawns on first and last row, and other impossible positions. But as promoted pieces aren't included, it's also too low. 2*10^52 is said to be a better estimate. However, if the position includes state such as 50move clock and/or count of repeated positions, you get a lot more positions ...  Anders Thulin ath*algonet.se http://www.algonet.se/~ath 