Go
We have two versions of Go available, Capture Go and the full version of Go.
Play against one of our Housebots, or, play against your own bots or your friends bots. The aim of Capture Go is to be the first to capture the target number of stones, or else to have captured the most stones when the game ends by both players passing their turns.
One player will have black stones and the other white stones. The game starts out with an empty board and black goes first.
A place on the board where any two lines meet is called an intersection, and the players take it in turns placing stones on unoccupied intersections. A player can also pass any of their moves, but keep in mind that if both players pass consecutively then the game ends and the winner is the player who has captured the most stones.
A block of stones of the same colour is called a chain. Two (horizontally or vertically) adjacent stones of the same colour are in the same chain. Two non-adjacent stones of the same colour can also be in the same chain if one of them is adjacent to a chain of the other.
On this board the two black stones form a single chain, but the white stones are two separate chains since they are not adjacent to each other.
On this board the five black stones form a single chain, but the white stones are three separate chains of one stone each.
To capture a chain of your opponent's stones you must have stones on every intersection adjacent to that chain. When a chain of stones is captured, those stones are removed from the board.
If it is the white player's turn and they place a stone in position (2, 2) on this board then the chain of three black stones will be captured and we will have the resulting board:
It's possible to place a stone on an intersection such that some of your own stones are captured. Such a move is illegal unless this move also captures enemy stones, and in which case these enemy stones are removed from the board but yours are not.
The winner is the first player to capture at least the target number of stones, or the player who has captured the most stones when both players pass consecutively. A tie is possible if both players pass with the same number of captured stones.
The full game of Go works like Capture Go, except for three things.
One: the game ends either when both players pass consecutively, or there have been a set number of moves (the maximum number of moves allowed; passes count too).
Two: when the game ends the winner is the player with the highest score according to the scoring method of the game (see below for the three scoring methods). The game is a draw if the players have the same score.
Three: there is an additional rule called the ko rule, which says that a player cannot place a stone in a position which would put the board in the exact same state as before.
Consider the board above. If it is black's turn and they place a stone in position (1, 1) then we will end up with the board below. If white were then allowed to play a stone in position (2, 1), this would result in the first board again. Therefore white is forbidden from placing a stone in position (2, 1) on this turn by the ko rule.
There are three different scoring methods that can be used:
- 1.Stone scoring
- 1.A player's score is the number of stones they have on the board
- 2.Territory scoring
- 1.A player's score is the number of empty intersections that are part of the player's territory. An intersection is part of a player's territory if it is empty and all adjacent intersections are of that player's colour or that player's territory. So then, a 'chain of empty intersections' is part of a player's territory if and only if it is adjacent to a stone of that player and no stones of the other player.
- 3.Area scoring
- 1.A player's score is the stone score plus the territory score. That is, the number of that player's stones on the board plus the number of intersections that are part of the player's territory.
Here are some suggestions of strategies to improve your bot's performance.
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.
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.
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.
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.)
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.
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.
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.
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.
Read about Go strategy and then write code to identify and appropriately respond to ladders, ko fights, etc.
Last modified 4yr ago