I am trying to create a simple AI that can play Go using Monte Carlo Tree Search.
This question, however, is valid for all games where players take turns doing some action that, on average, reduce the amount of possible actions to take in the future. (Other examples might be Tic Tac Toe, Connect 4 and a whole bunch of others.), or any situation in which we need to "Pick a random possibility until it is within expected parameters".
In Go, Players take turns placing a stone of their color on the board. As the board fills up, some moves are no longer valid (For instance, because there might be a stone at that location already.*)
The algorithm should pick a move at random. However, how do we ensure that the move we picked is valid? I see the following options, each with their own drawbacks:
When the move is not valid, pick a new random one. Drawback: The program is now probabilistic; it is very possible that it picks only invalid moves repeatedly, and therefore never finishes executing.
When the move is not valid, move to the next square (wrapping around at the edges of the board). Drawback: When there is a large region of the board that is already occupied, the distribution of moves picked is no longer random: It is far more likely that the position right next to the filled area is picked, as when the random number falls in this range, this is the chosen square.
First obtain a list of all possibilities, and choose a random element from this list. This ensures an equal distribution of probabilities. Drawback: Because we need to iterate over the whole board and obtain a list of all possible moves, this is inefficient. As the algorithm should run as fast as possible (As we want to simulate as many games as possible), iterating over the whole board should best be avoided.
Now, I am wondering if there exist another method of picking a move at random that:
- Does not significantly favour certain outcomes over others.
- Will terminate.
- Does not need to find out all possible moves from a certain position beforehand.
*(The rules of Go have more conditions for a move to be valid, but these do not change this question)