1. Introduction

In recent years, the development of artificial intelligence (AI) has penetrated people's lives. People received the help of artificial intelligence in medical care, aviation, construction, and other fields [1-5]. In addition to these aspects, AI also offers important contributions in the field of gaming. Artificial intelligence refers to the use of computer programs to represent human intelligence. When artificial intelligence is applied to games, computer programs can do some operations instead of human thinking, so that people can play games with computers alone. These games may have been originally designed for multiplayer, but with the help of artificial intelligence, machines can operate like humans, or even better. When machines learn large enough content, their processing power can surpass that of humans, which is an area worth exploring. Therefore, people can practice or learn some skills through these AI games.

Artificial intelligence has a significant impact on board games. These games are usually adversarial games, originally designed for two or more players to play against each other. AI allows people to play board games against machines alone. AlphaGo is the world-famous example of AI applied to the game Go. In March of 2016, AlphaGo's victory over world champion Lee Sedol represents a very successful development of AI in the field of board game [6]. In addition to amazing events like this, people are constantly learning about artificial intelligence for board games. Karamchandani’s group published the way to design a tic-tac-toe game as a fundamental board game by using AI technique [7]. Reddy and his team used the BFS, DFS, the Minimax algorithm, Alpha-beta pruning, and evaluation function to create a gobang game in Android operating system [8]. Bouzy and Cazenave sorted out the current research on go game to analyze the algorithm and make some expectations for the future [9]. For chess, the group of Maharaj described how Bellman’s equation may be applied to optimize the probability of winning [10].

Although AI also plays the role of replacing real people in games, different kinds of games use AI in different ways. This article collects four different board games and analyzes some of their existing applications to artificial intelligence, namely algorithms. It will start with the relatively simple tic-tac-toe game, and then look at the more complex board game. In the second part, the paper will describe the research carried out by four different groups on four different board games. The article will describe what algorithms they used to apply to the game. In the third part, this paper will describe the actual results of the four teams' research on board games and their prospects. At the end of the article, we will summarize and discuss the four existing board games AI technology and look into the future.

2. Method

2.1. Tic-Tac-Toe

Tic-tac-toe is played by two players on a 3×3 grid. The player marks each step in the middle of the grid with crosses or circles. When one player first connects his three markers in a straight line, that player wins. Due to the small size of the board, the gameplay is relatively simple. When both players hold the best moves, there is a tie. The simplicity of tic-tac-toe also makes it more instructive. Whether it's training a child's mind or studying AI, it can be considered a good exercise. In the study of Karamchandani’s group, they assigned a value for each grid and tried to sum the scores in each game [7]. They write the Basic Step and Iterative Step through JavaScript.

2.2. Gobang

Gobang is an updated version of tic-tac-toe. Compared to tic-tac-toe, Gobang is bigger in board size. Usually, the standard is a 15×15 grid, and the pieces are laid at the intersections of the grid. Gobang pieces are divided into black and white. When one side succeeds in connecting five pieces of its own color in a diagonal or straight line, that player wins. Gobang has more possibilities due to the increasing complexity of the board size and the rules of the game. Reddy's team wrote Gobang's Android app in Java [3]. Compared to Tic-tac-toe, Gobang has a much larger board and a much more difficult goal to achieve. Thus, the possibility of gobang's existence is much more complicated than Tic-tac-toe, which means the basic minimax method would be very slow to calculate the winning strategy. Nevertheless, alpha-beta pruning and evaluation functions are helpful to reduce unnecessary steps.

2.3. Go

The board of Go is 19×19. Go pieces are black and white. Black squares go first, white squares go second. In the game, there were 180 pieces on both sides. The main purpose of the game is to use your pieces to form territory by surrounding the empty areas of the board. It is also possible to capture an opponent's pieces by completely surrounding them. The Go board is similar to the Gobang board, but the rules are different. In Go, Bouzy's group mentioned the EF Uses Tree Search, which is specific to Go game [9]. They also compared different kinds of algorithms like ProofNumber Search, quiescence search, and DepthFirst search. They analyzed the advantages and disadvantages of these algorithms and pointed out the conditions under which each was more suitable for use.

2.4. Chess

The chess board is 8×8 in size. The checkerboard is a square, consisting of 32 dark and 32 light-colored squares. The bottom right corner of the board must be light square. The pieces in chess are black and white. Each side has 16 pieces, namely one king, one queen, two rooks, two bishops, two knights, and eight pawns. These pieces have their own ways of moving. When the game starts, they are all placed in the prescribed squares on the board. The purpose of a chess match is to checkmate the opponent's king. Chess is more different from Gobang and Go game because it has different types of pieces. Maharaj's research group used the famous endgame study Plaskett's Puzzle from 1970 to compare the two leading Chess engines, which are Stockfish and Leela Chess Zero.

3. Result and discussion

3.1. Tic-Tac-Toe

Because of Tic-tac-toe's gameplay simplicity, Karamchandani's team solved the algorithmic problem relatively easily [2]. But since the game itself is prone to draws, there are limitations on the AI that prevent it from being powerful enough so that it could attract players. Over time, algorithmic updates and modifications can also improve gameplay.

3.2. Gobang

The Reddy team has also had success with the Gobang Android app. They demonstrated the actual operation and display of the game on the simulator. The game displays victory or defeat normally. If the board is full, the game is shown to be tied. For this article, the team said more work needs to be done on the evaluation functions and search algorithms. In addition, the prohibition rules of international rules can be applied to future games.

3.3. Go

The research of Bouzy group shows that each of the existing algorithms has its own advantages and disadvantages [9]. For connection problems, the three-value evaluation method is more effective, as well as Proof Number Search. However, the disadvantages of this approach are time consuming and large memory footprint. Quiescence search algorithms can play an excellent role in dealing with the problem of uncertainty. The alpha pruning method can optimize other types of tree searches and reduce unnecessary search time. Depth-first search can quickly assess the current location. No matter in tactical search, or in global search, the appropriate search method should be chosen.

3.4. Chess

In the study of Maharaj’s team, Stockfish and LCZero represent two competing paradigms in the race to build the best chess engine. The power of the Stockfish engine is programmed into its search, and the power of LCZero is programmed into its evaluation. Stockfish's approach is superior when faced with Plaskett's conundrum. The engine searches nearly 1.9 billion different locations to identify minimax solutions, which is extremely efficient. Domain-specific search optimization enables it to find unique solutions. On the other hand, LCZero's selective search is less efficient, mainly because it selects the wrong rows for deep search. But the LCZero engine is built on "zero" knowledge of the game, not the rules. Therefore, the LCZero algorithm is more general than Stockfish.

4. Conclusion

This paper summarizes the application of AI technology in four different types of existing board games. From the simple Tic-tac-toe to Gobang to the more complex Go and chess, the algorithms of every game have achieved some degree of success. For simpler games, AI can be created effectively without much algorithmic skill. For example, tic-tac-toe algorithm has basically met the needs. Nonetheless, for more complex games, more algorithms are needed to optimize the system. In terms of board game algorithms, search tree techniques still need to be constantly optimized and modified to be able to choose the best way to give the next step in different situations. Although the current chess AI technology has made a great breakthrough, which means it can run effectively and has a strong ability, but in the future, more advanced and more convenient algorithms will be developed. In recent years, humans and AI have been competing and learning from each other. With continuous development and innovation, better algorithms and other knowledge will be mastered.