Math Exam

No Chance

no randomness involved, all strategy

Perfect information

both players have the same information

Normal play

win if you make the last move

misere play

win if your opponent makes the last move

Impartial

all pieces can be moved by either player

Partisan

each player has their own pieces

Symmetric

all spaces can be played on by either player

Solved

has been proven who has the winning strategy

Charles Bouton

Coined the name Nim, developed winning strategy

Piet Hein

Invented TacTix

John Nash

Popularized/rediscovered Hex at Princeton.

John Conway

Invented Sprouts, introduced theory of partisan games, published a book with the construction of surreal numbers

Michael Paterson

Invented sprouts

Elwyn Berlekamp

Introduced theory of partisan games, created Go

Richard Guy

Introduced the theory of partisan games

Francois Lucas

created Dots and Boxes. invented tower of hanoi puzzle

Ralph Gasser

Used computer program to prove perfect play in Nine Men’s Morris ends in tie

Louis Allis

Proved that 1st player has winning strategy in gomoku using computer search

Satoshi Hasegawa

reinveted Othello in 1971, published books on Othello strategies

Hiroki Takizawa

weakly solved 8×8 Othello board as draw with perfect play

Safe Position

if position left by a player after a move guarantees a win for the player

Unsafe position

position after a move does not guarantee a win, any unsafe can be made safe

Strategy stealing

Second player never has a guaranteed winning strategy, used to prove winning strategy

Brouwer’s Fixed Point Theorem

have to have fixed point, no matter how you move it one point stays the same

How does Brouwer’s Fixed Point Theorem relate to Hex

proves Hex can never end in draw

Sprague-Grundy Theorem

every impartial game under normal play is equal to a number, created cgt

Combinatorial game theory

studies strategies & math of perfect information, no chance games

Surreal numbers

real numbers, infinite and infinitesimal numbers, used to study cgt

Retrograde Analysis

starting from the end/working backwards to find the strategy to a game

Tree diagrams

show all possible outcomes

Brute force

check everything computationally, very ineffective

Strategies in Othello

get corners

Opening rules

rules that limit the 1st players chance to win, in the beginning

What games have opening rules

Go

Tangram puzzles

7 pieces arranged to replicate puzzle pattern using all pieces with no overlap

How many tangram convex patterns can be formed?

13

Nim

no chance, perfect information, impartial, normal play, solved

Who has the winning strategy in nim

depends on size of piles

Where, when, and who for Nim

China, 1901, Charles Bouton solved the game

Winning strategy for Nim

balance binary representation

TacTix

no chance, perfect information, impartial, normal play, solved

Who has winning strategy in tactix

even board 2nd player, odd board 1st player

Where, when, who for tactix

Denmark, 1950, Piet Hien created it

Strategy for tactix

mirror 1st player’s moves

Hex

no chance, perfect information, solved

Who has winning strategy in hex

1st player

Where, when, who for hex

Denmark, 1942, Hein invented, parker brothers gave its name, john nash popularized it

Strategy for hex

build bridges

Sprouts

no chance, perfect information, impartial, partially solved

Who has winning strategy in sprouts

depends on number of dots remining, 3, 4, or 5 = 1st player, 0,1,or 2 = 2nd player

Where, when, and who for sprouts

UK, 1967, John Conway & Michael Paterson

Strategy for sprouts

isolate points, force odd/even number of moves

Dots and Boxes

no chance, perfect information, impartial

Where, when and who for dots and boxes

France, 1889, Francois Lucas

Strategy for Dots and Boxes

double cross

Nine Men’s Morris

no chance, perfect information, partisan, normal rules, solved

Who has winning strategy in Nine Men’s Morris

ends in draw

Where, when and who for Nine Men’s Morris

Switzerland, Roman (old), Ralph Gasser

Strategy for Nine Men’s Morris

double mills

Mancala/Kalah

no chance, perfect information, partisan, solved

Who has winning strategy in mancala

1st player

Where, when and who for mancala

USA, 2000, Geoffrey Irving, Jeroen Donkers, Jos Uiterwijk

Strategy for mancala

steal, open pits on your side

Gomoku/Pente

no chance, perfect information, partisan, solved

Who has winning strategy for gomoku

1st player

Where, when, and who for Gomoku

China, around 270 BC, Louis Victor Allis

Strategy for gomoku

open threes/fours, block open threes/fours

Othello

no chance, perfect information, partisan, solved

Who has winning strategy for othello

draw

Where, when, and who for othello

England, 1888 or 1870, Lewis Waterman, John Mollett

Strategy for Othello

get corners

Go

no chance, perfect info,partisan

Where, when, and who for Go

China, more than 3,000 years ago, Berlekamp, Bill Spight

Strategy for Go

2 eye strategy, surround blank spot and have two of these, open near the edge but not on the edge

Equation for minimum moves in Sprouts

2n

Equation for maximum moves in Sprouts

3n-1