Category Archives: Game Theory

Parity NIM

Parity NIM consists of a pile containing an odd number of objects from which players take turns removing one or more objects, with at most \(k\) objects removed by each player during his or her turn. The player who has removed an odd number of objects at the end of the game wins.  If \(n\) is the number of objects in the initial pile, a specific solution for the pair \((n,k)\) can be found.   However, no general solution is known.

Hexagonal Chess

Hexagonal Chess is a modification of the traditional game of chess, played on a hexagonal board. A board is defined as an n-board if the board has n hexagons on the bottom row of the board.  All boards we used for this game are regular hexagonal boards. This means that the board has the same number of hexagons on every side.  At right is an example of a 5-board.

What is the minimum number of bishops (knights, kings, queen, etc) can be placed on the board so that all sites are challenged (the board is dominated)?  What is the maximum number of bishops (knights, kings, queen, etc) that can be placed on the board so that no bishop is able to capture another (all are independent).

graph1

Three Player Nim

In the game of Nim, several piles of sticks are placed on a table.  Two players take turns removing sticks from the piles. On each turn, a player must remove at least one stick, and may remove any number of sticks provided they all come from the same piles.  The first player without a stick to remove loses.  We will consider 3-player Nim.  Three players, A, B, and C, rotate turns in playing Nim.  The first player without a move loses. The goal for each player is, naturally, to avoid losing and each would prefer to make the last move, if possible.  Develop a theory of 3-person Nim and generalize your results.

Chomp the Graph

Given a finite undirected graph \(G\), players alternate turns and remove either a single edge or a vertex with all incident edges.  Whoever removes the last vertex, leaving their opponent with the empty graph, wins.   Which player has a winning strategy for games on trees, forests, cycle graphs, complete graphs, etc?

diagram