Due in stages:
Overview
In this problem set, you and a partner will implement an alpha-beta game playing program for Abalone. In addition, you have several written questions to do by yourself. Both are important, but don’t neglect the written problems since the time-per-point is likely rather less than for the programming part. Note the three turning times.
Please see the class policy on lateness and collaboration.
In all problems below, please think carefully before answering questions – strive for a terse, precise explanation. Points may be taken off for overly long or complex explanations. If it is impossible answer a question with the information given, feel free to make additional assumptions (just state them clearly).
1. [22 points] In this problem you are asked to implement a
complete game playing program. We ask
that you do it in teams of two. Note
that parts of this problem are due before the final due date for this
assignment (see above).
The game: Abalone
is a two-person, turn taking, deterministic game of perfect information, i.e. an ideal target for the game
playing algorithms we have covered in class.
The rules of the game can be found at:
http://en.wikipedia.org/wiki/Abalone_game
In order to reduce the branching factor to a manageable
number, we disallow broadside moves for the purposes of this
assignment. Note that the above web page
describes a notation for reporting board positions and moves -- please use it
when you display the board and when you enter or report moves.
You can practice playing the game at: http://www.clickhere.nl/abalone/ This implementation also does not allow
broadside moves.
What to turn in at projects end (5/3 - extended!):
a) [1
point] Only one copy of the solution to this problem needs to be turned in per
team. Make sure that both of you contribute
equally; in your write up, explain how you divided the work.
b) [3
points] Describe and motivate your choice of the static evaluation function
c) [3
points] Propose and motivate (but do not implement) two distinct techniques
that could improve the performance of your program
d) [15
points for ideas, code quality, comments and program functionality and performance]
Write the complete program (in Java) implementing the alpha-beta pruning
algorithm that allows a human to play against the computer; turn in a tree-friendly printout
of the essential components of your program (files containing the data representation, the successor function, the goal test, the static evaluation function and the alpha-beta algorithm but not the GUI, the intereaction with the user, etc)
and also a soft copy of the entire code base (instructions for turning in your code have been posted on
the class web site).
e) (Extra Credit) Implement one of the techniques proposed in part c)
f)
(Extra Credit) Compare the performance of your program
with and without part e)’s improvement. Ideally turn in a table or graph.
2. [3 points] Precisely
formulate the following as a constraint-satisfaction problem: Majoring in CS: Assume
that it is easy to pass the bloody courses, the only challenge is taking them
all in a limited amount of time, given prerequisite chains and distributional
requirements. No need to list every constraint explicitly, just describe a few
at a high level (e.g. prereq chains and what else?).
3. (corrected numbering) [2 points each] R&N
7.8 a, b, and g
4 (corrected numbering). If Fred is rich,
he is happy. But if he’s not rich, then he’s an unhappy liar. If Fred is either
happy or a liar, then he is funny. Fred smells bad when he’s funny. Using propositional logic, can you prove that
Fred is rich or smelly? Provide either a
proof or a succinct argument explaining why no such proof exists.
a) [2
points] Rich
b) [2
points] Smelly
5 (corrected numbering). Using a consistent vocabulary (which you define clearly
with a sentence per predicate, for example “P(x) means that x is a politician”)
encode sentences b, d, and f below in first-order predicate calculus:
a) [1
point] What vocabulary will you use for b?
b) [3 points] Politicians can fool
some of the people all the time, and all of the people some of the time, but
they can’t fool all of the people all of the time.
c) [1
point] What vocabulary will you use for d?
d) [3
points] Some students took AI in Spring 2004.
e) [1
point] What vocabulary will you use for e?
f) [3
points] The best score in AI is always higher than the best score in Operating
Systems.
Computer Science & Engineering
Department
University of Washington
Seattle, WA