Skip to content

A dots and boxes machine learning model & website

Notifications You must be signed in to change notification settings

suchir-g/doublecrossed

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 

Repository files navigation

doublecrossed

This is a small AI to play the game "Dots and Boxes". If you do not know the game check out it's Wikipedia (https://en.wikipedia.org/wiki/Dots_and_boxes).

The aim of the game is to complete as many boxes as you can, and the AI tries to play as optimally as it can to win - however it's not perfect especially on bigger boards. The way it does this is with various game theory approaches, and I aim to also train a machine learning model to compete against this model in the future.

This game is solved (https://en.wikipedia.org/wiki/Solved_game) for games upto size 4x5 (in dots). For a 4x4 game, the second player always wins assuming optimal play and for a 4x5 game it's always a draw. However, it is still unknown for larger board sizes and so to make a bot we have to use models which have the possibility of losing.

All of this information can be found in the links I provide below (and probably explained a bit better there too).

Essentially, the main rule you have to keep in mind whilst playing is the "long chain rule":

If you are player 1, you want the number of dots on the board + the number of long chains to be even, if you are player 2 you want this to be odd.

Note: a long chain is a chain of length 3+

The algorithm essentially revolves around this rule: playing and looking ahead to try and find a set of moves which forces the number of chains to be whatever it wants. If it cant look ahead that far/ or is in the endgame, then it uses a minimax algorithm to try and find the best sequence of moves.

The code is fully commented and explained as well.

https://www.youtube.com/watch?v=KboGyIilP6k&t=206s https://www.youtube.com/watch?v=rBngUo0JTzs Solving Dots and Boxes - scientific paper Book: The dots and boxes game by Berlekamp

About

A dots and boxes machine learning model & website

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages