Maximum possible mobility

[pete205]

Hi,
I was wondering how large to make my array that holds the possible moves for a given position. I've searched Google to no avail. Does any one know the maximum possible number of moves (mobility) that is possible in a (sensible) game of chess?
So far I only have the move generation part of my program, having it play random chess against itself yields a maximum of about 65. Thinking about the problem though this is stupidly low -- anyone got the numbers though?
Failing that, does anyone know the maximum number of queens that have been on a chessboard in a professional match? -- that would help establish an upper bound.
thanks

[Zach Wegner]

Hi,
I was wondering how large to make my array that holds the possible moves for a given position. I've searched Google to no avail. Does any one know the maximum possible number of moves (mobility) that is possible in a (sensible) game of chess?
So far I only have the move generation part of my program, having it play random chess against itself yields a maximum of about 65. Thinking about the problem though this is stupidly low -- anyone got the numbers though?
Failing that, does anyone know the maximum number of queens that have been on a chessboard in a professional match? -- that would help establish an upper bound.
thanks

There's a position floating around with IIRC 219 moves. I use 256 as a conservative upper bound.

[Jan Brouwer]

These are some maxima I found:

Code: Select all

  // Maximum number of moves in a position:
  // ======================================
  // 1. no promoted pieces, without promotion moves: 109 white moves (W.Cross 1967) janb: ## according to me and my programs: 108
  // 2. no promoted pieces                         : 144 white moves (J.Ban 1960)
  // 3. with promoted pieces                       : 218 white moves (Dickins 1968)
  // 4. with all 32 pieces                         :  99 white moves (HH.Cross 1946)

  assert(Perft("5k2/2K5/3N1B2/P1NB4/6Q1/4R3/P1PP1P1P/1R6 w - - 0 1",                  1) == 108);
  assert(Perft("n1r1r1b1/1P1P1P1P/1Q6/3NBNK1/R7/4p1p1/3PBPkP/2R5 w - - 0 1",          1) == 144);
  assert(Perft("3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1",                1) == 218);
  assert(Perft("q2Q3r/n6R/kpB1N1K1/p1p1Bppp/1PN3P1/1n1pp1b1/P1PPPP1P/r5Rb w - - 0 1", 1) ==  99);

Note that if you generate pseudo-legal moves, the numbers may be higher.

[bob]

Hi,
I was wondering how large to make my array that holds the possible moves for a given position. I've searched Google to no avail. Does any one know the maximum possible number of moves (mobility) that is possible in a (sensible) game of chess?
So far I only have the move generation part of my program, having it play random chess against itself yields a maximum of about 65. Thinking about the problem though this is stupidly low -- anyone got the numbers though?
Failing that, does anyone know the maximum number of queens that have been on a chessboard in a professional match? -- that would help establish an upper bound.
thanks

There's a position floating around with IIRC 219 moves. I use 256 as a conservative upper bound.

I don't have any limit however. But a discussion years ago on r.g.c.c produced a position with 219 legal moves, although I don't know where it came from. No one has produced a position since that had more moves, although those were legal moves I believe, so pseudo-legal might go higher. I just don't remember for certain whether this was legal or just all moves.

[Zach Wegner]

Well, I should add that 256 is a limit only in a few circumstances: the root move list, the moves that are generated for SAN output, the move list at a split point, etc. During tree search I also have (nearly) unlimited move lists.

[Bill Rogers]

I think I remember someone posting a game here a couple of years ago that lasted 256 moves or very close to it. I was amazed to see a game that went that long.
Bill

[bob]

I think I remember someone posting a game here a couple of years ago that lasted 256 moves or very close to it. I was amazed to see a game that went that long.
Bill

That is nothing. I played a 3 0 game years ago (or crafty did) against a _human_ using pre-move with whatever GUI he was using and he was intentionally trying to blow up the old xboard limit of 256 moves in a game, which he did on multiple occasions until I figured out what was happening and got Tim Mann to increase the xboard move list to solve the problem. I could not imagine a human playing 256 moves in 3 minutes of clock time with zero increment, but it happened and he beat lots of programs doing it.

[Onno Garms]

Some time ago I noted the following maximum numbers for real games: 71 in a serious game in an international turnament, 62 between strong GMs (Karpov vs. Kasparow). In spite of some research I was unable to find the link again.

I also found a position with 225 moves on the internet, see
http://groups.google.de/group/rec.puzzl ... febb104b36
but clearly the counting is not correct there (queen on rank 2 counted twice).

Using the fact that the maximum of the moves of all pieces is less or equal the sum of the maxima for all pieces, we get an upper bound of 321. Using the fact that bishops and queens lose 2 squares when not placed on one of the four center squares, we get 307. It's easy to reduce that a bit further.

AFAIK it is unknown is the real maximum is less then 256, but many chess programs rely on that assumption.

[pete205]

Thanks to everyone for your help. Looks like 256 then -- although I might go with 192 as the max size since from Jan's data it looks as though the only way to top that is to get 9 queens(!). If my engine is cocky enough to waste time getting 9 queens it should rightly be punished by breaking. Of course, if the opponent gets 9 queens then it doesn't matter if it breaks, it has already lost.

[Bill Rogers]

Peter
I think that somehow we got away from your original question. I once put a subroutine in one of my development chess programs to keep count of the greatest possible moves it made during a game. I actually tried this using several different openings and was supprised to see that at one point or another during the game it calculated 55 possible moves for one side. If you found 65 then I would go with that number.
The rest of the answers seem be the number of moves in a complete chess game.
Bill