Computer dots

логическая настольная игра точки искусственный интеллект аватарArtificial intelligence (AI) is the science about the development of the intelligent software and technical devices. The term machine game is used in the AI field and it means the development of the software that can play games. The development of the AI for playing dots is called the computer dots.

Various software that allows playing dots against the AI has been created from the beginning of the 2000s. It was at that time that the first theoretical studies of this subject appeared. However, up to this day there is no program that can compete even with the mid-level player. Dots is a positional game with a huge number of combinations. This fact seriously complicates the creation of effective AI algorithms. In addition, the software development is not accompanied by the considerable intellectual and financial resources.

The first known work devoted to the AI in the dots game was the article "Methods and algorithms" (2002) by Pavel Torgashov. He implemented his ideas and algorithms in the Points v.3.1c program. In addition, a few unpopular AI programs appeared in the early 2000s under the influence of Torgashov’s article. His article described the use of the minimax algorithm for the moves search, the evaluation of the playing position, the evaluation of possible moves, and the reduction of the number of considered situations on the field (the truncation of the tree of variants).

In 2006 a polish player Bartek Dyda published his program called Kropki (he had worked on it since 1999). Bartek used the C++ programming language. Several new versions of his program appeared till 2011. In Kropki the move was searched using the minimax algorithm with the reduction of the search area by means of the alpha-beta pruning. The most important AI module was the technique of the position estimation. The program tried to estimate the number of dots necessary for the encirclement of each group of AI dots.

A new AI project appeared in the early 2010s. Later it split into the OpenPointsAI (2015) program by Evgeniy Kurnevsky developed using the rust programming language and the DotsGameAI (2012) program by Ivan Kochurkin developed using the C# programming language. Initially, the developers used the minimax algorithm, then they used the Monte Carlo tree search (MCTS). In addition the alpha-beta pruning and Zobrist hashing were also used.

In 2011 Alexey Pryimak published the DotsAI (PointsAI) v.1 program. It was written in java programming language. The program used the 9×9 cells patterns of game situations as the major way to choose the move. The patterns had different detalization. Some dots in the templates were insignificant, i.e. no matter either the dot was put or not and what color it was. The templates were divided into different types depending on their application. The program included about 1,000 templates. The program also had a constructor of trees of moves sequences, but the trees base was still small.

In 2016 the next version of Alexey Pryimak's program - DotsAI v.2 appeared. The main improvement in comparison with the 1st version is the transfer of all the logic of game situations into the trees of moves. The templates are used now only for comparison with the game situation. Logic became more flexible:  there’s the opportunity to add the conditions of the application of AI moves in the tree. The template size is increased from 9×9 to 15×15 cells. The patterns with the abstract moves acquired larger importance. The new algorithm of the encirclement is applied. The AI moves search is accelerated by 2. Also a lot of improvements are made in the program design.