2

Given the current board state of an ongoing game, (the position and color of the tiles on the board) is it possible to determine the moves each player made to arrive at that state?

Due to the number of possible board configurations that exist at each prior turn, I don't think it's possible, but I'm hoping I'm wrong.

If the game is only a few turns in, you can determine the moves easily, at a glance. (especially if you are familiar with the common opening moves). But by mid-game/late game, is it possible?

Can you utilize the same search algorithms used to drive an AI player (minimax w/ alpha pruning,for example) to go in reverse and determine the moves that have already been made?

Edit after reading @Zibelas comment : If it's not possible to get the exact moves, is it possible to determine any set of moves that would result in the current board state? As long as the moves are valid and the board configuration ends up in the right place, then that's fine.

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. You also know that both players have moved the same number of moves, (so black is the next to move) .

dontascii
  • 21
  • 2
  • 1
    It depends. Since it is possible to have the whole board filled with only one color, there are at least two different ways how you can reach that state (the second is a mirrowed version of the first). This means you can't say for sure that the given solution is the actual way the players played the game – Zibelas Feb 02 '23 at 14:31
  • 2
    If you're only looking for a list of possible move sets that lead to the current board state, that can be trivially proven to be "computable": have a program generate all possible move trees, and select from that any move trees that result in the target board configuration. This program will take a very long time to run (possibly longer than the life of the universe; depends on how much you optimize it), but it's still a valid program that will terminate in some finite amount of time. – Zags Feb 02 '23 at 19:04

2 Answers2

1

The less stones that are on the board, the higher is your chance that you can determinate the exact sequence of played stones.

But it is easy to prove that there are more ways to reach the same current state. if you imagine that the stones are placed on the board in a 4x4 block in the middle and white places them on this block to the right in the row 1 & 3 and black to the left of the block in the rows 2 & 4, you can switch the order of the rows and still get the same result.

Now let's talk about the brute force way to reach any solution that results in the current board. You can have at most 60 turns on a 8x8 board (64 places minus the 4 start chips). If we simplify the math and assume we have each turn 10 valid moves (the actual number is higher after a few turns), that means the total amount of different moves is 10^60. If a brute force program can calculate 10^9 moves per second, that still ends in around 3.17^43 years. Brute force is not the way to go. If the amount of stones is lower, brute force would be possible

But if we want to know the sequence that resulted in a board with maybe 20-30 placed stones, that can work, it should be possible to deduct the sequence of stones. There should be certain pattern that let you make for sure that a stone was placed there. The easiest would be corner stones. It might be more feasible to create a pattern matcher and reverse the board from there. How this would look in practice would be a better question for the coding Stack Exchange.

Glorfindel
  • 29,533
  • 7
  • 89
  • 137
Zibelas
  • 1,609
  • 5
  • 13
0

For any given board state, there are a limited number of moves from a valid previous state that could have produced what you see now. Given that, yes, it ought to be possible, in principle, to programmatically determine a move sequence from a standard starting board that will produce the state seen.

That said, there is the problem of determining the validity of the previous state for each back-move computation -- and the more stones are on the board, the larger this problem becomes. I'm no game theory mathematician, and can't say for certain, but it seems very possible that this prerequisite task is so computationally complex as to be impractical to determine.

This effectively becomes a problem of starting from the beginning state and working forward, likely a Very Large Number of times, to determine if a given state is valid -- which was the problem with brute-force computation of chess and go. Only when it became possible to program software that played like a human (ignoring what we would consider obviously bad moves) did the problem become tractable (along with training AI the same way a human master would be trained, by exposure to a large number of games).

Like many game problems, then, while probably possible in principle, this may not be practical with real world computing without involving a well-trained AI to validate board states.

Zeiss Ikon
  • 1,687
  • 12
  • 14
  • "I'm no game theory mathematician, and can't say for certain, but it seems very possible that this prerequisite task is so computationally complex as to be impractical to determine." I would be extremely surprised if that was true, especially since Othello has such a low depth/branching factor, compared to other similar board games. Also, if the position comes from a game played by a human, then you can use a heuristic to guide your search, by giving more priority to exploration of moves that could reasonably be played by a human. – Stef Mar 09 '23 at 21:02
  • @stef that's essentially what I wrote in my third paragraph. – Zeiss Ikon Mar 10 '23 at 11:59