Author: Uri Blass
Date: 21:31:05 01/23/02
Go up one level in this thread
On January 23, 2002 at 23:06:25, Robert Hyatt wrote: >On January 23, 2002 at 22:56:07, Russell Reagan wrote: > >>I'd like to know two things for each of the values. I'd like to know the >>theoretical maximum value, and a practical maximum value for use in a chess >>program. >> >>Here's what I'd like to know: >> >>Maximum number of moves a chess game can last, and a good value for the maximum >>size of the move history stack. > > >The game is infinite. If you read the rules of chess, the 50 move rule >is not absolute, either side _may_ claim a draw after 50 non-capture/non-pawn >moves occur, but they are not _forced_ to do so. If you make the 50 move >rule forced, then the game is limited to rougly 5050 moves, assuming you >make 49 non-capture/non-pawn moves, then move a pawn or capture something, >then continue the process until there are only two kings left. > > > > >> >>Maximum number of legal moves in a chess position, and a good maximum value for >>the legal moves array. > > > >no one has beat 219 yet. But that doesn't mean it doesn't exist. I see no >reason to have _any_ maximum, just use an appropriate data structure instead >and if someone finds that oddball position with 500 moves you won't have a >problem... It is easy to prove that 500 is impossible. 27 is the maximal number of legal moves for a piece. 27*16<500 and it is easy to prove better upper bound I also believe that you never get more than 200 in your search in practical games so using 218 as the maximal number of legal moves is safe(I tried to use my program to get 219 legal moves in similiar positions to the position of 218 moves but I could find no example(my program calculated perft 1 of millions of positions that are similiar to the position with 218 legal moves when it calculated perft of a possible position some plies before the position with 218 legal moves and the maximal number was 218) Uri > > > >> >>I can't think of anymore maximum values that would be good to know, but I was >>just thinking about how horrible it would be to set the size of the move history >>stack to some value and then in some crazy game that is clearly drawn have my >>opponent draw it out hundreds of moves more by piddling around and making a pawn >>move every 40-50 moves. Not likely, but I'm sure stranger things have happened. >>Same with the legal moves maximum. I'd hate to miss a move because I didn't >>create a large enough legal move array. >> >>I recall someone a long time ago giving a value for maximum number of moves to >>be around 5,400, and I'm guessing that maximum number of legal moves is around >>80-100+. >> >>If all else fails, the legal move array could be 269, since that would account >>for 9 queens, 2 rooks, 2 bishops, 2 knights, and 1 king all with maximum number >>of legal moves. All of those pieces obviously cannot all have the maximum number >>of legal moves if they're all on the board, so 269 would be a safe maximum. >> >>As for the maximum number of legal moves, 6300 should cover it since 16 pawns at >>a maximum of 6 moves each, plus 30 captures, totals 126. So you could have 126 >>blocks of 50 moves. And I guess that would really be blocks of 49 moves, as 50 >>would be a draw, totallying 6174 total moves. >> >>Even at 6 bytes per move, that's only ~50K of memory. >> >>If anyone knows these exact values off hand, or cares to take the time to >>compute them accurately, I'd love to know them. If not I'll just shoot high and >>waste a few bytes :) >> >>Russell
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.