3. Consider the connect-4 game (also known as 4 in a line) which is a two player game stated as follows:
A 7x6 (7 rows and 6 columns) rectangular board placed vertically is given. 21 red and 21 yellow tokens are to be placed on this board by two players which alternate their moves by dropping a token into one of the seven columns. The token falls down to the lowest unoccupied square. A player wins if he has connected four of his tokens vertically, horizontally or diagonally. If the board is filled and no player has aligned four tokens the game ends in a draw (see Figure Q4-1 for example).
You will design an AI agent to play against a human player. Formulate the problem as an adversarial search problem by answering the following questions:
a. Describe what will be the state. Give an example state. 4
b. State the initial state. 2
c. Let players be 'y' and 'r', and that 'r' always play first. Write a high level 4 pseudocode for the Player(s) function, where the function returns the current player (either ‘y’ or ‘r’).
d. Write a high level pseudocode for the Actions(s,p) function that returns 4 the list of available actions for player p in state s.
e. Write a high level pseudocode for the Result(s,a) function that returns 4 the new state after action a has been executed in state s.
f. Describe the terminal test. 4
g. Suggest an evaluation function as a heuristic or estimate during the 6