Author: KarinsDad
Date: 08:30:16 04/18/00
Go up one level in this thread
On April 17, 2000 at 22:21:47, Flemming Rodler wrote: >Hi, > >Given any position that can be reached in a game of chess does anybody know of a >reasonable tight upper bound on the number of moves that can be played for one >side. It is easy to come up with a loose bound by saying > >2 rooks = max 28 moves. >2 Knights = max 16 moves. >2 Bishops = max 28 moves. >9 Queen = max 252 moves. (9*28) >1 King = max 9 moves. >---------------------------- >Bound = max 333 moves. > >Of couse the pieces might interfere with each other making this bound way too >loose. > > >Best regards >Flemming [D]Q5nk/2Q3Rp/4Q3/6Q1/1Q6/3Q4/1K3Q2/R6Q w Ra1 12 Qa8 18 Kb2 8 Qb4 21 Qc7 21 Qd3 25 Qe6 25 Qf2 21 Qg5 21 Qh1 18 Rg7 6 196 So, for this absurd example, there are 196 possible moves for white. This is probably close to the maximum. But, as can be seen, this is an extremely absurd example. Why? Because it would be extremely difficult to get to this position in a real game. The last move by black had to be ng8 and the move before that by white had to be Qa8 (regardless of whether these two moves were captures or not and regardless of whether the queen move was a check or not). But, before that, white had so many ways to checkmate (for about 20 or more moves now) that this position is unreasonable. Therefore, what I have given you is a non-reasonable tight bound. So, overall, if you write a program that handles number of legal moves and the program allows someone to enter in a random legal position, then it will require 8 bits (255 max) to store the number of legal moves. If the program does not allow you to enter in random legal positions, you could probably get away with 7 bits (127 max). However, I would think that most programs use a byte (8 bits) to store it since the 8th bit would have to be masked off anyway (i.e. waste of time) if it was used for anything else. KarinsDad :)
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.