4

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)

  • 4
    If you want to program a game of Go, iterating over all fields to see if at least they are valid to play is the least of the effort you'll have to expend. Worrying over the cost of that check is completely inappropriate. – Kilian Foth Jun 10 '15 at 12:32
  • @KilianFoth What other parts of the game are you referring to? The actual updating of the liberties (and removing of liberty-less stones) of all stone groups is a problem that stays quite local. Evaluation of the final board is only done once the game is considered 'finished' and thus not at every move. What am I missing? – Qqwy Jun 10 '15 at 12:56
  • I'm guessing he's commenting on the difficulty of making a computer play go; though you do specify specifically choosing random moves. Purely random play in go is probably less effective than purely random play on a 50x50 tic tac toe board, against a human. – StarWeaver Jun 10 '15 at 15:03
  • @Qqwy AFAIK typical MCTS engines will use heuristics to choose move candidates with different probability. These heuristics will be more expensive to compute/update than merely tracking occupied points. – CodesInChaos Jun 11 '15 at 13:27
  • @CodesInChaos: AFAIK, in MCTS, the tree construction is done 1 node at a time (by playing a random game from that node) and the score in the node is the win/loss % of games started from its child nodes. The heuristic is only used in the 'decide from what node to start n random games from next' (favouring ones with high win %) and thus only once per randomly played game. – Qqwy Jun 11 '15 at 13:38
2

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.

  • A hybrid approach where you eliminate some points from the list (e.g those occupied by stones) and reject others once they're chosen is another possible choice. – CodesInChaos Jun 11 '15 at 13:31
  • The idea of profiling is a very good one. As for the 'n+1, n+2' option: This is actually the second case I describe. I do not think this is uniform, because take a situation in which only square 1 and square 10 are free. (on a board with 10 squares) now, there's a 1/10th chance of ending on #1, and a 9/10 of ending at #10. – Qqwy Jun 11 '15 at 13:35
  • In the 'random pick' case, what do you do after you ran 1660 random picks and are thus in the 1% chance of not finding one? discard the current simulation all together? – Qqwy Jun 11 '15 at 13:43
  • @Qqwy You could just run a while longer, the probability of not finding anything drops exponentially (assuming your PRNG is good). Or you could switch to another search algorithm (enumerate all valid moves, then pick one or error out if there is none) in that rare case. – CodesInChaos Jun 11 '15 at 13:57
  • @Qqwy, sorry, I should have made the notation cleaner (I meant that in every step n is the square you checked in the previous step); I suggested to visit squares n, n+1, n+3, n+5 etc So if you have 10 squares and 1-5 are taken, if you try to visit square 5 you get 6 but if you get 4 you end up in 7. Will probably break if the number of valid squares doesn't divide the number of total squares. As CodesInChaos said, you keep trying to get a valid move; but it's a good idea to have a break clause based on some metric i.e. number of moves so you don't wait for 1660 moves from the beginning – Thanos Tintinidis Jun 11 '15 at 15:27
9

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.

  • 1
    I agree. Maintaining the list means not having to perform the search all over again, hence you really only need to do this once. You wouldn't search for all available cards before drawing a random card from a full deck, you'd remove a random card from the remaining cards to choose from. – Neil Jun 10 '15 at 13:00
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.