Gomoku is an abstract strategy board game, also called Omok or Five in a Row. This paper explains the implementation of an AI with minimax alpha-beta search with a sequences pattern recognition.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2345678901234567890123456789012345678901234567890123456789012345678901234567890
% 1 2 3 4 5 6 7 8\textbf{}
%\documentclass[letterpaper, 10 pt, conference]{ieeeconf} % Comment this line out
% if you need a4paper
\documentclass[a4paper, 10pt, conference]{ieeeconf} % Use this line for a4
% paper
\IEEEoverridecommandlockouts % This command is only
% needed if you want to
% use the \thanks command
\overrideIEEEmargins
% See the \addtolength command later in the file to balance the column lengths
% on the last page of the document
% The following packages can be found on http:\\www.ctan.org
%\usepackage{graphics} % for pdf, bitmapped graphics files
%\usepackage{epsfig} % for postscript graphics files
%\usepackage{mathptmx} % assumes new font selection scheme installed
%\usepackage{times} % assumes new font selection scheme installed
%\usepackage{amsmath} % assumes amsmath package installed
%\usepackage{amssymb} % assumes amsmath package installed
\title{\LARGE \bf
GOMOKU \& Minimax-alphabeta search
}
%\author{ \parbox{3 in}{\centering Huibert Kwakernaak*
% \thanks{*Use the $\backslash$thanks command to put information here}\\
% Faculty of Electrical Engineering, Mathematics and Computer Science\\
% University of Twente\\
% 7500 AE Enschede, The Netherlands\\
% {\tt\small h.kwakernaak@autsubmit.com}}
% \hspace*{ 0.5 in}
% \parbox{3 in}{ \centering Pradeep Misra**
% \thanks{**The footnote marks may be inserted manually}\\
% Department of Electrical Engineering \\
% Wright State University\\
% Dayton, OH 45435, USA\\
% {\tt\small pmisra@cs.wright.edu}}
%}
\author{Mykola Shevchenko 130708081% <-this %stops a space
}
\begin{document}
\maketitle
\thispagestyle{empty}
\pagestyle{empty}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
Gomoku is an abstract strategy board game, also called Omok or Five in a Row. This paper explains the implementation of an AI with minimax alpha-beta search with a sequences pattern recognition.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{INTRODUCTION}
Gomoku is usually played on a board of 15x15 consists in position black and white stones on a board.$^{1}$ The player with five consecutive stones of the same color wins the game. The minimax algorithm focuses on minimizing the possible loss for a worst case (maximum loss) scenario. The recursive implementation allows the algorithm to be considerably fast with reasonable winning moves.
\section{IMPLEMENTATION}
\subsection{Strategy}
The strategy is hidden in the evaluation function, which is responsible for determining how good or bad a move is. This is achievable by constructing a tree with a specified depth and to give each position of stones on the board a score that would represent the gravity of future probable situation. In fact, it is important to understand that the minimax algorithm always implied the opponent will make the best possible move.
Therefore the final outcome will depend only on the sensible weight specified to different combinations.
\subsection{Minimax implementation}
This algorithm allows the evaluation of a position and decides how efficient it would be for a player to reach that position.$^{2}$ However, it is not the most optimal solution because it might get lost in evaluating poor scenarios while there would be some obvious winning once. In fact, whenever it is applied to games like Gomoku with board 8x8 (=64 cells with three possible states: white, black or null), the time to compute all the possible combinations is unacceptable.
$$
64^3 = 262144
$$
The algorithm minimax will have to analyze all 262144 scenarios. To make the algorithm more efficient, alpha-beta pruning is integrated into the method. It seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It consists of passing two key values to determine if a branch is worth being analysed.
\subsection{Alpha-beta integration}
The min. (alpha) and max. values (beta) are recursively passed into the arguments of the function and get assigned the best score so far. The cutoff happens whenever we want to skip a tree as we know the move we already did is good enough. This allows our program to think quicker and still be reasonable.
Whenever a specified depth is reached, it stops creating new moves for both players. This is where evalution of the board happens.
\subsection{Evaluation function}
The evaluation function is what analyzes the best moves and give each board a score. The depth in the search determines the amount of moves the algorithm will predict. In the current scenario the depth is four which means two plies for each player will be on the board.
\subsection{Pattern Recognition}
The implementation in this paper is based on translation of rows, coloumns and diagonals into sequences of string. After every translation, each sequence is analyzed on multiple values and possible strategic combinations. The biggest score is assigned to a five in a row "GGGGG" (e.g = 1000). The least dangerous combinations are given a lower score. Therefore combinations
$$x4 = 100, x3 = 10, x2 = 1.$$
In order to achieve better performance during evaluation it is crucial to increase the possible combinations. In fact, the second most strategic possible combos are the empty spaces around streaks. In fact whenever on the board there is a space, it is translated in the straing as an underscore. This allows the evaluation to search for patterns as GG\_GG or G\_GGG where the underscore is currently the space in the middle of the stones translated as G.
\section{CONCLUSIONS}
The current algorithm is able to block a casual user with a common intention of creating four in a row. These possible moves are predicted and blocked, while at the same time the algorithm considers the best strategic moves. The current depth is 4 and it is relateively fast (less than 0.5 seconds) and responsive.
\addtolength{\textheight}{-4cm} % This command serves to balance the column lengths
% on the last page of the document manually. It shortens
% the textheight of the last page by a suitable amount.
% This command does not take effect until the next page
% so it should come on the page before the last. Make
% sure that you do not shorten the textheight too much.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{ACKNOWLEDGMENT}
I would like to thank my companion Henrik Skogmo for intense coding and exciting Waterloo battles.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
\bibitem{c1} YourTurnMyTurn.com team, Introduction and object of the board game, Go-moku rules, accessed 3rd March 2016, http://www.yourturnmyturn.com/rules/go-moku.php
\bibitem{c2} ME 575 - Optimization, Minimax and Maximin Optimization, accessed 3rd March 2016, <
http://apmonitor.com/me575/index.php/Main/MiniMax>
\end{thebibliography}
\end{document}