In the second exercise you are asked to implement, for the Backgammon environment of the previous exercise, an intelligent agent that plays the game. The agent will perform search into the game tree, with a depth varying dynamically, and choose the move based on maximum expected value. Thus, essentially you will be implementing an expcti-minimax algorithm. In addition, you should use modified alpha-beta pruning, whenever the bound on true value (2 in absolute value) can be used to be certain that no score reached in a subtree makes a difference. Use of A-B pruning is also a good idea, but is optional.
You need at this point to implement your static heuristic evaluation function using several features, which will then be combined using weights into a final value. In addition, your evaluation function should provide an error measure on its quality of evaluation. For standardization purposes, the function should return values between -2 and 2 (the idea is that the function should return values that can be uses as if they were expected values of game score). The error measure should be approximately one standard deviation of score error, whenever this is meaningful. Thus, for a terminal position, the error should be 0. For other positions, the error should be something greater than 0.
The search depth should be varied according to computation time and evaluation confidence. In general, the search depth is shallow - no more than 2-ply. An option of an additional 2-ply should be used if the error estimate returned by the evaluation function is large compared to the difference from competing brances.
In order to better debug the agent and present its behaviour, we advise that you add to the environment simulator a capability of starting at a position different from the initial position, e.g. read from a file. In addition, reading an explicit random seed will allow you to make sure that the die scores do not change between runs. Also, you should include a debug option that writes out to a file some information about the search, including positions checked and the heuristic function values and error estimates.
The program and code sent to the grader, with documentation on the heuristic, including how error estimates are computed, to Mr. Ami Berler by e-mail or otherwise as specified by the grader, a printout of the code and results. Present a case where your program performs pruning, and a case when your program varied the search depth due to estimated heuristic error. Set up a time for frontal grading checking of the delivered assignment, in which both members of each team must demonstrate at least some familiarity with their program...
Deadline: November 25, 2002