📚 node [[games theory]]

Table of Contents

[2016-07-30] Conway games

  1. L, R : sets of games, then G = <L, R> is a game
  2. DGC: no infinite sequence of games Gi = <Li, Ri> with G(i+1) ∈ Li ∪ Ri for all i ∈ N

L and R are left and right options of G.

G = {L1, L2, … Ln | R1, R2 … Rm }

0 = ({} , {}) = {|}
1 = ({0}, {}} = {0|}
-1 = ({} , {0}) = {|0}

= ({0}, {0}) = {0|0}

n = {n - 1|}
1/2 = {0|1}

Conway induction: ICGN. 0 satisfies automatically.
Proof: infinite sequence of games not satisfying the property, contradiciton.

Conway induction implies DGC

Finitely many positions: short

Same moves: impartial game

Abelian group:

  1. 0 = {|}
  2. G + H = {(GL + H) ∪ (G + HL | (GR + H) ∪ (G + HR)}
  3. -G = {-GR | -GL}

The set of all Conway games forms a partial order with respect to the comparison operations:

  1. G=H. If the second player to move in the game G-H can win (G and H are equal).
  2. G||H. If the first player to move in the game G-H can win (G and H are fuzzy).
  3. G>H. If Left can win the game G-H whether he plays first or not (G is greater than H).
  4. G<H. If Right can win the game G-H whether he plays first or not (G is less than H).

A basic theorem shows that all games may be put in a canonical form, which allows an easy test for equality. The canon
ical form depends on two types of simplification:

  1. Removal of a dominated option: if G={{L1,L2,…}|GR} and L2>=L1, then G={{L2,…}|GR}; and if G={GL|{R1,R_

2,…}} and R1>=R2, then G={GL|{R2,…}}.

  1. Replacement of reversible moves: if G={{{AL|{A(R1),A(R2),…}},G(L2),…}|GR}, and A(R1)<=G, then G={{{A^

(R1L)},G(L2),…}|GR}.

G is said to be in canonical form if it has no dominated options or reversible moves. If G and H are both in canonical
form, they both have the same sets of left and right options and so are equal.

related [[math]]

📖 stoas
⥱ context