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 of integers as in lecture:
// type definition
struct Cons {
int first;
Cons* rest;
};
// constructor definition
Cons* cons(int first, Cons* rest)
{
Cons* newcons = new Cons;
newcons->first = first;
newcons->rest = rest;
return newcons;
}
Don't forget the semicolon ending the type definition!
To do: 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.
To do: 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.
To do: Now write recursive and loop versions in C of the function reverse. As in Scheme, it should return a new list. Be sure to use new! As a reminder, here's ane Scheme version:
(define reverse-accum
(lambda (l accum)
(cond [(empty? l) accum]
[else (reverse-accum (rest l) (cons (first l) accum))])))
(define reverse
(lambda (l)
(reverse-accum l empty)))
What if I wanted other kinds of lists. Well, then C gets annoying. The most straightforward thing to do is use definitions like the above for each kind of list you want. E.g.,
// definitions for lists of integers
struct Cons_int {
int first;
Cons_int* rest;
};
Cons_int* cons_int(int first, Cons_int* rest)
{
Cons_int* newcons = new Cons;
newcons->first = first;
newcons->rest = rest;
return newcons;
}
// definitions for lists of lists of integers
struct Cons_Cons_int {
Cons_int* first;
Cons_Cons_int* rest;
};
Cons_Cons_int* cons_cons_int(Cons_int* first, Cons_Cons_int* rest)
{
Cons_Cons_int* newcons = new Cons;
newcons->first = first;
newcons->rest = rest;
return newcons;
}
Similarly, you define a version of whatever other function you need,
such as "reverse", for each kind of list.
For the curious: You might add the line
typedef Cons* List;after the definition of Cons. typedef simply defines a more mnemonic name for this type. List can then be used anywhere you used Cons*.
For the curious: There is a way to avoid code duplication when you have multiple kinds of lists. Make each element of the list be in a "union" type. E.g., make a type whose members are either an int or a Cons_int*:
enum whichkind = {is_int,is_cons};
struct List_Element {
whichkind kind;
union {
int the_int;
Cons_int* the_cons;
} data;
};
struct Cons {
List_Element first;
Cons* rest;
};
If first is a Int_or_Cons_int,
you can test if it's an int by checking
first.kind == is_int. If it is, get the integer with
first.data.the_int.
An important drawback is that the compiler can no longer verify that
a particular list contains only integers.
For the overly curious: Rather than using a union type, many typical C programmers "cheat" the type system with "type casts" to syntactically simplify such code. But, this cheat is very error prone, and it reduces the helpfulness of type checking.
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, weighting the 4-in-a-rows most heavily. 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/her best move, i.e., the one with the minimal value, whenever it is his/her turn.
Thinking ahead for the rest of the game is impractical except for very simple games (like tic-tac-toe). This is because there can be a very 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 (to maximize pruning).
In the recent past, 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; the predecessor of Deep Blue from 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.