Designing A Computer To Play Nim: A Mini Capstone Project In Digital Design I

This paper describes a design project suitable for inclusion in an introductory course in digital circuit design. The project is the design and realization of a special-purpose computer to play the game of Nim, an ancient game involving the removal of pieces from stacks. Two players alternate turns, and each turn consists of removing any number of pieces from any one stack. The person taking the last piece is the winner (although the more common rules state 'last piece loses,' our rules slightly simplify the required algorithm). The rules of Nim are easily understood, and the game has an underlying strategy that is well suited for description using logic expressions. Realization of the computer requires the application of various topics in combinational and sequential circuit design, topics that are presented in the course. The computer sub-circuits include: a 3-bit counter; a decoder circuit; combinational logic to determine the computer's move; a finite state machine to realize the computer's move. Using a Field Programmable Logic Array (FPGA), the entire computer is realized using one integrated circuit chip, which is configured via a development system. An additional input-output board provides the user input-output needed for playing against the computer. Using FPGA design entry and routing software, students develop the computer design during several weeks of laboratory time. The project exposes students to a meaningful, practical application of the course material, and the opportunity to use modern digital design software and hardware tools. The project also requires students to devise the winning strategy for the game; they do this by collecting and analyzing data taken during several games played against a computer. Although students are heavily guided in their designs, there are many enhancements to the computer, which students can propose and implement. The project also introduces students to the concept of the data path/controller architecture commonly used for a digital system, including a general-purpose computer.