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 opponent's moves from that gamestate. If any of them leads to a win for the opponent, don't pick m. Keep going until you find a move m that doesn't let your opponent win. If you try all the legal moves, and they all let your opponent win, you're hosed, and you can choose any move (they're all equally bad.)

Choose a move that leads to a gamestate that looks good. Devise a way to rate gamestates by assigning a number in such a way that gamestates that look good for you get higher numbers, and gamestates that look bad for you get lower numbers. For example, you could add a point to the rating of a gamestate for every group of three of your markers in a square, and subtract a point for every group of three of your opponent's markers in a square. Assign 100 points if there are four of your markers in a square (that is, if the gamestate is one in which you've won.) Then run through all the moves, try them out, rate the resulting gamestates, and choose the move that leads to the highest rated gamestate.

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 tree. You search through this tree looking for a move that wins, or that at least avoids losing. Here is a sketch of how you might approach this.

(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 negative of this maximum as the score.

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 all possible sequences of plays. You may worry that there isn't enough memory to do this, or that it will take longer to make a move than you have patience for. If so, modify your value() function so that it uses a second argument to keep track of how deep it is searching. That is, when you first call it, pass 0 as this argument, and when it calls itself have it add one to the argument is was called with. Impose a cutoff, so that when it is called with depth argument (say) 4, it does not call itself to find the score, but rather tries to estimate the score by looking at the current position. For example, it might add points for 3 of its own pieces in a square, and subtract points for 3 of its opponent's pieces in a square.

(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.