13
$\begingroup$

I asked this over on boardgames SE, and was directed to post here in hopes of getting an answer. Original post is here: https://boardgames.stackexchange.com/questions/29824/othello-most-number-of-legal-moves-in-a-given-turn

Can anyone help me figure out the what the largest number of possible moves for a given turn would be in Othello/Reversi using a standard 8x8 playing board? On the first turn, there are 4 possible legal moves, the next player has 3 possible, and depending on that move, the next turn there are 4 or 5 possible moves. I'm not sure how to go about figuring out the best-case case scenario for a player to gain the most possible moves that turn, and I'd like to find out what this maximum is. I searched around, but only saw information on maximum number of games possible, which is not what I'm looking for.

I spent some time trying to work out a solution, and made a guess at what a lower bound could be for this solution. Making the assumption that possible moves form the entire outside perimeter of the current game board, it might seem like a simple solution would be the outside perimeter of the board would be the maximum amount of moves, which would be 28 possible moves. However, it's not quite this straightforward, since the board could have holes in it, or a concave shape, which would increase the perimeter. However, I'm at a loss at how to determine what the 'best case' scenario would be to give the maximum possible positions, and at a further loss at how to verify that such a pattern could be created via playing a legal game (i.e. not just an arbitrary arrangement of pieces). Along this same line of reasoning, I figured there's also upper bound limit of at most 60, but this limit could be lowered a bit, probably somewhere around 8 or 10 less, although this is just a conservative guess at when there's enough pieces on the board to consider it for a possible game state with the maximum amount of moves. I believe the solution is some number between 28 and 40, but I have no idea how to determine the exact number.

Improve this question
$\endgroup$
4
  • $\begingroup$ Interesting problem. Maybe all game states can be simulated by a computer program but I'm afraid that there might be too many states to brute force a solution like that $\endgroup$
    – Ivo
    Commented May 4, 2016 at 13:04
  • $\begingroup$ What size board are you using? 8x8? $\endgroup$
    – LeppyR64
    Commented May 5, 2016 at 18:52
  • $\begingroup$ I asked the question with a standard 8x8 size board in mind, but I'm curious as to the solution for different sized boards now as well. An 8x8 board is estimated at less than 10^28 possible legal moves, according to en.wikipedia.org/wiki/Computer_Othello, regarding solving a perfect game. Simulating all possible games is not feasible, and reverse engineering a game is probably even harder. $\endgroup$
    – Incognito
    Commented May 8, 2016 at 5:44
  • $\begingroup$ It might be possible to solve the question for smaller boards and then notice a pattern or something. Have you tried doing that? $\endgroup$
    – ghosts_in_the_code
    Commented May 12, 2016 at 8:15

4 Answers 4

Reset to default
12
$\begingroup$

The upper bound limit is likely to be quite a bit lower than 60.

For the purposes of this I will assume that you are WHITE.

In order for you to have a valid move in Othello, you need a line formed by the empty space and at least one of each colour. The largest number of valid moves made possible by the presence of a single WHITE counter is 8 - one for each direction. This also requires (at least) 8 BLACK counters, so 9 counters total are required to produce 8 possible moves.
enter image description here

With a single BLACK counter, the maximum number of valid moves is 4 and requires a further 4 WHITE counters.
enter image description here

Though I have no mathematical proof, I would suspect that the upper limit on the number of valid moves can be no higher than the number of counters on the board, leaving you with a maximum of 32 valid moves with 32 counters in play. Here is an arrangement that achieves that:
enter image description here

I suspect, however, that this layout cannot be achieved through a sequence of valid moves as the previous move by black would have resulted in some of the central WHITE counters being captured.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I had 32 floating around in my mind as what seemed like a plausible solution, but had no backing to that theory except that it was half the size of the board. You've shown some good insight, so now I wonder if it's possible to make it to 32 with a valid game, or if that's just an ideal solution. $\endgroup$
    – Incognito
    Commented May 8, 2016 at 5:49
  • 4
    $\begingroup$ Consider a board with two vertically-connected white pieces near the middle, and two black pieces on either side. That's six pieces total, but White would have eight valid moves. While that doesn't show that it would be possible to have more than 32 legal moves, it clearly demonstrates that the number of legal moves is not bounded by the number of pieces, at least for positions that don't need to be reachable by valid play. Whether any position reachable by valid play would have more legal moves for the player on move than pieces on the board might be an interesting question, though. $\endgroup$
    – supercat
    Commented Jan 5, 2017 at 23:05
  • $\begingroup$ "it clearly demonstrates that the number of legal moves is not bounded by the number of pieces" -- So it's bounded by the number of pieces + 2 ... it certainly doesn't scale. $\endgroup$
    – Jim Balter
    Commented Jun 13, 2017 at 8:52
7
$\begingroup$

if the question still stands, in the Wthor database of 100.000 real games, the maximum number of legal moves is 21. And theaverage number is about 9.5 Olivier

Improve this answer
$\endgroup$
4
$\begingroup$

In 20,000 random games, the longest list of legal moves for any position was 24. After 10,000 the longest list was 22. You could make an estimate by playing many random games and recording the average and standard deviation of the move list lengths at every ply. Or you could make a pair of players that try to maximize the number of legal moves for either player over the next n ply -- then play them against each other.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Did you search for positions where the number of legal moves exceeds the number of counters on the board? It's certainly possible to place 10 markers on the board so that white would have 14 valid moves, but I don't know that any sequence with more valid moves than markers would be reachable in legal play. $\endgroup$
    – supercat
    Commented Jan 6, 2017 at 0:27
4
$\begingroup$

I wrote a hill-climbing algorithm that searches for configurations with the maximum number of legal moves. I've made sure that the initial 4 cells are filled, the number of white and black tokens is the same, and all the tokens form a single connected component.

The best I could find is a position with 34 legal moves for black (all empty cells). Here black is 'x' and white is 'o'. I doubt that this position is reachable in an actual game though.

. . . . . . . .
. o o x . o o x
. x x . . x x .
. o . o x x o .
. o x x x x . .
. o x o x x o .
. o . o . o o .
. . . . . . . .

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.