Implementation of Artificial Intelligence , Machine Learning in TIC - TAC - TOE

INTRODUCTION

This project was originally developed by Mohd Akram. This project is a simple demonstration of the power of AI. The friendly language will help you easily understand the code. Hope that after reading this post you might be more interested in AI than before and would develop much better applications.

The Code ...

A brief description of the classes and their methods...

file         : TicTacToe.java

class      : TicTacToe

global variables  :

• winComb  - int[][]      : all winning situations
• state          - int[][]      : Current state of the Game
• pl1            - Player     : Player 1 object (Computer / Human)
• pl2            - Player     : Player 2 object (Computer / Human)
• butClicked- int           : Buttton recently clicked by the user
• w1            - int           : Number of games won by Player1(X)
• w2            - int           : Number of games won by Player1(O)
• dr            - int             : Number of game draws

Methods :

• public TicTacToe()
• public void start()
• public void refreshGrid()
• public static int checkWin(int turn,int[][] st)
• public static int checkWin2(String x,String o)
• public void print(String s)
• public void gameInit()
• private void initComponents()

file : Player.java
class : Player (abstract)

global variables : none

Methods :

• void playTurn(int pl,int turn)
• void playerInit()
• void notifyWin(int pl)
• void notifyLose(int pl)

file : Human.java

class : Human (extends Player)

global variables : none

Mathods :

• void playTurn(int pl,int turn) // overriden

file : Computer.java

class : Computer (extends Player)

global Variables :

• t - int - Turn number
• begin - Node - top element of the state tree
• current - Node - Current Node of state tree
• layerFiles - File[] - Layer Files from layer1 ...... layer 9
• layers - ArrayList<Layer> - layers of memory tree

Methods :

• public Computer(String l)
• public void evaluate()
• public void loadMind()
• public void saveMind()
• public void makeNewMind()
• public void playTurn(int p,int turn) // overriden
• void notifyWin(int pl) // overriden
• void notifyLose(int pl) // overriden

file : Node.java

class : Node

global variables :

• sub_nodes - ArrayList<Node> - connections of this node to its subNodes
• subNodes - String - Temporary storing id's of subNodes separated by " , "
• id - String - id of Current Node
• pref - int - Preference value of current Node
• n - int - No. of times this node is played
• lNum - int - The layer number in which this node exists in the memory tree
• comp - Computer - The Computer object this node belongs to
• nodeType - int - Stores whether this node is end node or not

Methods :

• public Node(String i,int l,Computer c)
• public void setAsState()
• public void playNext1()
• public void playNext2()
• public void playNextn()
• public void extractNodes()

file : Layer.java

class : Layer

global Variables :

• nodes - ArrayList<Node> - Stores reference to the Nodes in that Layer
• layerNum - int - Stores Layer Number(1-9)

Methods :

• public void refreshLayer()
• public Node searchByState(int[][] state)
• public Node searchById(String id)

DESCRIPTION....

The model of the game can be summarized as follows ....

The Game follows a very easy method of getting the most probable next chance ....  the method of finding the favourable state is explained later.

The GUI of the game is made with netbeans Form maker.

The Main Class(Tic Tac Toe)

Tic Tac Toe is the main class :

The state variable of type int[][] stores the state of the game. It is a 3x3 array initially filled with 0's.

1 stands for 'x' and 2 stands for 'o'. There are two objects of type Player named "pl1" and "pl2". The game alternately calls the playTurn methods of each player starting from player 1,updates the display and breaks the game whenever there is a win situation. The method "checkWin()" checks win situation. All the internel processing of the next Turn takes place by the Player object.

The Classes Human and Computer extend the Player class hence an object of either class can be stored in pl1 and pl2 objects.

The Display

The display part contains a 9x9 grid of jButtons.The text on top of these shows the block status.There is also a notification bar at the bottom of the jFrame. The bare at the right side of the jFrame shows three status : Number of games won by either player and Number of Draws.

