TicTacToe in Prolog

In this project, you will implement the TicTacToe program in Prolog. The code you need to get started is in the file [[login to view URL]][1]. The example from Figures 4.15 and 4.20 in the Luger text is included here, and we suggest that you trace this example in Prolog. In the Prolog implementation, we will number the squares in the TicTacToe board and we will use this numbering in our interactions with the program. However, in our internal representation of the TicTacToe board, we will use the following Prolog term: rows( cols(_A, _B, _C), cols(_D, _E, _F), cols(_G, _H, _I) ) Initially, the variables in this term will be uninstantiated. (Notice that a call to the predicate **initial_state(Board)** will bind the variable **Board** to this initial uninstantiated representation of the TicTacToe board.) As the game progresses, the variables will be successively instantiated to the atoms **'X'** and **'O'** to represent the moves by the two players. The predicate **index/3** is provided to translate between the external positional representation and the internal variable representation of the board. Notice that the clauses of **index/3** are arranged in the default order that we have proposed for the moves in the game: center square first, then corner squares, then noncorner edge squares. We can thus enumerate moves in the default order by backtracking through **index/3**, or by backtracking through any predicate that is defined using **index/3**. For example, we can collect a list of moves in the default order by a call to **findall/3** or **bagof/3**. (Note: **bagof/3** is usually preferred to **findall/3**, because it handles free variables in a more sophisticated way.) ## Deliverables [login to view URL] according to requirements mentioned. 1. **move(+MaxMin, ?Square) ** The predicate **move/2** executes one move of the game, by instantiating **Square** to **'X'** if **MaxMin** = +1, and to **'O'** if **MaxMin** = -1. *Hint:* If you are trying to write something complicated here, you are on the wrong track. This predicate can be defined using two short lines of code! 2. **successors(+Board, +MaxMin, -Children) **This predicate is similar to the Scheme function with the same name. The variable **MaxMin** indicates which player is currently making a move: +1 indicates that the maximizing player is making a move (and in TicTacToe, the maximizing player is always **'X'**); -1 indicates that the minimizing player is making a move (and in TicTacToe, the minimizing player is always **'O'**). The variable **Board** represents the state of the game prior to the move, and the output variable, **Children**, is a list of the board configurations that the indicated player can reach in one move. *Note:* It is important that the terms in the output list, **Children**, all have distinct variables, none of which are shared with the variables in the input, **Board**. This can be accomplished by the use of the metalogical predicate **copy_term/2**. 3. **three_in_a_row(+Board, +Player) ** This predicate succeeds if **Board** represents a winning configuration according to the rules of TicTacToe, and fails otherwise. The variable **Player** is either the atom **'X'** or the atom **'O'**. *Note:* The mode specification here tells us that **Player** should be instantiated when the predicate is called, and that the uninstantiated variables in **Board**, if any, should not be affected by the call. 4. **evaluate(+Board, -Value) ** This predicate is similar to the Scheme function with the same name. It is true if **Value** is the heuristic value of **Board**, as defined in Figure 4.16 of the Luger text. *Note:* Make sure that the execution of this predicate does not instantiate any of the variables in **Board**. 5. **bestmove(+MaxMin, +Depth, ?Board) ** This predicate is similar to the function with the same name in your Scheme (or C) implementation of TicTacToe, but with a twist appropriate to Prolog. **MaxMin** is either +1 or -1, to indicate whether we are searching for the best maxmizing or the best minimizing move, and **Depth** is the cutoff depth for the minimax algorithm with alpha-beta pruning. But notice that there are no distinct input and output variables here to represent the state of the game! Instead, the predicate should be called with the variable **Board** instantiated to the current state of the game, and a successful minimax search should further instantiate the variable **Board** to the configuration that represents the best subsequent move for the indicated player. (To see how this should work, check out the use of **bestmove/3** inside the predicate **play/4**.) *Hint:* You will need a good understanding of how Prolog handles logical variables to implement this predicate correctly. Test files, trace and the Luger text is attached. ## Platform Unix