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.