Dots And Boxes
Dots And Boxes is played on a rectangular grid of dots. Players alternate drawing a horizontal or a vertical line between adjacent dots - if they complete a box then they score 1 point (per box) and get another turn. The player with the most points once all of the boxes have been completed wins.
The template code, found in the Online Code Editor, works out what all the valid moves are and picks one at random. This can be improved by finding valid moves which complete a box and picking one of those at random, if any exist. Can you use the doesCompleteSquare() function to implement this?
In some cases, one line can complete two different boxes. By adapting doesCompleteSquare(), or writing a new function, you could prioritise such lines over lines which complete only one box.
Next, you could think about how to guard against your opponent using the same strategy. It might help to start by writing a function which calculates whether, if you play a certain move, your opponent will be able to complete a box on their next turn.
One way to do this is to calculate what the new grid and squares will look like after your move, and then using findLegalMoves() and doesCompleteSquare(), but there is a faster method. Maybe trying out a practice game on pen and paper will be helpful – what type of moves let your opponent complete a square in the next turn?
Advanced strategies involve analysis of “chains” – a collection of adjacent boxes where the exterior lines are filled in, and the interior lines can all be filled in by one player in a sequence of moves, as they get another turn each time they complete a square. For instance, the game below has a chain of size 3 in the leftmost columns, which makes a better sequence of moves than joining a line to make two squares in the rightmost columns. (In fact, in this case the player can complete both chains to score five points, but advanced analysis may look at which chains it is possible to create/complete in a couple of turns in the future.)
The calculate_move() function is the equivalent of your main function. This is where you need to make your changes and from where you will control the game. The function:
- 1.Receives information about the game in a Python dictionary called 'gamestate'.
- 2.Returns a game move.
In order to work out what move you want to make, the calculate_move() function is given as input the gamestate. The gamestate is a Python dictionary where all of the game information is held. Examples of accessing data in the gamestate are:
gamestate["Dimensions"][0] # number of rows in the grid
gamestate["Grid"] # the list of lines and which player (if either) has chosen this line already
The gamestate contains the following keys:
Key | Description |
Dimensions | A list of two integers, the number of columns and the number of rows of dots in the grid. |
Grid | A list of lines, each represented by two coordinates and a value to indicate which player has coloured in the line (if either). See below for more detail. |
Squares | A list of boxes, each represented by the four lines in the box and a value to indicate which player has coloured in the box (if either). See below for more detail. |
IsMover | A Boolean value indicating whether it is your turn to move. It will always be true when the calculate_move() function has been called. (Delve deeper into the code if you want to do some processing during your opponent's turn.) |
ResponseDeadline | The epoch time, in milliseconds, that a successful move has to be sent and received by to prevent you from timing out. (Epoch time is the amount of time that has passed since midnight on 1 January 1970, which can be accessed in Python with time.time().) |
GameStatus | A string that will have value "RUNNING" if the game is in progress or a reason the game has ended otherwise. |
MyScore | Your current score—the number of squares you have completed. |
OppScore | Your opponent’s score—the number of squares they have completed. |
InvalidMove | A value which is "None" unless the user has made an invalid move. |
OpponentId | The name of your opponent's bot. |
An example gamestate:
{
'Dimensions': [3, 2],
'Grid': [[[0, 0], [1, 0], -1], [[0, 1], [1, 1], -1], [[1, 0], [2, 0], -1], [[1, 1], [2, 1], -1], [[0, 0], [0, 1], -1], [[1, 0], [1, 1], -1], [[2, 0], [2, 1], -1]],
'Squares': [[[[[0, 0], [1, 0], False], [[0, 0], [0, 1], False], [[1, 0], [1, 1], False], [[0, 1], [1, 1], False]], -1], [[[[1, 0], [2, 0], False], [[1, 0], [1, 1], False], [[2, 0], [2, 1], False], [[1, 1], [2, 1], False]], -1]],
'IsMover': True,
'ResponseDeadline': 1563537731769,
'GameStatus': 'RUNNING',
'MyScore': 0,
'OppScore': 0,
'InvalidMove': None,
'OpponentId': 'housebot-practise'
}
There are two representations of the board in gamestate, one representing the lines that have been played ("grid") and another representing each box ("squares").
- Coordinate: a list of two numbers, representing a dot on the grid. [0, 0] is the top left dot. The coordinates represent the x and the y axis, using 0-based indexing, so for instance [2, 3] is the dot on the third column and the fourth row.
- Grid: A list of lists, where each list represents a line. It contains two coordinates and an integer, -1, 0 or 1. This integer is -1 if neither player has drawn the line, 0 if you have drawn this line already and 1 if your opponent has drawn this line. For instance, the list [[1, 0], [1, 1], 1] means that your opponent has drawn a vertical line between the dots in the top two rows of the second column.
- Squares: A list of lists, where each list represents a box. It contains four lines and an integer, -1, 0 or 1. Each line consists of two coordinates and a Boolean, which is False if neither player has drawn the line and True if either player has drawn the line. The integer at the end of the list is -1 if the box has not been completed (i.e. not all lines have been drawn), 0 if you have completed the box and 1 if your opponent has completed the box.
Every time it is your turn, the game engine will run your calculate_move() function, which needs to return a valid move. A valid move is a list of two coordinates, representing adjacent dots which do not currently have a line between them.
For example, [[0, 1], [1, 1]] is a valid move (unless it has already been played), because there is a horizontal line between [0, 1] and [1, 1].
- findLegalMoves(grid) – Given a list representing the lines on the current board, return a list of all possible valid moves – that is, a list of representations of each line which has not yet been drawn.
- doesCompleteSquare(move, squares) – Given a valid move and a list representing the squares on the current board, return a Boolean which is True if the move would complete at least one box (i.e. if the new line forms a square with other lines already on the board) and False otherwise.
Last modified 3yr ago