CSCI 3202 PS 2;

Problem 2.1 (35 points) SIM game

Write a program to play the game of SIM with eight points (labeled A-H). Again, the two

players are RED and BLUE; you can assume that RED moves first by convention; each

player alternately chooses an edge to “claim” for the given color; and the loser is the player

who is forced to create a complete triangle of edges in their own color. Your program

should play interactively against the user. It needn’t involve any fancy graphics or interface,

but it should play a decent and competitive game of SIM. The interaction could be entirely

textual, and could look something like this:

Are you playing Red? (Y/N): Y

RED move: A, B

BLUE move: E, G

etc.

Some notes: you might want to use alpha-beta pruning (it’ll come in handy for the next

problem anyway). In any event, whatever algorithmic strategy you use for your program,

you should explain and document your approach. Since the computer program will

probably not display the current state of the game (though of course it could), you may

want to play against the program with a paper-and-colored-pencil representation of the

game board handy. You should submit the important source code for your program (i.e.,

the major procedures for deciding on a next move) and a sample game or two to show how

it plays the game

Problem 2.2 (15 points) Alpha-Beta Pruning

Construct a tree with a branching factor of 3 at each level, and 81 leaves. This tree will

represent two complete MAX-MIN pairs of moves. The top level of the tree is MAX; the next

level (3 nodes) is MIN; the third level (9 nodes) is MAX; the fourth (27) is MIN; and the fifth

(81 nodes) are the leaves of the tree, labeled with the following numbers, grouped in sets of

27, and reading from left to right:

8 3 7 2 5 9 5 3 8 2 5 7 9 4 8 6 3 2 4 9 5 1 7 2 2 4 6

1 4 7 8 4 2 5 7 8 2 4 6 9 5 6 1 0 2 4 5 3 9 2 7 3 1 7

9 5 6 4 0 1 3 4 5 1 2 3 7 3 4 4 3 2 8 2 7 1 9 3 2 7 3

As usual, MAX is trying to achieve the highest number; MIN the lowest.

(a) What is the overall value of this tree to MAX?

(b) How many of these leaves 81 leaves actually have to be evaluated by an alpha-beta

game search algorithm assuming that possible moves are examined from left to right?

(c) How many leaves have to be evaluated by alpha-beta assuming that moves

are examined from right to left?

(d) Suppose the root player is MIN. (That is, the levels of the tree are now MIN, MAX, MIN,

and MAX.) Now how many of the 81 leaves have to be evaluated by an alpha-beta searcher

if moves are examined from left to right?

Problem 3. (20 points) 4×4 Sudoku

Suppose, instead of the regular (9×9) Sudoku game, we make a much simpler 4×4 version.

In this version, each square contains the number 1, 2, 3, or 4; a square only contains one

number; each of the four rows contains the values 1, 2, 3, 4; each of the columns contains 1,

2, 3, 4; and each two-by-two block (upper left, upper right, lower left, lower right) likewise

contains 1, 2, 3, 4. The rows are counted from the top (i.e., the top row is row number 1),

and the columns are counted from the left.

3a. (2 points) Here’s a 4×4 Sudoku puzzle for you to solve “by hand”:

3b. (18 points) Let’s approach this puzzle using propositional logic. Let the sentence

variable “Sxyz” stand for the sentence “The Square in row x, column y, has contents z.”

Thus, there are 64 sentences whose truth value we are interested in:

S111 (“Row 1 Column 1 contains 1”)

S112 (“Row 1 Column 1 contains 2”)

S113 (“Row 1 Column 1 contains 3”)

S114 (“Row 1 Column 1 contains 4”)

S121 (“Row 1 Column 2 contains 1”)

…

S444 (“Row 4 Column 4 contains 4”)

In the sample puzzle above, then, as it happens S144 is true, S111 is true, and S113 is false.

Representing this puzzle in propositional logic means that we have to state many of the

constraints of the puzzle in the appropriate form. For example, to represent the idea that

the square in row 1 column 1 contains a number, we could write:

S111 OR S112 OR S113 OR S114

We need more than this, however. Since the square can only contain a single number, we

need statements like:

NOT(S111 AND S112)

NOT (S111 AND S113)

and so forth.

Your job is as follows:

(a) Write the necessary statements of propositional logic to ensure that there is exactly one

“3” in the fourth column of the puzzle.

(b) Write the necessary statements of propositional logic to derive the placement of a “3” in

row 3, column 4; these statements should include starting constraints of the puzzle (e.g.,

“S144”, “S242”, and so on) and rules like the one you wrote in part (i) above. Finally, show

how you can use resolution, along with those statements, to derive the truth of S343.

Problem 4 (30 points) Mastermind

In this problem, you will write a program to play as the “code-guesser” in the game of

Masetermind. For simplicity, this game of Mastermind has four colors (not six, as usual)

and three positions (not four, as usual). The colors are Red, Blue, Orange, and White. This

means that there are only 64 possible codes.

Your program should allow you (as user) to think of a “secret” code. The program will then

make successive guesses at the code, and you answer with X and O responses as in the

standard MasterMind game. The program should simply keep track of the current set of

“open” guesses consistent with the answers so far; you can then decide how the next guess

can be selected. When the game starts, the program has 64 “open” possibilities; each

answered guess should narrow the possibilities.

Here’s an example. Suppose you think of the code: R R W. The program might begin by

asking:

B B O Your answer: nothing (no X’s or O’s)

The program now has limited the set of open codes to a total of eight (the ones that involve

only R and W). The program might next ask:

R W W Your answer: XX

The program now has three remaining possibilities (WWW, RRW, and RWR). The program

might now guess:

WWW Your answer: X

The program now has only one remaining possibility (RRW), so it guesses that, and it’s

done.

Show your program at work for an example code.

This strategy is a small example of what in machine learning is referred to as “candidate

elimination”: as we get more information, we can eliminate hypotheses that are

incompatible with the information that we’ve received so far. Would this strategy work for

a large-scale Mastermind game with (say) 30 colors and (say) 25 positions?

# CSCI 3202 PS 2

$30.00

CSCI 3202 PS 2;

Problem 2.1 (35 points) SIM game

Write a program to play the game of SIM with eight points (labeled A-H). Again, the two

players are RED and BLUE; you can assume that RED moves first by convention; each

player alternately chooses an edge to “claim” for the given color; and the loser is the player

who is forced to create a complete triangle of edges in their own color. Your program

should play interactively against the user. It needn’t involve any fancy graphics or interface,

but it should play a decent and competitive game of SIM. The interaction could be entirely

textual, and could look something like this: