Reversi/Othello - Given a certain game state (the arrangment of the tiles on board), is it possible to find a set of moves that would satisfy it?

Question

Edit- here are the rules of the game, if you are not familiar: https://en.wikipedia.org/wiki/Reversi#Rules

Let's assume black was the first to move on a standard 8x8 board with 2 tiles for each player placed in the center of the board in the traditional starting configuration for a Reversi game. We also know that both players have moved the same number of moves, (so black is the next to move)

Is it possible to find a set of valid moves that would result in the given board state? (It is understood that there are multiple moves that could result in a given state. As long as the moves are valid, I don't care)

By "board state", I mean the arrangement of tiles on the board.

I'm familiar with minmax algo (with alpha pruning) but I'm not sure if it can be used in this case.

This is what I came up with in my head:

1. White was last to move, so search for a continous line of white tiles
2. Flip all tiles in that line except for the first and last ones. (the ends)
3. Remove one end tile and keep track of its position on the board. This is a potential move. Leave the other end as-is.
4. Check if the board is in a valid state.

If you repeat these steps for black, then white, then black, and so on, you will either:

A. End up in the starting position. The result is a set of valid moves that satisfy the orignal board state. (The moves you kept track of in step 3)

B. If the board is valid but the next player doesn't have a move, it's possible that there was no valid move at that time. Record 0 for that move and keep going with the previous player.

C. Invalid board state. Delete the previously remembered move and restore the board state. Using the same player, start the process over again, looking for a continuous line of tiles. If no other lines exist, undo the next recorded move, and start again with the other player. Rinse. Repeat, until you arrive at A.

Depending on how far the game has advanced, this could take a. really. long. time. I might be overlooking some aspect of gameplay that would make it even more challenging.

This seems a lot more difficult than finding the best move using minmax, etc.

Has anyone successfully been able to do this programmatically? Is it even possible mid-to-late game?

I have not tried to do this yet in code. I'm trying to wrap my head around it first.

Answer 1

The obvious answer is "yes": simply generate all possible games with the number of given stones (which is finite) and select the ones which generate the position.

What you probably mean is: is there an algorithm to do it in a reasonable amount of time?

I think the question is interesting. I had the same question some 20 years or so ago, when I saw a position where the subtitle claimed one side was "clearly" better, when it looked like the opposite to me. But the Othello program I had at that time didn't allow setting up an arbitrary board position, it had to be a valid game sequence. Since I'm not an expert player, I was hoping to use that program to prove my suspicion.

My idea was similar to yours: just work backwards from a given position till reaching the starting position. I didn't know though who was last to move, which made it more difficult, but it's the same problem in principle. But the game was not very far, maybe 20 moves, so I thought it should be feasible.

I think I run my program for several hours, maybe days (I don't remember exactly) before I gave up. The combinatorial explosion is bigger than it looks initially.

One thing, which you seem to have overlooked in your above steps: it's not enough to just look at lines, you have to look at combinations of lines also. To give a simple example, let's say a section of the board looks like this:

O - - -
O - - -
O - - -
O O O O

Here O denotes a white stone and - either a black stone or no stone. Four white stones in a row mean 6 possible flipping scenarios, with two such lines that means 12. So far so good. But if the White move was in the lower left, we also have to consider the possible combinations, which are 4 extra scenarios. That may not sound like much in this example, but if you get additional lines like diagonals from the stone in question, the number of combinations quickly get multiplicative.

So while working backwards may be the simplest approach, I don't think it's a very practical approach. Surely my program from 20 years ago could be improved, and computers are much faster now, but my conclusion from this experiment was that it's a flawed approach in principle.

Instead, what I'd propose now is to work forward from the starting position and use some invariants from the given position. I.e. we know the outside disk were never flipped, this may be enough to keep the search tree in check, even though I'm sure there still would be a practical limit for the number of stones in the given position (but hopefully larger than 20). One reason I think this is, that usually the number of legal moves may go to about 10 in the middle game (and can be lower a lot of the time) whereas when backtracking there are usually much more possible scenarios. That may sound a lot like my initial suggestion of simply generating all possible games, but my point here is using as many invariants as possible. For an example that they can not only be deducted for outside stones let's hypothesize the following cutout from a given position:

X        
  X . . .
X X O O .
    . . .

(Here an X indicates either a black or white stone, a . no stone and the spaces can be anything.)

The right O stone was obviously placed by White, but from this we can deduce that the other O stone was placed by Black, even if the X's allow other scenarios in an earlier position. You may even deduce such things manually and just hardcode them in the search.

I feel there must have been already been research done in this area, but I wasn't able to find it.