## Project Description

Design and implement an interactive 44 Tic-Tac-Toe game for a person to play against a computer. The game consists of a 44 grid. To win, a player must place 4 of his/her symbols on 4 squares that line up vertically, horizontally or diagonally (45 or 135 degrees.) Figure 1 gives an example of a winning pattern for the player with the X symbol.

Use the ALPHA-BETA SEARCH algorithm in Figure 2 to implement your game. Note that in the algorithm in Figure 2, the main function uses min_utility and max_utility as the initial alpha and beta values for the MAX-VALUE function, where min_utility and max_utility are the minimum and maximum utility values defined for terminal nodes in the game. This will allow your program to prune more branches and run more efficiently than using minus infinity and positive infinity as initial values as in the original alpha-beta search algorithm.

If your program cannot search to the maximum depth in reasonable time for a move (say 10 seconds), then you should cutoff the search at a certain depth level l and use the following evaluation function to estimate the expected utility value for non-terminal nodes

``````Eval ( s ) = 6 X 3 + 3 X 2 ( s ) + X 1 ( s ) (6O3 + 3O2 ( s ) + O1 ( s ))
``````

where s is the current state, X n is the number of rows, columns, or diagonals with exactly n X ‘ s and no O’s. Similarly, On is the number of rows, columns, or diagonals with just n O’s. To compute the above evaluation function, you should consider every row and every column but only the middle 45 degree diagonal (with 4 squares) and the middle 135 degree diagonal (with 4 squares). You should set the cutoff level l as far down as possible for your program to perform well (in terms of intelligence) and yet finish computing for a move within 10 seconds.

There are three types of terminal nodes: (1) player X wins, (2) player O wins, and (3) draw – 44 grid is filled up and neither player has 4 symbols lined up. Assign a utility value of +1000, -1000 and 0 to the three types of terminal nodes, respectively.

Each time the ALPHA-BETA SEARCH function is called to return the best action, output the following information (statistics) on the screen: (1) whether cutoff occurred, (2) maximum depth reached, (3) total number of nodes generated (including root node), and (4) number of times pruning occurred within the MAX-VALUE function and (5) number of times pruning occurred within the MIN-VALUE function. As a minimum requirement, your program will run in command line mode that allows the player to specify which square to place his/her symbol. C++, or Java are preferred programming languages. If you plan to use another language, send me an e-mail first.

Design three different levels of difficulty: 1 (easy), 2 (intermediate) and 3 (difficult). Let the design above be leve1 3 (difficult). You can think about how to modify the above design for the easy and intermediate levels. The human player can choose which level to play when the game starts.

## Extra Credits

The followings are optional. You can implement one or both of the followings to get extra credits.

• Design and implement a graphical user interface (GUI) that displays the 4 x 4 grid on the screen and allows the user to use the mouse to pick the square to place the symbol.
• [Invent another evaluation function Eval(s) and show that it performs better than the evaluation function above. If you choose to do this, you still have to implement the Eval (s) described above and then make comparison with yours.

What you need to submit:

• Source code for your program. Complete documentation and in-line comments are required for your source code. Points will be taken off if you do not have these.
• Your executable code.
• An MS Words, PDF, or plain text file that contains: instructions on how to compile and run your program, and a high-level description of your program design.

Demo: A 15-min demo of your program on your notebook computer will be required.

Here is something else we explain:

1. Let the computer (or the max player) have the X symbol and the human player have the O symbol.
2. When the game starts, let the human player choose whether to go first or second.
3. In the Project description, X3 is the same as X3(s) and O3 is the same as O3(s) in the equation for the evaluation function Eval(s).