Unformatted text preview:

CSE 4308 / CSE 5360 - Artificial Intelligence I Homework 2: Two-Player GamesCSE 4308 / CSE 5360 - Artificial Intelligence IHomework 2- Fall 2013Due Date: Oct. 1 2013, 12:30 pmProblems marked with a∗are required only for students in the graduate section (CSE 5360). They will begraded for extra credit for students of CSE 4308.Minimax Search1. Consider the following game tree where the utilities of terminal nodes are indicated below the leaf nodes.97106965121210a) Perform standard Minimax search on the tree and indicate the resulting utilities at all the nodes inthe tree. Also indicate which of the two choices the Max player should play at the root of the tree.b) Perform Minimax search with alpha-beta pruning on the tree. Indicate which branches are pruned(assuming that the search visits nodes from left to right ). Also indicate next to each node either itstrue value or its α or β value.2. Consider the following two-player game. Starting with 7 tokens on the table, each player at each movecan either pick up 1 or 3 of them. Whoever picks up the last one looses and has to pay the other player aprize equal to the number of tokens that the winning player has picked up during the game.a) Draw the corresponding Minimax search tree, including the utility values at the leaf nodes.b) Perform Minimax search on the tree and indicate all the utilities at the nodes in the tree.c) Perform Minimax search with alpha-beta pruning on the tree. Indicate which branches are pruned(assuming that the search visits nodes from left to right ). Also indicate next to each node either itstrue value or its α or β value.2013 Manfred Huber Page 1CSE 4308 / CSE 5360 - Artificial Intelligence I Homework 2: Two-Player GamesGame Playing3. Consider a generalization of the game in Problem 2 where there are initially n tokens and each player has3 choices, namely removing 1, 2, or 3 tokens. Scoring (i.e. utility calculation) works the same way as inProblem 2.a) Implement a game playing program that (starting with the initial n tokens) plays against a user. Theprogram should first ask if the human or the computer has the first move and then start the game.Whenever it is the user’s turn, the program should read a move from the keyboard. For moves bythe computer you should implement an appropriate game search (this also requires the capability toidentify terminal nodes, i.e. nodes where there are not tokens left). Once the game terminates yourprogram should indicate who won and what the score obtained by the human player is.To limit the search time of the computer (for larger n this problem is too complex to search itexhaustively) you have to implement a limit on the number of nodes that are opened before thesearch terminates. For this assignment your program should open no more than 400 nodes beforechoosing a move (if you make this parameter flexible you can use it to regulate the strength of yourcomputer player). Not being able to exhaustively construct the search tree implies that you haveto implement a heuristic evaluation function which replaces the actual utility in cases where thesearch stops before reaching terminal nodes (such an evaluation function could look at a variety ofdifferent features - e.g. since it is also possible for the opponent to force a round to collectivelyremove 4 tokens, the remainder of a division by 4 can be indicative of part of what is achievable.(Note: it is very difficult for this problem to come up with a very good evaluation function. Whilethe program will play stronger with a better evaluation function, the goal here is not to come upwith an optimal evaluation function).b)∗Implement a second pruning strategy for your computer player to decide which nodes to expandand when to stop (e.g. α − β pruning or quiescence). Your agent with this second pruning strategystill has to respect the 400 node limit. Run this agent against your first agent and compare theirperformance (e.g. which player was stronger ? How many nodes did each one expand ?, How manyplies did each player look for (i.e. what was the depth of the deepest node the player looked at) ?).Expectiminimax4. Consider a modified version of the game from Problem 3 where each player in each round has to firstflip a coin and based on the outcome has the choice either between removing 1 or 2 tokens, or betweenremoving 1 or 3 tokens. The scoring is again performed in the same way as before.a) Draw the Expectiminimax search tree, including the utility values at the leaf nodes, for a start statein which there are 5 tokens on the table.b) Perform Expectiminimax on the tree and indicate all the utilities at the nodes in the tree.c)∗Implement Expectiminimax without pruning (i.e. such that it explicitly visits all the nodes) for thisproblem with a general start state with n tokens on the table. Note that you are not asked to comeup with an evaluation heuristic or pruning function (however, this algorithm will potentially run fora very long time for large values n).2013 Manfred Huber Page


View Full Document

UT Arlington CSE 4308 - Homework 2

Download Homework 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?