Mathematics Science Fair Project
Research combinatorial games using the game of Nim as an example


Projects by Grade Level
1st 2nd 3rd 4th 5th 6th
7th 8th 9th 10th 11th 12th
Home Advanced Award Winning Warning!
Project Information
Title: Study the basic theory of combinatorial games using the game of Nim as an example
Subject: Mathematics
Subcategory: Game Theory
Grade level: High school - grades 10-12
Academic Level: Ordinary
Project Type: Descriptive
Cost: Low
Awards: First Place, Canada Wide Virtual Science Fair ($100)
Affiliation: Canada Wide Virtual Science Fair
Description: Main topics: Introduction of the theory of combinatorial games and a variant of the game of Nim; Chocolate problems: inequalities, floor function, ceiling function; the graphs of the variants of Nim; varieties of graphs produced by games with various kinds of inequalities; chocolates with very strange properties.
Links:
www.virtualsciencefair.org
www.virtualsciencefair.org
www.virtualsciencefair.org

Background

Combinatorial Game Theory

Combinatorial game theory (CGT) is a mathematical theory that studies two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT does not study games of chance (like poker). It restricts itself to games whose position is public to both players, and in which the set of available moves is also public (see perfect information). CGT principles can be applied to games like chess, checkers, Go, Arimaa, Hex, and Connect6 but these games are mostly too complicated to allow complete analysis (although the theory has had some recent successes in analyzing Go endgames).

Applying CGT to a position attempts to determine the optimum sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process is torturously difficult unless the game is very simple.

Nim

Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.

Nim has been mathematically solved for any number of initial heaps and objects; that is, there is an easily calculated way to determine which player will win and what winning moves are open to that player. In a game that starts with heaps of 3, 4, and 5, the first player will win with optimal play, whether the misère or normal play convention is followed.

The key to the theory of the game is the binary digital sum of the heap sizes, that is, the sum (in binary) neglecting all carries from one digit to another. This operation is also known as "exclusive or" (xor) or "vector addition over GF(2)". Within combinatorial game theory it is usually called the nim-sum, as will be done here. The nim-sum of x and y is written x ⊕ y to distinguish it from the ordinary sum, x + y.

See also:
Combinatorial Game Theory
Nim

Source: Wikipedia (All text is available under the terms of the Creative Commons Attribution-ShareAlike License)

Useful Links
Science Fair Projects Resources
Citation Guides, Style Manuals, Reference
General Safety Resources
Electrical Safety FAQ
Mathematics Science Fair Projects

Mathematics Award Winning Projects

Mathematics Encyclopedia


Projects Home
Primary School
Elementary School
Middle School
High School
Advanced
Easy Projects
Award Winning
Popular Ideas
Branches of Science
Experiments

Science Fair Project Guide
Home
Science Fair Project Types
The Scientific Method - How to Experiment
The Display Board
Topics, Ideas, Sample Projects

Repeat Famous Experiments and Inventions
Science Jokes Science Trivia
Scientists & Inventors

Read for Free
The Science Fair
A Juvenile Science Adventure Novel
by Julian T. Rubin

Human Abridged Wikipedia Articles



My Dog Kelly

Follow Us On:
     

Privacy Policy - Site Map - About Us - Letters to the Editor

Comments and inquiries:
webmaster@julianTrubin.com


Last updated: January 2018
Copyright © 2003-2018 Julian Rubin