Computer Science 237
Computer Organization

Williams College
Fall 2006

Lab 2: The Palm Development Environment
Due: Monday, September 25, 2006 at 9:00 AM

Lab meets this week in TCL 312. We will begin promptly at 1:10 PM.

The purpose of this week's lab is to become familiar with the GNU prc-tools development system for Palm handhelds. This environment consists of several compilers (C, C++, etc.), an assembler, a Palm emulator, and proprietary ROM's and development kits. To get you started with all of this, you will be putting the finishing touches on an implementation of the game "Quarto." This handout describes the game and what you need to do to finish it; the tools will be discussed in lab.


A Quarto board during play.

Quarto is a game that centers around 16 distinguishable playing pieces, each of which has 4 features. In the actual game, the pieces have color (dark or light), height (short or tall), outer shape (round or square), and inner shape (solid or hollow). Each physical piece is different from every other piece in at least one feature. We might imagine that the pieces are the 16 4-bit unsigned integers between 0 and 15, and that each of these integers differs from the others in one or more bit positions.

The play of the game rotates, usually between two players. A turn consists of placing a piece on a 4×4 board in an empty square. Once placed, the piece is never moved. The goal is to be the player who first gets a row, column, or diagonal of pieces that share some characteristic. For example, you may finish a diagonal with a piece that has the same 4's bit as all the three others. The important principle to remember (and to get over) is that no one "owns" any board pieces; pieces you play can work for you this turn, and be used against you by your opponent.

In our games we'll also add the rule that you win if you place a piece that finishes a 2×2 square of similar pieces. In particular, the square can wrap around the boundaries of the board. (Aside: is it possible for a game to be winnerless?) This cries out % 4, but that's not easy! How can you "mod" by 4 with more efficient operations?

The implemenation for most of the game is provided. Your task is to write one C function, 

    extern Boolean win();

that considers a board and decides if it represents a winning state.

(The Palm environment defines boolean, true, false, and UInt8--an unsigned byte.) The win method returns true if four pieces appear in a winning position, and false otherwise. You will make use of one (silly) method: 

   extern UInt8 get(UInt8 row, UInt8 col);

This method returns the piece stored at the indicated board position (0 <= row,col < 4). The piece is encoded as a small integer. If the board square is empty, the value is zero. If the board square is a valid piece, the 16's bit is set, and the low 4 bits are the small integer representing the piece. Each bit of the integer is consistently mapped to a feature of the piece.

When you identify four squares that are proof of a win, you should call 

   extern void highlight(UInt8 row, UInt8 col);

on each of the squares that make up the winning combination. This suggests to the players (who may be surprised), how the win occurred.

You may retrieve your startup kit from the CS 237 shared area on the FreeBSD systems in the file quarto1.tar.gz. You will learn about the contents of this kit and what to do with them during the lab meeting.

Your program will be graded on correctness, efficiency and documentation. To make things efficient, and to help you with next week's lab, you should not write any helper functions (even though you may be tempted).

When you've finished, submit only the file win.c using turnin on the CSLab FreeBSD systems.