EECS 3401 – Project1 [20 Points]
Due by 28th November 11:59pm EST
In the second project, you will design agents for the zero-sum game called Four in a Row. This is a two-player board game, in which the players choose a color and then take turns dropping colored discs into a seven-column, six-row vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical, or diagonal line of four of one’s own discs. Four in a Row is a solved game. The first player can always win by playing the right moves. See here for more details.
For this project, you will implement the following 3 algorithms:
•Minimax – Here you will implement depth-limited minimax which searches to an arbitrary depth as it’s not feasible to search the entire game tree.
•Alpha-Beta Pruning – This will speed-up the search as the depth of the tree increases, as it allows for more efficient exploration of the minimax tree
•Expectimax – This models probabilistic behavior of opponents that may make suboptimal decisions. For this you will have chance nodes that will replace the MIN nodes (AI-Agent2 or Human Player). For this implementation, consider you will only be running against an adversary which chooses actions uniformly at random, because Minimax and Alpha-Beta algorithms assume that MAX plays against an adversary who makes optimal decisions.
Pseudocodes for the above-mentioned algorithms have been provided in the lecture slides. Note that they only return the best utility value, whereas you need to select the action that is associated with this value. To implement this, please consider for the MAX player, all valid actions at the root of the tree, and then you return the action that leads to the best value.
There are some incomplete function definitions provided that need to be completed for the complete implementation of the game.
A GUI has been provided to simulate the game and test the performance of these algorithms.
The starter code that has been provided to you, includes two main files:
•four_in_a_row.py – This file includes all functions of the game. Also, an evaluation function has been provided to score the leaves of your minimax tree, in order to treat them as terminal nodes. o You have a choice to implement your own evaluate function, if you are able to think of a better one. A better evaluation function would mean it has lower computation time and/or higher winning percentage for a fixed depth compared to what has been provided.
So in case you’re up for the challenge, please explain your strategy with regards to choosing the evaluation function in a readme.txt file.
o For an AI-Agent to make its next move, it needs to run an adversarial search as a MAX player. In the case of Minimax and Alpha-Beta, the opponent is considered a MIN player. Whereas in the case Expectimax the opponent is considered a CHANCE player. For a Random-Player making a move, the move is a random valid move.
oAt the maximum tree depth utilities of the nodes should always be evaluated from MAX’s point of view, because during this process the adversary never considers its own score at all. Also, the adversary tries to minimize the score of the MAX player that initiated the game search is an assumption that minimax algorithm works under.
•game_gui.py – This file provides the GUI for the game and includes all types of players that can play the game. This file helps to display the game environment and select different game modes including AI-Agent1 vs AI-Agent2, and AI-Agent vs Human-Player, AI-Agent vs Random-Player, etc.
Types of players that can participate in the game:
•AI-Agent – This will be the agent that you implement
•Random Player – This kind of player chooses valid columns with equal probability
•Human Player – This will be a human playing the game.
To run the game, use the following command: python four_in_a_row.py
Make sure your code is well commented.
Submission Instructions: Your submission should be a zipped file, having the name
Firstname_Lastname_studentid_Project2.zip including your modified four_in_a_row.py file to Project 2 on eclass.
