AI Project Report(Tic Tac Toe Master) PDF

Preview

Summary

It is AI project report name Tic Tac Toe Master....

Description

TicTacToe-Master Documentation

Muhammad Nausherwan Tahir (SP16-BSE-025) Muhammad Waseem Akram (SP16-BSE-028) Haji Saeed Aslam (FA16-BSE-155) Talha Sadaqat (SP16-BSE-122)

28 Dec, 2018

1 Introduction 1.1 What is Tic Tac Toe Master? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 2 Backend Functionality 2.1 How Game work? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 3 Implementation 3.1 How to play? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 4 Algorithm Detail 4.1 Minimax Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.2 Alpha-Beta pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8 5 Grid Formation 5.1 Step Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 5.2 Possible Variation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10

1. Introduction: 1.1 What is Tic Tac Toe Master? Tic-tac-toe is not a very challenging game for human beings. If you’re an enthusiast, you’ve probably moved from the basic game to some variant like three dimensional tic-tac-toe on a larger grid. If you sit down right now to play ordinary three-by-three tic-tac-toe with a friend, what will probably happen is that every game will come out a tie. Both you and your friend can probably play perfectly, never making a mistake that would allow your opponent to win. But can you describe how you know where to move each turn? Most of the time, you probably aren’t even aware of alternative possibilities; you just look at the board and instantly know where you want to move. That kind of instant knowledge is great for human beings, because it makes you a fast player. But it isn’t much help in writing a computer program. For that, you have to know very explicitly what your strategy is. Tic-tac-toe is a casual strategy game for everyone. It is easy to teach, and the player can play this game almost everywhere. Because it only requires a writing tool and a writable surface. Vandalism is not recommended. Players: Two players Time estimation: one – two minutes 2. Backend Functionality 2.1 How Game Work The functionality that hoe game work? Is given in detail. Rules of the Game:   

The game is to be played between two people (in this program between HUMAN and COMPUTER). One of the player chooses ‘O’ and the other ‘X’ to mark their respective cells. The game starts with one of the players and the game ends when one of the players has one whole row/ column/ diagonal filled with his/her respective character (‘O’ or ‘X’).

A player can play perfect tic-tac-toe (win or draw) given they move according to the highest possible move from the following table. 1. 2. 3. 4.

Win: If the player has two in a row, play the third to get three in a row. Block: If the opponent has two in a row, play the third to block them. Fork: Create an opportunity where you can win in two ways. Block opponent's fork:

a. Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.) b. Option 2: If there is a configuration where the opponent can fork, block that fork. 5. Center: Play the center. 6. Opposite corner: If the opponent is in the corner, play the opposite corner. 7. Empty corner: Play in a corner square. 8. Empty side: Play in a middle square on any of the 4 sides. The first player, whom we shall designate "X", has 3 possible positions to mark during the first turn. Superficially, it might seem that there are 9 possible positions, corresponding to the 9 squares in the grid. However, by rotating the board, we will find that in the first turn, every corner mark is strategically equivalent to every other corner mark. The same is true of every edge mark. For strategy purposes, there are therefore only three possible first marks: corner, edge, or center. Player X can win or force a draw from any of these starting marks; however, playing the corner gives the opponent the smallest choice of squares which must be played to avoid losing. The second player, whom we shall designate "O", must respond to X's opening mark in such a way as to avoid the forced win. Player O must always respond to a corner opening with a center mark, and to a center opening with a corner mark. An edge opening must be answered either with a center mark, a corner mark next to the X, or an edge mark opposite the X. Any other responses will allow X to force the win. Once the opening is completed, O's task is to follow the above list of priorities in order to force the draw, or else to gain a win if X makes a weak play. 3. Implementation 3.1 How to play?   

Use any method to find who will start first. Then each player taking turn draw their symbol on a space from that nine possible spaces. The one who met the winning condition first win. If after nine possible spaces are used, but no one wins, that game is a draw.

Goal: The goal of this game is to be the first one who draws three of the player’s symbol to form one of these winning conditions. Winning Condition: These are the acceptable win condition of this game.

Diagonal win:

