Go Bot Strategy

Here are some suggestions of strategies to improve your bot's performance.

Pass to win at Capture Go

If your opponent has just passed their turn and you have more captures than they do, then you can pass your turn and instantly win the game.

Reduce invalid moves

There are are often many places on the board where you cannot place a stone, and you run the risk of your turn timing out if you keep trying invalid moves (especially as the board gets more full). A simple way to improve this is to keep randomly selecting an intersection until you select one that is unoccupied. But this is still very inefficient since you may be randomly choosing the same invalid locations multiple times. Thus you will want to iterate over the whole board, checking each intersection at most once. However, if you don't keep an element of randomness then at some point you'll pick an empty but invalid intersection and keep picking that same intersection until you time out. Look up Python's `random.shuffle` and see if you can use it to randomly iterate over the board without checking any intersection twice.

Capture when you can

If there is a move we can make that will instantly capture some enemy stones then it is probably better to make that move than to do something random (especially if we're playing Capture Go). Can you write a function that takes a board and a location on it and finds if a stone at that location has been captured? Then for every empty intersection you can see if anything would be captured by placing a stone there - you only need to check if any of the adjacent stones of the opponent's colour are captured. When you've done that you can find out which move captures the most enemy stones and return that if it captures at least one stone.

Eliminate invalid moves

It may be the case that you end up in a position where there are no valid moves, or they are so few that you still run the risk of timeout. Thus we want a method for knowing with certainty whether a potential move is valid. Then we can iterate over every intersection in turn and find a valid move if there is one; if there are no valid moves we can pass instead of timing out.

For Capture Go the only additional thing to consider is whether a move would be suicidal - cause the capture of your own stones (and no enemy stones) - and thus invalid. However, we only need to check this for moves that don't capture enemy stones; a move which captures enemy stones is legal even if it would otherwise capture your own stones. Note also that you only need to check if the stone that is placed would be captured; other stones of yours can only be captured if the stone that was placed is also captured.

For full Go you also need to ensure that you aren't breaking the ko rule, so for each move you consider you will need to check if the resulting board is the same as `gameState["PreviousBoard"]`. (It also improves efficiency to note that you are only at risk of breaking the ko rule when you are trying to place a stone where it would be surrounded - in other words it would be suicidal if not for the fact it was capturing enemy stones.)

Know your score

If you are playing full go then write functions to calculate you and your opponent's scores. Then you can pass if you are in the lead and your opponent has just passed. You can calculate your territory by removing all enemy stones and placing enemy stones on the other empty intersections; then your territory is the number of enemy stones that are captured on this board. Similarly for your opponent's territory.

Evading capture

Particularly if you cannot make any capturing moves, you may want to check if on your opponent's next turn they can capture any of your stones. Then you may find a move which will prevent this from happening, e.g. placing a stone where they would have to have gone to capture you. Remember to prioritise as well; if your opponent has the choose of capturing a small chain or a large chain, then maybe you should protect the large chain.

Setting up a capture

Sometimes you won't be able to capture a chain in one turn, but in two turns. Write code which identifies when this is the case and then makes the first step; next turn the code from earlier will hopefully finish the job. You might also generalise this to n-step captures, prioritising those with smaller n and larger chains.

Keeping an eye on your eyes

Do a bit of reading about Go and you'll come across the concept of "eyes". Write code that will identify eyes, and if any of your chains has a single eye then work towards splitting it in two or joining another one onto the chain. And you probably don't want to place stones inside your eyes unless you are deliberately splitting an eye. Also prevent any of your opponent's chains from developing a second eye.

Identifying other common structures

Read about Go strategy and then write code to identify and appropriately respond to ladders, ko fights, etc.

iconGoBlack.png
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License