Implementation and analysis of Monte Carlo Tree Search and Minimax algorithm for computer to play Dots and Boxes

Abstract

Implementation and analysis of Monte Carlo Tree Search and Minimax algorithm for computers to play Dots and Boxes is the online version of the pen and paper game, Dots and Boxes which is the most widely played game. We have made the Dots and Boxes game Convenient, Fast to Play, & of course pleasing to the eye (with our UI). The Rules of the game are simple: Players take turns joining two horizontally or vertically adjacent dots by a line. A player/Computer that completes the fourth side of a square (a box) colours that box and must play again. When all boxes have been colored, the game ends, and the player/Computer who has colored more boxes wins. Easy Right? Well not that easy when you play, it challenges your critical thinking as the game progresses. Keeping that in mind we also have scores counted by computer and shown as the boxes get colored to make sure the player knows. We have used Artificial Intelligence Algorithms Monte Carlo Tree Search for searching the game tree. Monte-Carlo Tree Search (MCTS) and other algorithms like MiniMax or Alpha-Beta pruning are used to play against human players and also against themselves, The process of Monte Carlo Tree Search can be broken down into four distinct steps, i.e. selection, expansion, simulation, and backpropagation. Minimax algorithm plays a critical role in selecting moves that will try to find moves that give fewer points to the opponent and more to the computer making it tough on an opponent.