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)
How to pick a random move/action/element non-probabilistically?
game development;random
Let's try to analyse the costsWhen 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 27the cost would be (pickMove + isValid)*27Yes 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 + pickMoveMaintain and update the list of possible moves to pick from.finally, this would be pickMove + updateListSo 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:pick a move, nif it's invalid, check square n+1skip one square and check square n+3if it's invalid, go to 4the 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.