Authored by Nonki Takahashi
Three days until yesterday, I had participated in the Game Programming Workshop 2014 at Hakone in Japan. I saw many presentations about many kind of games such like chess, shogi, Go, Reversi, mahjong, magic chess, Are You a Werewolf?, Xiangqi, Connect6 and so on. Many of the presenters have discussed about the game AI (artificial intelligence).
Today I will talk about game AI. Many of the games AI is divided into the following two. One is game tree search. The other is simulation.
Following picture is a sample of a game tree. Every node of the tree means one of the game position.
And games AI search these kind of game tree to win thee game. Most basic idea for game tree search is called minimax. Following picture shows how minimax works.
Sample code of minimax can be shown in my tic-tac-toe program LBW762-3 . This program calculates score for every node (game position): +1 means X wins, -1 means O wins, 0 means draw. X is max level player to maximize the score. O is min level player to minimize the score. My Connect Four program LSM678-6 also uses minimax algorithm.
But for some games, the game trees become too large. So, searching game trees is difficult for the games. Go game is one of these games. Recently many Go games AI do random simulation (called playout) many times to find better move. My program Go Simulator PTB804-2 shows just simulations.
Happy game programming!