How to pick a random move/action/element non-probabilistically?

Question

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:

1. Does not significantly favour certain outcomes over others.
2. Will terminate.
3. 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)

Answer 1

Let's try to analyse the costs

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.

is it? Even if you play in a 19x19 board and have only one move left, this gives you a 1/361 chance to pick it and you'll have to try 1660 times to have a 99% chance to terminate. This drops rapidly; for the previous move it's 828 and for the vast majority is around 20 so the average is around 27

the cost would be (pickMove + isValid)*27

Yes the worst case is inf but we want the average case.

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.

so this would be: 361 * isValid + pickMove

Maintain and update the list of possible moves to pick from.

finally, this would be pickMove + updateList

So now we have an approximation of the costs, which one is better?
(pickMove + isValid)*27 vs 361 * isValid + pickMove vs pickMove + updateList

I agree with ratchet freak that the solution with the list seems the best. But I don't know for sure; maybe updateList becomes super slow after adding all the rules for liberties and ko. Is the second one better than the first? Maybe not if pickMove is way faster than isValid.

But maybe we can avoid all these; I have a hunch that the following algorithm will generate a uniform distribution:

1. pick a move, n
2. if it's invalid, check square n+1
3. skip one square and check square n+3
4. if it's invalid, go to 4

the idea is to skip one more square for every invalid square you encounter. It might not work and it definitely involves more than one steps.

So my answer would: profile them. This is not a trivial case of using quicksort over bubblesort. And, in fact, sometimes it might actually not matter if you use bubblesort. Which brings us to my real answer: do you know that this is where you should focus your optimisation efforts?

Maybe most of the time is wasted in a datastructure or in RNG. Or maybe one approach enables parallelisation or you can write it a low-level language easier thus making number crunching faster. Yes it's probably your innermost loop but you should still implement, test and then optimise the performance.

Answer 2

Maintain and update the list of possible moves to pick from.

Changes to this list will be small per move on average and often localized to where the piece was put.

Answer 3

How about using a hybrid approach?

First, estimate the number of available valid moves. (Probably based on the percentage of the board that is covered with stones/pegs/pawns.)

If the number of available valid moves is large, then it is okay to follow the strategy of trying moves at random until a valid one is found, because it will soon yield a result.

If the number of available valid moves is small, then you know that iterating over the whole board and obtaining a list of all possible moves is not going to represent a terribly large overhead, so you can go ahead and construct this list and then randomly pick from the list a move which is already known to be valid.