Final

Strategy presentation in class May 14, 2004
Project demo due on June 4, 2004 2:00pm
Final report due 2:00pm June 10, 2004.


Figure 1. The Othello board at the start.

Summary:

You will devise strategies to play Othello (aka Reversi) and implement one of your strategies with two Xilinx XC4003E-PC84s, and an 8K-byte SRAM. Your design will interface with a ``host'' computer that will be responsible for keeping track of the game and making the White player's moves. The only information provided by the host computer will be the location of White's moves.

The Game

In Othello two players, Black and White, take turns placing black and white stones, respectively, on an 8 by 8 grid until neither player can place a stone. A stone may be placed in an empty location if there is at least one direction (N,NE,E,SE,S,SW,W, or NW) in which one or more of the opponent's consecutive stones will become bordered on both ends with your stones (after the move). Any stones that become surrounded as the result of the move will flip to the other color.

Figure 1 shows the 8 by 8 board at the start of the game. In Figure 1, Black can move in locations d3, f5, e6 or c4. Figure 2 shows the board after Black places a stone in location d3.


Figure 2. The Othello board after Black places stone in d3.

Figure 3(a) shows a later board; it is White's turn. White can place a stone in b4, b6, c3, d2, e2, or g3. Figure 3(b) shows the board after White places a stone in e2.


Figure 3. Before and after White moves at e2.

One important rule is that a player must move (place a stone) if there is a move available, regardless of how detrimental that move will be to the player. The winner is the player with the most stones on the board when no more moves by either player are possible.

Design of an Othello player

As your final project in cmpe126, you will design and debug a digital-Othello-player machine using two Xilinx XC4003E-PC84 and possibly an 8K-byte RAM.

To know and understand the game, several game sources are provided for trying out strategies.

The game environment


Figure 4. Interface between the PC and BORG player.

Your machine will interface to a host PC that presents White's moves one at a time as indicated in Figure 4. Here is the protocol. for the communication between the PC and Borg board. The host program (which I will provide) maintains the screen, either determines White's moves or gets them from the keyboard, and informs the Borg of White's moves, processes the Black moves it recieves from the Borg board, keeps track of the board and detects when the game is over, or a player makes an illegal move.

Your machine will be reset through the global reset mechanism (P10) when a new game is beginning. Your machine does not need to detect when the game is over, but otherwise must keep enough information to make its moves. The host PC will only be providing the White's moves.

Evaluation

There will be a tournament on June 4, 2004 in BE 150 (2:00-3:30pm). The quality of your design will be evaluated based on

  1. The score your machine gets against different levels of difficulty.
  2. The simplicity of your design versus the complexity of your strategy.
  3. The propagation delay along the critical path(s), in other words, the maximum clock rate of your design.
  4. The documentation of your design.

Your responsibilities

  1. Devise and test at least two basic strategies with a (behavioral) high-level simulation. To evaluate a strategy, code it in C and integrated into the source code that is supplied to you.

    Be prepared to present your strategy(ies) in the class on May 14.

    There is always the danger that the high-level language constructs in C are too powerful and may not be implemented efficiently or directly in hardware. Just keep in mind that your strategy has to be realized in two Xilinx FPGAs, eventually. Estimate the number of CLBs that is required by your strategy(ies).

  2. Realize your design with the BORG prototyping board.

  3. Submit a good quality final report documenting you strategy, design, schematic diagrams, timing diagrams, test plans, simulation results, design files .ncd and schematics, and your (logic synthesis) .eqn, .pla and .fsm files. Please place the design files on a floppy disk and submit this disk with your report.

Advice

When devising your strategy to solve this problem, keep the implementation constraints in mind. It is easy to come up with ``interesting'' strategies which are not easily implementable in hardware. Please start with a VERY simple strategy first, and estimate the hardware resources needed to realize it. You can improve the game strategy later on when you have a better understanding of the constraints and the game.

A successful project requires good planning, step by step documentation, and innovation. Procrastination leads to disaster. Start working on it now.

The CMPE126 Web:
Copyright 2004; Department of Computer Engineering, University of California, Santa Cruz.
martine@cse.ucsc.edu