Dots ‘n Boxes Game Engine for Python

DnBPy is a light-weight Dots ‘n Boxes game engine for Python. It is
particularly useful for AI projects, and can be used as an environment
for Reinforcement Learning projects.

Installation

pip install dnbpy

Usage example

import dnbpy
# (2, 2) means: create a 2x2 board
# player identifiers are not limited to strings
game = dnbpy.Game((2, 2), ['player1', 'player2'])
game.select_edge(0, 'player1')
game.select_edge(2, 'player2')
game.select_edge(3, 'player1')
game.select_edge(5, 'player2')
print(game.get_score('player1'))
# 0
print(game.get_score('player2'))
# 1
print(game.is_finished())
# False

The Board State

The board state is represented as a bit vector. The bit vector’s length
is equal to the number of edges. The index of a bit in the vector
corresponds to an edge on the board. If the bit has value 1, the edge
is selected, and if the bit has value 0, the edge is unselected.

The board edges are indexed as follows (for the 2x2 case):

*    0    *    1    *
2         3         4
*    5    *    6    *
7         8         9
*    10   *    11   *

In the example above, if edges 1 and 5 are selected, the board state
will be 01000100000. For other board dimensions, the same
convention is followed for edge indexing. The horizontal edges at the
very top of the board are indexed first, left-to-right, followed by the
vertical edges of the first row, etc.

A board is described using the convention n x m, where n is the
number of rows, and m is the number of columns. The 2x3 case is indexed
as follows:

*    0    *    1    *    2    *
3         4         5         6
*    7    *    8    *    9    *
10        11        12        13
*    14   *    15   *    16   *

Boxes

A board consists of a number of boxes. The boxes on a board can be
accessed:

game = dnbpy.Game((2, 2), ['player1', 'player2'])
boxes = game.get_all_boxes()
print(len(boxes))
# 4
print(str(boxes[0]))
# 0-2-3-5
print(str(boxes[1]))
# 1-3-4-6
print(str(boxes[2]))
# 5-7-8-10
print(str(boxes[3]))
# 6-8-9-11

During a game, the game engine keeps track of the boxes that players
capture:

game = dnbpy.Game((2, 2), ['player1', 'player2'])
game.select_edge(0, 'player1')
game.select_edge(2, 'player2')
game.select_edge(3, 'player1')
game.select_edge(5, 'player2')
boxes = game.get_boxes('player1')
print(len(boxes))
# 0
boxes = game.get_boxes('player2')
print(len(boxes))
# 1
print(str(boxes[0]))
# 0-2-3-5

Built-in Players

DnBPy includes several built-in players, ranging from simple to more complex levels of sophistication and gameplay.
These players can be used as follows:

move = built_in_player.select_edge(game.get_board_state())

Assuming we already have a game of type dnbpy.Game initialized, and a built_in_player of type dnbpy.Policy
initialized, the select_edge function can be called to get the player’s next move. The following built-in players are
available:

Randomly-acting Player

selects an edge randomly
initialization: built_in_player = dnbpy.RandomPolicy()

Level 1 Heuristic Player

selects an edge randomly that completes a box, if possible; otherwise, it selects an edge at random
initialization: built_in_player = dnbpy.Level1HeuristicPolicy((rows, cols))

Level 2 Heuristic Player

selects an edge randomly that completes a box, if possible; otherwise, it selects an edge randomly that does not allow
the opponent to complete a box; otherwise, it selects an edge at random
initialization: built_in_player = dnbpy.Level2HeuristicPolicy((rows, cols))

Level 3 Minimax Player

uses depth-limited minimax search with alpha-beta pruning to estimate the value of a board position
initialization: built_in_player = dnbpy.Level3MinimaxPolicy((rows, cols), 3)

Command-line demo

DnBPy includes a simple command-line demo program. Start the program with:

python play.py

To play against the randomly-acting player, or the level 1, 2, or 3 heuristic player, enter one of $random, $L1,
$L2, or $L3 as a player name, respectively.