Part A: MinMax Search and Alpha-Beta Pruning (10 points) [Must be handed in individually]
These are problems to work out on paper and hand it as a document HW10.txt. When you are asked to insert values into the tree, you may draw a diagram using "ASCII Art", or you may simply list the values in a breadth-first (level by level) transversal of the nodes in the diagram.
"This lecture" refers to lecture on Tuesday 4/19, the first lecture on game playing.
Problem A.1:
Problem A.2:
Problem A.3:
Problem A.4:
Problem A.5:
Problem A.6:
Problem A.7:
Problem A.8:
Part B: Sim Pencil Game Player (90 points) [You may choose a partner to complete this problem if you wish]
For this problem, you are going to write a program to play a game called Sim, a simple game which can be played with paper and two colored pencils. After drawing six dots on the paper, each player takes turns connecting two dots (which can not already be connected) with a line, and the first player to draw a triangle loses (for more details see the Wiki page). This game as interesting connections to some deep mathematics about graphs, and one of the consequences of the theory is that there can never be a tie game.
We will play this using a GUI in which the human player always goes first, and draws red lines by dragging between two circles with the mouse, and the machine player responds by drawing a blue line:
You will be provided with the program SimGame.java which controls the main loop of the game, checks for legal moves and for wins, and manages the GUI. You must provide two classes:
Graph.java -- Provides the basic functionality to store the undirected graph (graphs will be introduced on Tuesday 4/26, or read this) and look for triangles, and
Player.java-- Contains a methodmove(Graph G)which takes a graph and returns the next move that the machine makes.
We will describe these in some detail below, but these overall requirements must be followed for your code to work:
(1) The human goes first, draws red lines, and the machine (your Player) goes second and draws blue lines.
(2) Neither player can redraw a line after it has been drawn, and neither player can draw a line from a vertex to itself.
(3) Your program should be written to play the game with six vertices.
The code distribution for this homework is here: ZIP
The Graph Class
The Graph.java class will represent the "board" on which the game plays, and it will function in this game the same as the 3x3 integer array in Tic Tac Toe: all the moves will be made in the graph, and players will add edges and remove edges as they try various moves (just as I placed moves on the TTT array and then removed them). There is ONLY ONE instance of the graph at any time.
You must use the technique of an "adjacency matrix" to store the edges of the undirected graph as explained in lecture on 4/26 (or read this): there will be N vertices (in fact we will use N = 6 only in this homework), and your adjacency matrix will store integers to indicate the presence or absence of edges:
private static int[][] B = new int[N][N]; // 0 = no edge; 1 = red edge; -1 = blue edge
Since we are storing an undirected graph, for simplicity we will store all edges twice, from source to target and then again from target to source. The graph shown above would, for example, be represented by the following matrix:
0 1 2 3 4 5 0: -1 -1 -1 1: -1 1 2: -1 1 1 3: -1 1 4: 1 5: 1
You must provide the following public methods in your implementation:
public Graph(int N); // a constructor for a instance of the class with N vertices public void addEdge(int u, int v, int w); // add an edge from vertex u to v with value w (which in this hw will be only 0, -1, or 1) public void removeEdge(int u, int v); // remove the edge from u to v and the (duplicate) edge from v to u public int getEdge(int u, int v); // return the value (-1, 0, or 1) of the edge that goes from u to v public boolean isEdge(int u, int v); // return true or false depending on whether there is an edge (of either color) from u to v public int degree(int v); // return the number of edges of either color connected to vertex v public int degree(int v, int w); // return the number of edges of color w connected to vertex v public void printEdges(); // print out the edge matrix, as shown above; this is only for debugging public boolean isCycleOfLength(int n, int w); // return true iff there is a cycle of length n among edges of color w
You should review the lecture slides on graphs to understand how to do these methods. Just remember that our undirected graph is written to store the edges twice, and your addEdge and removeEdge methods must account for this (the getEdgeand isEdge only need to check for one or the other). The only difficulty is in the last method, which you can see is called in the SimGame class to check if there is a triangle after each move, to determine the winner, i.e.,
if( isCycleOfLength(3, -1) ) Declare the Winner!
will return true if the machine (blue) just created a triangle, which is just a cycle in an undirected graph of length 3.
You do not need to do the Topological Sort algorithm (which is, in any case, defined for directed graphs) to find these cycles: instead write a depth-first method as a helper, which returns true iff there is a path of length n from u to v, connected only with edge of color w:
private boolean isCycleHelper(int u, int v, int n, int w) .....
Then you can call this helper as isCycleHelper(u,u,3,-1) on each node u in the graph, to see if there is a cycle anywhere in the graph of length 3.
For full credit, you MUST provide a unit test main method in your Graph class which tests that all the methods in the class work as expected.
The Player Class
The Graph class will represent the "board" on which the game plays, and it will function in this game the same as the 3x3 integer array in Tic Tac Toe: all the moves will be made in the graph, and players will add edges and remove them as they consider the various moves.
Your Player class should have a public method which returns the next Move:
public Move move(Graph G); // perform min-max on G and find the best move for blue
(This would be the same as the chooseMove method in the lecture code.)
The class Move is as follows, and it is provided at the end of the SimGame.java file, so that you can refer to it in your Player class:
class Move {
int source;
int target;
public Move(int s, int t) {
source = s; target = t;
}
public String toString() {
return "(" + source + "," + target + ")";
}
}We have provided a class RandomPlayer which simply chooses an available move randomly. After you create your Graph class, you should run the game with this player just to make sure everything is working properly with the graph class. After that, you should develop your own Player, based on an evaluation function and min-max search.
Your Player class should hold to the following requirements:
(1) You should NOT create multiple graphs during the min-max search, but pass the graph G through the recursion, adding and removing edges, as we added and removed moves to the 3x3 integer array in the Tic Tac Toe program.
(2) You must implement the min-max recursive evaluation, using alpha-beta pruning as shown in lecture;
(3) Your player class should not take more than 5 seconds (approximately) to respond with its move; this mean you can search to a maximum depth of perhaps 6-8 ply;
(4) You must implement an intelligent eval(Graph G) method which
(4.1) Returns a winning score for blue (e.g., 100000) if there is a red triangle in the graph, returns a losing score for blue (e.g., -100000) if there is a blue triangle, and
(4.2) If neither side won, then attempt to follow the strategy given in one of the Wiki pages devoted to this game:
A simple way to implement this strategy is to go through the vertices, and let
A = the number of vertices which have more than one blue edge connected;
B = the number of vertices which have more than one red edge connected;
Then, return B - A.
This is a very rough approximation of the strategy outlined in the Wiki. I encourage you to try other refinements suggested there, such as counting the number of forbidden edges, looking for cycles of length 4, etc.
Other elements of the strategy for the eval and min-max search algorithm for your player are up to you, but full credit will be given only to thoughtful , flexible solutions which involve (i) a useful evaluation function, and (ii) min-max search using alpha-beta pruning. One caveat: do not try to do any fancy strategy (e.g., looking for cycles of length 4, etc.) in the recursive min-max search; instead, do this in the evaluation function. You can be imaginative in your use of the calculation of the value of the graph, and give different weights to different features.
Hint: We have not talked about how to access the adjacency lists for each vertex in the graph. There is a simple way to do it: if you want to know the vertices which are adjacent to a vertex u in the graph, then scan across the matrix using getEdge(u,v) and reject any columns in which there is no edge:
for(int v = 0; v < N; ++v) if(getEdge(u,v) != 0) Then there is an edge between u and v, i.e., v is adjacent to u.
This will tell you if there is an edge of ANY color; you of course need to find triangles which are of a single color; you will therefore need to make a simple change to this code to see if there are adjacent vertices connected by a particular color.
You may, but need not, provide a unit test in the Player class that makes sure it works. The Player class will be fairly throughly exercised by SimGame, so it is not really necessary as a step in the development process.