The Player Class

This is an abstract class and is extended by a player type. It contains some necessary functions which a player should contain like playTurn() , notifyWin() , notifyLose() etc.

The Human Class

This is the interface between the human and the game . When the playTurn() method is callled , it waits until the user presses one of the button from the 9x9 grid. The static variable butPressed gives the recently pressed button and this inforation is used by the player Human class to fill a cell with 'x' or 'o' depending on the player turn Number. If it's an even No the object fills 'o' in the required cell otherwise it fills 'a' by setting the state variable of the Main class which updates the display after receiving a new state.

The notifyWin() and notifyLose() have nothing to do with the Human class hence are empty.

The method to fill a block by a Human Player is ....

The COMPUTER Class

This is where the main part of artificial intelligence comes. The Computer classes a tree method to store the possible sates , current states , and there preferences . The possible states of the game are stored in objects named Node. Each Node containes information about its state. Each Node has an id which represent the state of the Node.

The id is a String of 9 characters. Each Character shows a cell. 0 shows blank cell. 1 shows 'x' and 2 shows 'o'. example of an id is : "220211001" which represents the state shown on top of the page.

The Node also contains references to the nodes which can be played after the current node is played.At each call of the PlayTurn() the computer finds the most preferred state of the game after the current state by looking at the subNodes of the Current Node.The Most Preffered state is obtained by comparing the preference values of the subNodes and the subNode with largest value is set as the current state and also as the Current Node.There are two methods of finding and updating the preference values.

Initializing the Computer

The computer object is provided with a file path to the Layer Files which contain list of all the Nodes. There are nine layer files. If the layer files do not exist the computer makes new layer Files. Then Comes the part where the computer memory is created. The makeNewMind() method creates new Nodes or possible states of the Game without the layer Files and stores them in layer objects. Then it evalutes the Winning and Losing Situations by and updates their preference values by 100 and -100 respectively. The saveMind() method saves the layers date (i.e. the Nodes data) into layer Files. These Layer Files can be used to retain the memory of the game after the game exists. The existing Mind Files can be loaded by loadMind() method.
The Node "begin" is the first node of the Game (i.e. blank node).It is then manually connected to its possible subNodes by setting the variable subNodes and then calling extractNodes().

Playing the Turn

The computer plays the nextTurn by the process written above. The two methods are PlayeNext1()/PlayeNext2()(depending on the player No.) and the PlayNextn(). 

The playnext1() method prepares a list of all the Nodes having maximum preferences and then plays one of them. The PlayNextn() method plays the turn which is played least no of times thus not leaving any stone unturned. This method is useful when doing the evaluation process .
Method of finding preference :
The computer finds the preference f a node by adding the preferences of all its subNodes. This way the node having no chances of winning in the nextTurn hence having no positive value in its subNodes will have very less value of its own . This way the computer will go away from this node and thus will go toward a winning situation.
The Computer class does the job of finding the prefernces of all the nodes except the repfernce of the beginning node(i.e. the blank node).
On getting a win or lose state the Computer is notified and thus the computer decreases the preference of the current node by 10 if its a losing notification and if its a winning notification the computer increases the value of the currrent node by 10. This way upon playing many times by the playNextn() method we will get a clear map of the preferred and not unfavoured sates and what path to take in order to reach a highly favoured winning state. When playing against a human it's better to use the PlayNext1() method to play the turn because it makes best use of what it learned from previous games.

Files :

TicTacToe.java

Player.java

Human.java

Computer.java

Node.java

Layer.java

Conclusion

I hope you enjoyed reading my post and would be further interested in this topic. This Method can be used to develop other machine learning programs. I would be really happy to see this in other programs :) .

Credits

This project was developed by Mohd Akram ,an Intermediate student from India . I am 16 years old indian with many ideas in my mind and hope that you will help me make them come real.Thank You very much for reading my work.

email me at : mdakram28@facebook.com