CSCI1300 Notes 10: Game AI

Now that you have a program that can manage a FactorBlocks game, you need to design a program that can choose good moves. This design will form the basis of your tournament entry, as described in more detail in Notes 11.

Your first task for these notes is to form a team of three or four students who will work together on your tournament entry. Choose a name for your team, and choose a captain.

Here are some ideas to guide you in developing a design, starting with a very simple idea and moving up in capability.

** Choose any old legal move.** You can't propose just any move,
because you'll lose in the tournament if your program proposes an illegal move.
But if you come up with a way to check if a move is legal, you can come up with
a move, check to see if it's legal, and try another one if it's not legal.

** Choose a winning
move if there is one.** First, come up with a way to try
out a move. That is, given a gamestate and a move,
design a function that gives you the new gamestate.
Then come up with a way to determine if a given gamestate
is one in which you have won (that is, there are 4 of your markers in a
square.) Then come up with a way to test each legal move to see if it's a
winning move, and choose that move if you find one.

** Choose a move that doesn't let your opponent win, if there is one.**
This uses some of the same machinery as the previous approach. Pick a move
(call it m), try it out to get a new gamestate, then check all of your

** Choose a move that leads to a gamestate that
looks good.** Devise a way to

** Tree search.** Most AI
approaches to game play use this approach, in which your program tries to
analyze the possible moves, the responses its opponent could make, its
responses to those, and so on. If you make a diagram of all of your moves, the
responses to them, the responses to the responses, and so on, you get a
branching structure called a

(a) Suppose you have a way of representing collections of moves, for example an array of moves that has room for 24 moves (the max possible) packaged in a struct with a count that indicates how many moves are actually filled in in the array.

(b) Design a function that is given a gamestate and returns the collection of legal moves.

(c) Design a function that is given a gamestate and a legal move and returns the new gamestate that results when the move is made (you need this for some of the approaches above, anyway.)

(d) Design a function value() that
returns a score when given a gamestate. The score
represents how good the gamestate is ** for
the player that has just played**. It calculates the score as follows. If
the player who has just played has four in a square, the program returns 100.
Otherwise, get the collection of legal moves (which will be moves for the
opponent.) If there are no legal moves, return 0 as the score. If there are
some moves, for each of them , find the gamestate that results from playing it, and use value() to
calculate the score for that gamestate. Find the
maximum of these values. Return the

**Note** that the
function value() will call itself. This is perfectly
legal. Functions that call themselves are called ** recursive**.

(e) Have your makemove() function choose its move as follows. Generate all the legal moves. For each, find the gamestate that results, and use value() to calculate the score for that gamestate. Choose the move that gives the maximum score.

(f) The program as described performs an ** exhaustive
search** of the game tree. That is, it explores

(g) When you actually try out your function, you may find
that your program wins, but wastes time along the way on moves that do no harm
but don't do any good, either. If so, you can try using the depth idea to ** discount**
the scores of wins that are farther in the future. That is, rather than
returning 100 for a win, value() returns 100*pow(.9,depth), so that the deeper into the search the win
is, the less valuable it is rated.

** An approach of your own.** You
can come up with your own approach to choosing rules; you do not have to use
one of these. Just be sure it doesn't come up with illegal moves!

What
to turn in.

Spend your time on this assignment emphasizing ** design**,
not code. Discuss with your teammates what approach you are going to use. You
may want to develop designs or partial designs for more than one approach, and
then make a choice.

Whatever approach you choose, try to develop your design
well enough that coding will be almost trivial. That is, for any piece of your
design, such as checking to see if a move is legal, you should understand ** how**
you are going to do it.

Turn in a diagram or outline that shows your design. You may find that it's clearer to use multiple outlines or diagrams, where one diagram or outline shows how big pieces fit together, and other diagrams or outlines zoom in and show the structure of the big pieces, rather than trying to fit the whole design into one diagram or outline. For example, one diagram or outline may use a piece called "check legality of move", and another diagram or outline will describe how you are going to do the check.

** Important: **Your diagram or
outline must include the name of your team, the names of the students on the
team, and the name of the captain.

If you have time, work out what functions you are going to have in your implementation, and what their headers are (what the function is named, what, if anything, it returns, what parameters it needs.) Turn in a list of these. You'll find working this out will help greatly when the time comes to write the code, in part because you know enough to write the calls to any functions that you use.

** Note:** if you use outline form,
or you draw diagrams on the computer, each team member must turn in his or her
own outline, electronically as for other homework (including time report). If
you use diagrams drawn on paper, you'll turn it in in
class as hardcopy. But each team member MUST also turn in an individual email
report, including time report, which refers to the diagram. The paper diagram
must have the names of all team members on it when it is submitted, as
mentioned above.