Paper Authors

Abstract

NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Session 1793

Designing a Computer to Play Nim: A Mini-Capstone Project in Digital Design I John Greco, Ph.D. Department of Electrical and Computer Engineering Lafayette College Easton, PA 18042

Abstract 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.

Introduction The game of Nim 1–8 is an ancient game whose playing area consists of several stacks of pieces. In the original design of the game, there is no restriction on the number of stacks, nor is there any restriction on the number of pieces in each stack. Two players alternately remove pieces from the field, removing any number of pieces on each turn, but removing pieces from only one stack. Traditionally, the person removing the last piece loses the game.

Proceedings of the 2004 American Society for Engineering Education Annual Conference & Exposition Copyright ©2004, American Society for Engineering Education

• Citation

• Format
  • APA
  • APA - LaTeX bibitem
  • MLA
  • MLA - LaTeX bibitem
  • Bibtex
  • EndNote - RIS

Greco, J. (2004, June), Designing A Computer To Play Nim: A Mini Capstone Project In Digital Design I Paper presented at 2004 Annual Conference, Salt Lake City, Utah. 10.18260/1-2--14039