dots-and-boxes

Dots and Boxes

Dots and Boxes is a pencil-and-paper game for two players written in Go based on the Fyne framework.

Game Rule

The game starts with an empty grid of dots. Usually two players take turns adding a single horizontal or vertical line between two unjoined adjacent dots. A player who completes the fourth side of a 1×1 box earns one point and takes another turn. A point is typically recorded by placing a mark that identifies the player in the box, such as an initial. The game ends when no more lines can be placed. The winner is the player with the most points. The board may be of any size grid. (Referenced from Wikipedia)

AI Model

We implemented seven levels of AI. They are as follows:

• Level 0 Model: Returns the empty edges on the board.
• Level 1 Model: Returns the edges on the board where a score can be obtained (if available).
• Level 2 Model: Returns the edges on the board where a score can be obtained; if none are available, it avoids edges where the opponent can score.
• Level 3 Model: Returns the edges on the board where a score can be obtained; if none are available, and if the opponent will inevitably score, it returns the edge that minimizes the opponent’s score.
• Level 4 Model: This model only activates during the endgame (the endgame is defined as when all positions on the board have at least two empty edges). If it is not in the endgame, it returns the result of the Level 3 Model. During the endgame, it sequentially adds an empty edge to the board and simulates a match between two Level 3 Models, returning the edge with the best outcome from the simulated match.
• Level 5 Model: The Level 5 Model considers all the best edges from the Level 4 Model as candidate edges and conducts several simulations of matches between two Level 4 Models. From the results of N simulations, it selects the candidate edge that performs the best.
• Level 6 Model: The Level 6 Model runs runtime.NumCPU() instances of the Level 5 Model in parallel, collects the results from all Level 5 Models, and selects the best edge based on the aggregated results.

Getting Started

To get started with Dots and Boxes, follow the steps below:

Prerequisites

Make sure you have the following installed:

• Go (version 1.18 or higher)
• Fyne framework for building the UI

Installation

1. Clone the repository:

$ git clone https://github.com/HuXin0817/dots-and-boxes.git
$ cd dots-and-boxes

1. Install the dependencies:

$ go mod tidy

1. Generate code:

$ go generate ./...

1. Run the game:

$ go run main.go

Customization

You can modify the game grid size and AI settings by editing the game configuration in the source code. For example, you can change the grid size in the main.go file and adjust the AI behavior by modifying the AI model files located in the src/ai directory.

Contributing

If you'd like to contribute to the project, please fork the repository and submit a pull request with your changes. Make sure to follow the Go code style for consistency.

License

This project is licensed under the MIT License - see the LICENSE file for details.