Comp 210 Lab 13: Connect5, Lists in C

Connect5

How to leave your program for grading

If we can't find and run your program, it might not be graded, so be sure to do the following!

If you are writing a Scheme program, it should be in the file /home/youruserid/comp210/final/connect5.ss. Otherwise, the compiled version of your program should be in the file /home/youruserid/comp210/final/connect5.

If you are not writing a Scheme program, and thus you need to compile it, be sure to compile it using one of the machines in Ryon. We will be running it on those machines, so you need to make sure it runs on them. (It's sufficient to compile it on any Solaris machine, e.g., ural, but not a SunOS machine, e.g., great-horned, and not your home PC/Mac.)

The last lab gave incorrect instructions for protecting your work directory. You should set it so that we can test your final project: chmod 750 comp210, chmod 750 comp210/final, chmod 750 comp210/final/connect5.

Testing

As you are writing the program, test the pieces individually. When you appear to have a working program, test it on some sample board positions. We have provided a few samples for you to try. For a Scheme program, you can type, e.g.,

mzscheme -l macro.ss -q -m -r connect5.ss < ~comp210/Projects/Connect5/Tests/noChoice

(This is how we will run it. For an explanation of these flags, type mzscheme -h.) For a compiled C program, you can type, e.g.,

connect5 < ~comp210/Projects/Connect5/Tests/noChoice

Be sure to try it on more than just our samples.

Using the referee

Even if you're not trying for extra credit, you should test your program using the "referee" that we've provided. Your program may lose most of the time, but it should be able to play.

We've provided a text-based and a graphics-based referee. Let's try the graphical one.

To start the referee, type ~comp210/Projects/Connect5/bin/conn5-gui.
Now give it a size for the board, as asked.
Now give it how much time per move it allowed, as asked. When working to make your program play well, you should allow 15 seconds, as we will use in the tournament. But for initial testing, you may want to allow more time.
Now give it the two opponents to play. As an example, try /home/comp210/Projects/Connect5/Players/first.ss (a very stupid player) and /home/comp210/Projects/Connect5/Players/phool (one of last year's winners).
Note that we did not type ~comp210/.... The referee does not know about the tilde (~) or other UNIX shell shortcuts (e.g., pattern matching with wildcards). You can use paths relative to your current directory, though.
Now sit back. It will launch a window that draws the game as it is played.

To use the textual referee, follow the same instructions, except starting with ~comp210/Projects/Connect5/bin/conn5-text.

You can also provide the game parameters as command line arguments. Type ~comp210/Projects/Connect5/bin/conn5-text -help, and it will tell you how.

The text referee is quicker (you don't have to wait for a window to appear) and tells you how quickly moves are made. The graphical referee is easier to follow and may give you a better understanding of the strategies used by the players.

Hints for making your program smarter

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.

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. As both programs improved, they traded 1st and 2nd place 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 not written in Scheme). 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.

Lists in C

Here's a brief discussion of lists in C. They will be discussed in more detail in class. Also for more detail, especially on how to write code, see last year's lab on lists in C. You'll first need to look at how to define pairs of things. For this, we use structures, as explained in last year's lab on C structures

In class we discussed the basic problem of using vectors to represent lists. If we have a list

(define a (list 3 3 3))

and we make two new lists using that one

(define b (cons 1 a))
(define c (cons 2 a))

we need to somehow store both a 1 and a 2 "before" the rest of the elements, because we can use any of these lists. By themselves, vectors only allow one element to be before the rest.

What we need if for each list element to point to the next element in the list. Then in the previous example, both the first element of list b and the first element of list c point to the first element of list a.

    b: 1
       |
       V
    a: 3 -> 3 -> 3
       ^
       |
    c: 2

The last element of a list doesn't point to anything.

How would we represent this in memory? We store things in pairs: a list element and a pointer to the next list element. Since we use pointers to get the next element, they don't have to be in order or contiguous. Here's one possibility:

label	memory cell	contents	explanation
a	500	3	0th element of a
	501	502	pointer to 1st element of a
	502	3	1st element of a
	503	506	pointer to 2nd element of a
b	504	1	0th element of b
	505	500	pointer to 1st element of b
	600	3	2nd element of a
	601	0	no pointer
c	700	2	0th element of c
	701	500	pointer to 1st element of c

A list is then just a pointer to one of these cons-cells. An empty list is a "null" pointer. (In a real computer, by convention, a null pointer is the address 0 since the low-end of memory is special and not used for a user's program.)

Let's look at the equivalent of Scheme's basic list operations:

(cons a l): We allocate a contiguous pair of cells. In the first, we put the value of a. In the second, we put the value of list b, which is a pointer. We return a pointer to the first cell of the pair.
null: We return the null pointer.
(car l), (cdr l): We follow the pointer that is the value of list l to a pair of cells. We return the contents of the first or second cell, respectively.
(set-car! l a), (set-cdr! l l'): We follow the pointer that is the value of list l to a pair of cells. We change the contents of the first or second cell, respectively, to contain the other value provided.

Observe that using set-car! to change the car of a also changes elements in b and c. We've seen this kind of behavior before with vectors/arrays.

`shared`

In the missionaries and cannibals assignment, you probably saw some lists printed using shared. We now know enough to explain why. Using our previous example, try

(define a (list 3 3 3))
(define b (cons 1 a))
(define c (cons 2 a))
(list b c)

This will return (at the appropriate language level)

(shared ((-1- (list 3 3 3)))
   (list (cons 1 -1-)
         (cons 2 -1-)))

I.e., it shows that part of the list is shared. To read this code, consider shared to be essentially like local.

Circular lists

Let's try using set-cdr!. What are the results of (set-cdr! a b) or (set-cdr! a a).

Circular lists are occasionally useful, but can be annoying. Try finding the length of one!