By now, you should be dreaming pleasantly about lists in your sleep. Using them in C shouldn't be anything too new. But, it is important to try them out because people always make mistakes when first using C pointers and structures.
First we define the type of lists. This is mostly from class.
struct Cons {
int number;
Cons* next;
}
typedef Cons* List;
You haven't seen the typedef before, but it simply gives
a more mnemonic name to lists. List can be used anywhere
you would've otherwise used Cons*.
Write a recursive version of the length function in C. This should be very similar to the Scheme function you wrote at the beginning of the course.
Now, write a version of length using a for-loop and no recursion in C. (This is the version traditionally favored by C programmers, but you should feel equally comfortable with either version.) If you have any trouble, don't forget that you can take the intermediate step of writing an accumulator-style version.
Now write recursive and loop versions in C of the function reverse. As in Scheme, it should return a new list (of type List). Be sure to use new!
First, make sure your program meets the basic requirements before you go for the extra credit. It is fairly easy to make a program to play Connect 5, but it is much harder to make it play well.
Here's a tip to save you time. You could do the following, where there the italics are the computer typing:
unix% connect5 5 0 0 0 0 0 0 1 1 1 1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 unix%Or, you could put that board position into a file, say board1 and do the following:
unix% connect5 < board1 0 1 unix%This is called redirecting standard input from the file board1, as is part of what we'll do to run your program.
If you're programming this in C, you might want to use a typedef as introduced above. For example,
typedef int Board[20][20];defines Board to be the type of a 20-by-20 array of ints.
If you are simply given a board position, how can you figure out what move is best? The basic approach is to assume that you can give a numeric value to any board position. E.g., if the game is over and you have won, it should receive the best posible value, let's say 100. If the game is over and you have lost, it should receive the lowest possible value, let's say -100. A draw would be in the middle, or 0.
Can you come up with a way to assign a value for other board positions, when the game isn't done yet? This is the hard part.
One basic approach is to come up with some heuristics based on game strategy. E.g., for Connect 5, I might look at the number of 4-in-a-rows, 3-in-a-rows, and 2-in-a-rows I have and somehow add them up, and subtract the 4-in-a-rows, 3-in-a-rows, and 2-in-a-rows my opponent has. This valuing isn't necessarily 100% accurate, but it's easy to do. In my code, I would write a function that finds a move that maximizes the value. (I don't necessarily need a function that computes the value of the current board.) This should find any immediately winning move, and do a reasonable job otherwise.
Another basic approach just expands the previous one. In order to find out what move to make, I'll see what would happen if I made each of the possible moves. After I make a move, my opponent gets to move. After that, I can make a move, then my opponent, etc., until the game ends. This makes a (large) tree of game positions, with the children of a game position being all those obtained after a possible move.
I can easily assign values to these final won, lost, or drawn positions. Working backwards, I want to assign values to earlier positions, based on what happens later. If I'm forced to lose a move later, that's as bad as having lost. Along the way, I should always pick my best move, i.e., the one with the maximum value, whenever it is my turn. I should also assume that my opponent is just as smart and picking his best move, i.e., the one with the minimal value, whenever it is his turn.
Thinking ahead for the rest of the game is impractical except for very simple games. This is because there can be a large number of moves and board positions. In practice, I can only think ahead a few moves. This still generates a tree of moves and board positions, but one where the leaves are not necessarily finished games. Instead, I need to use a heuristic board evaluation routine to estimate the values of these positions.
You'll have a hard time searching more than 2 moves ahead in the time alotted. Compare to the 8+ moves that good human chess players look ahead or the 14+ moves that Deep Blue chess program looks ahead.
Start by thinking about strategies for playing the game. Try playing our sample programs to see what is good and bad about their strategies.
If you are going for the extra credit, you will quickly learn that a faster program is generally a better program. After you get your program to work, you should spend time to see how to make it faster and smarter.
Making your board evaluator smarter generally makes it slower. You look for more kinds of patterns to make more interesting distinctions. Making your game tree search smarter generally means making it search more of the tree. You can try to make the search faster so that you can look another move ahead. Or you can try to figure out what parts of the tree you don't even need to look at ("pruning" the tree) and what order to search the tree in.
In the recent past, the most of the better programs for this assignment haven't searched ahead at all. In the given time limits, your time is generally better spent on a good board evaluator.
Historical note: In the late 80's, Hitech (from Carnegie Mellon University) was generally the computer chess program to beat. It was designed by a former world champion of postal chess, and his goal was to make the program as smart as possible, both in board evaluation and searching. A rival program, Deep Thought (also from CMU; it later became Deep Blue at IBM) was started with an entirely different goal. Rather than being smart, Deep Thought was mainly fast so that it could look ahead more moves than any other program. As both programs improved, they traded top honors among all chess programs back and forth, with Deep Blue currently the clear winner.
While you should look at how to improve the algorithms in your program, there is one quick and easy way to speed up your program if it is written in C/C++. You should have the compiler "optimize" your program, e.g., using the -O flag. Look at the manual page, man g++ for lots of other options.