Game Play AI with Tic-Tac-Toe Example

In Gaming AI engine you have many ways for implementation but you have few strategic , you can calculate the current situation and play the best move , or estimate it based on thinking of the sequential of all possible movements, this is typically what happen in chess playing in particular, you spend a lot of time estimating the sequential of the all possible movement..

Another factor that affect the AI strategy which is the number of steps prediction ability and the more the number of future steps calculation the best AI engine results but the slower response (and difficult for programming)

Let's take Tic-Tac-Toe Game as a good simple example:

1) Non-predictive AI engine:
-We instantiate AI engine
-Update current border pieces positions
-Get the suggested move which is the best for current situation but not the best as strategic planning..

Note: For board gaming you need to represent the board by double array and the value of each item represent the current piece on it, in case of XO we can use 0 as empty 1 for X and 2 for O , for Chess it would be more complex , so you may need to have schema : 0 = empty ,1x = white piece (11=King, 12=Queen , 13=Rock,14=Horse,...), 2x = Black piece (21=King, 22=Queen , 23=Rock, 24=Horse,...)

public GameAI(int [][] box,int winValue,int lossValue,int levelOfAI) {
this.box=box;
this.winValue=winValue;
this.lossValue=lossValue;
this.levelOfAI=levelOfAI;
}

public int[][] play (){
//try to win the game
if(tryToWin()) return box;
//try to prevent him from win
if(tryToPreventLoss()) return box;
//try to play in the center
if(tryToCenteralize()) return box;
return box;
}

where try to win try to identify places to put the coin to win, while try to prevent loss try to identify certain places where the other user can win if left , and the third one try to centralize for the best wining options and it handle certain centralize problems according to the AI level you can skip certain conditions so it can be beaten by the user.

Also this AI engine can be used for suggested movement by the user by inverting the instantiation of win-Value and loss-Value.

2) Predictive AI engine:
-We instantiate AI engine
-Update current border pieces positions
-Get the suggested move based on predicted movement, so the suggested move is the best move for the number of predicted movement.

The predictive engine use the heuristic search algorithm to find the best movement, in case of XO we have the heuristic defined as :

E(n) = Hx(n) - HO(n) suppose the user play with the X piece
where
Hx(n) = Number of lines that can be completed by the X player
Ho(n) = Number of lines that can be completed by the O player

Example:



Hx(1)=number of line can be completed by X to win = red lines = 8 lines
Ho(1)=number of line can be completed by O to win = green lines = 4 lines
So E(1) = 8 - 4 = 4 and no other location of the X piece will give better heuristic value.

Another example:



Hx(1)=number of line can be completed by X to win = red lines = 8 lines
Ho(1)=number of line can be completed by O to win = green lines = 6 lines
So E(1) = 8 - 6 = 2 So if X-player select this location he will loss 2 advantage points over the O-player..

The Min-Max means you select the maximum for the current play and minimum for the next play (minimum for me = max for the opponent) then the max , min ,...etc.. until predictive steps ends up.

In the current tree, we will estimate the play for 2 future movement for the best current move for O player after the X played into the center, this is similar to what human brain calculate usually (So we will select max for the current play from the next level tree, then the minimum , ...etc..)



(Click on the image to enlarge)

NOTE:Consider the reflection of pieces position so the selected corner position for example, have 4 possible values, this is usually selected by random generation to make a difference in each playing movement, so whenever the X-player place the piece at the center the O-player should play a piece on one of the 4 corners..