The player who controls O symbol won by drawing the three symbols in a diagonal line. Vertical win:

The player who controls O symbol won by drawing the three symbols in a vertical line Horizontal win:

The player who controls O symbol won by drawing the three symbols in a horizontal line. If no one wins, then the game is said to be draw.

It is the Draw form of the game. 4. Algorithm Detail: In this game we use two algorithm. The detail of both algorithm are given below. 4.1 Minimax Algorithm: Minimax is a kind of backtracking algorithm that is used in decision making and game theory to find the optimal move for a player, assuming that your opponent also plays optimally. It is widely used in two player turn-based games such as Tic-Tac-Toe, Backgammon, Mancala, Chess, etc. In Minimax the two players are called maximizer and minimizer. The maximizer tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible. Example: Consider a game which has 4 final states and paths to reach final state are from root to 4 leaves of a perfect binary tree as shown below. Assume you are the maximizing player and you get the first chance to move, i.e., you are at the root and your opponent at next level. Which move you would make as a maximizing player considering that your opponent also plays optimally?

Since this is a backtracking based algorithm, it tries all possible moves, then backtracks and makes a decision.

Maximizer goes LEFT: It is now the minimizers turn. The minimizer now has a choice between 3 and 5. Being the minimizer it will definitely choose the least among both, that is 3  Maximizer goes RIGHT: It is now the minimizers turn. The minimizer now has a choice between 2 and 9. He will choose 2 as it is the least among the two values. Being the maximizer you would choose the larger value that is 3. Hence the optimal move for the maximizer is to go LEFT and the optimal value is 3. 

Now the game tree looks like below:

The above tree shows two possible scores when maximizer makes left and right moves. As seen in the above example, each leaf node had a value associated with it. We had stored this value in an array. But in the real world when we are creating a program to play Tic-Tac-Toe, Chess, Backgamon, etc. we need to implement a function that calculates the value of the board depending on the placement of pieces on the board. This function is often known as Evaluation Function. It is sometimes also called Heuristic Function. The basic idea behind the evaluation function is to give a high value for a board if maximizer‘s turn or a low value for the board if minimizer‘s turn. For this scenario let us consider X as the maximizer and O as the minimizer. Let us build our evaluation function: i)

If X wins on the board we give it a positive value of +10.

ii)

If O wins on the board we give it a negative value of -10.

iii)

If no one has won or the game results in a draw then we give a value of +0.

We could have chosen any positive / negative value other than 10. Finding the Best Move: We shall be introducing a new function called findBestMove(). This function evaluates all the available moves using minimax() and then returns the best move the maximizer can make. The pseudocode is as follows: (i) Minimax: To check whether or not the current move is better than the best move we take the help of minimax() function which will consider all the possible ways the game can go and returns the best value for that move, assuming the opponent also plays optimally The code for the maximizer and minimizer in the minimax() function is similar to findBestMove() , the only difference is, instead of returning a move, it will return a value. (ii) Checking for GameOver state: To check whether the game is over and to make sure there are no moves left we use isMovesLeft() function. It is a simple straightforward function which checks whether a move is available or not and returns true or false respectively. 4.2 Alpha-Beta Pruning

Alpha: It is the best choice so far for the player MAX. We want to get the highest possible value here. Beta: It is the best choice so far for MIN, and it has to be the lowest possible value. The method that we are going to look in this article is called alpha-beta pruning. If we apply alpha-beta pruning to a standard minimax algorithm, it returns the same move as the standard one, but it removes (prunes) all the nodes that are possibly not affecting the final decision. 5. Grid Formation: The only important part of Tic-tac-toe grid is that it has nine spaces. The player can draw it anyway they like. The formation is given below in detail: 5.1 Step Up: i) Draw a 3 x 3, nine possible spaces grid as follow.

ii)

With any method, one player chooses to draw O symbol another player will draw X symbol.

In our project we use that number of grid shown in figure:

Possible Variations: The players can play the game with bigger grid 4x4 or 5x5, but it is recommended that they also expand the winning requirements to four or five symbols in a row. Show in figure below:

It is of 4x4 Grid.

It is of 5x5 grid....