Games.TicTacToe0

Martin Escardo, Paulo Oliva, 27th October 2022

Implementation of tic-tac-toe using a general definition of finite
history dependent game.


{-# OPTIONS --safe --without-K #-}

module Games.TicTacToe0 where

open import Fin.Topology
open import Fin.Type
open import Games.TypeTrees
open import Games.ArgMinMax
open import MLTT.Athenian
open import MLTT.Spartan hiding (J)
open import MonadOnTypes.J
open import MonadOnTypes.K
open import TypeTopology.CompactTypes
open import TypeTopology.SigmaDiscreteAndTotallySeparated
open import UF.DiscreteAndSeparated


The type of outcomes:


R : 𝓤₀ ̇
R = Fin 

open import Games.FiniteHistoryDependent {𝓤₀} {𝓤₀} R
open import MonadOnTypes.JK R


The meaning of the outcomes:


X-wins draw O-wins : R
X-wins = 𝟎
draw   = 𝟏
O-wins = 𝟐


In our conception of game, it is not necessary to specify the players,
but in this case it is convenient to do so:


data Player : 𝓤₀ ̇ where
 X O : Player

opponent : Player → Player
opponent X = O
opponent O = X

value : Player → R
value X = X-wins
value O = O-wins


It is also convenient to have a type of boards:


Grid   = Fin  × Fin 
Matrix = Grid → Maybe Player
Board  = Player × Matrix

board₀ : Board
board₀ = X , (λ _ → Nothing)


Convention: in a board (p , A), the player p plays next.


wins : Player → Matrix → Bool
wins p A = line || col || diag
 where
  _is_ : Maybe Player → Player → Bool
  Nothing is _ = false
  Just X  is X = true
  Just O  is X = false
  Just X  is O = false
  Just O  is O = true

  infix  _is_

  l₀ = A (𝟎 , 𝟎) is p && A (𝟎 , 𝟏) is p && A (𝟎 , 𝟐) is p
  l₁ = A (𝟏 , 𝟎) is p && A (𝟏 , 𝟏) is p && A (𝟏 , 𝟐) is p
  l₂ = A (𝟐 , 𝟎) is p && A (𝟐 , 𝟏) is p && A (𝟐 , 𝟐) is p

  c₀ = A (𝟎 , 𝟎) is p && A (𝟏 , 𝟎) is p && A (𝟐 , 𝟎) is p
  c₁ = A (𝟎 , 𝟏) is p && A (𝟏 , 𝟏) is p && A (𝟐 , 𝟏) is p
  c₂ = A (𝟎 , 𝟐) is p && A (𝟏 , 𝟐) is p && A (𝟐 , 𝟐) is p

  d₀ = A (𝟎 , 𝟎) is p && A (𝟏 , 𝟏) is p && A (𝟐 , 𝟐) is p
  d₁ = A (𝟎 , 𝟐) is p && A (𝟏 , 𝟏) is p && A (𝟐 , 𝟎) is p

  line = l₀ || l₁ || l₂
  col  = c₀ || c₁ || c₂
  diag = d₀ || d₁


The type of moves in a board:


Move : Board → 𝓤₀ ̇
Move (_ , A) = Σ g ꞉ Grid , A g ＝ Nothing


The type of grids has decidable equality (it is discrete) and
decidable quantification (it is compact).  The type of moves in a
board is decidable (either empty or pointed) and also has decidable
quantification.


Grid-is-discrete : is-discrete Grid
Grid-is-discrete = ×-is-discrete Fin-is-discrete Fin-is-discrete

Grid-compact : is-Compact Grid {𝓤₀}
Grid-compact = ×-is-Compact Fin-Compact Fin-Compact

Move-decidable : (b : Board) → is-decidable (Move b)
Move-decidable (_ , A) = Grid-compact
                          (λ g → A g ＝ Nothing)
                          (λ g → Nothing-is-isolated' (A g))

Move-compact : (b : Board) → is-Compact (Move b)
Move-compact (x , A) = complemented-subset-of-compact-type
                        Grid-compact
                        (λ g → Nothing-is-isolated' (A g))
                        (λ g → Nothing-is-h-isolated' (A g))

Update a matrix by playing a move:


update : (p : Player) (A : Matrix) → Move (p , A) → Matrix
update p A (g , _) g' with (Grid-is-discrete g g')
...                        | inl _ = Just p
...                        | inr _ = A g'


Update a board by playing a move:


play : (b : Board) → Move b → Board
play (p , A) m = opponent p , update p A m


The game tree, with a bound on which we perform induction:


tree : Board → ℕ → 𝑻
tree b                 = []
tree b@(p , A) (succ k) with wins (opponent p) A | Move-decidable b
...                        | true  | _     = []
...                        | false | inl _ = Move b ∷ (λ (m : Move b) → tree (play b m) k)
...                        | false | inr _ = []


The outcome function:


outcome : (b : Board) (k : ℕ) → Path (tree b k) → R
outcome b  ⟨⟩ = draw
outcome b@(p , A) (succ k) ms with wins (opponent p) A | Move-decidable b
outcome b@(p , A) (succ k) ⟨⟩        | true  | _     = value (opponent p)
outcome b@(p , A) (succ k) (m :: ms) | false | inl _ = outcome (play b m) k ms
outcome b@(p , A) (succ k) ⟨⟩        | false | inr _ = draw


Selection functions for players, namely argmin for X and argmax for O:


open J-definitions R
open ArgMinMax-Compact-Fin

selection : (p : Player) {M : 𝓤 ̇ } → M → is-Compact M {𝓤₀} → J M
selection X m κ p = pr₁ (compact-argmin p κ m)
selection O m κ p = pr₁ (compact-argmax p κ m)


And their derived quantifiers:


open K-definitions R

quantifier : Player → {M : 𝓤 ̇ } → is-Compact M → is-decidable M → K M
quantifier p κ (inl m) = overline (selection p m κ)
quantifier p κ (inr _) = λ _ → draw


The quantifier tree for the game:


quantifiers : (b : Board) (k : ℕ) → 𝓚 (tree b k)
quantifiers b  = ⟨⟩
quantifiers b@(p , A) (succ k) with wins (opponent p) A | Move-decidable b
... | true  | _     = ⟨⟩
... | false | inl _ = quantifier p (Move-compact b) (Move-decidable b)
                      :: (λ (m : Move b) → quantifiers (play b m) k)
... | false | inr _ = ⟨⟩

And finally the game by putting the above together:


tic-tac-toe : Game
tic-tac-toe = game (tree board₀ ) (outcome board₀ ) (quantifiers board₀ )

r : R
r = optimal-outcome tic-tac-toe


The above computation takes too long, due to the use of brute-force
search in the definition of the game (the compactness conditions). A
more efficient one is in another file.


selections : (b : Board) (k : ℕ) → 𝓙 (tree b k)
selections b  = ⟨⟩
selections b@(p , A) (succ k) with wins (opponent p) A | Move-decidable b
... | true  | _      = ⟨⟩
... | false | inl m₀ = selection p m₀ (Move-compact b)
                      :: (λ m → selections (play b m) k)
... | false | inr _  = ⟨⟩


p : Path (game-tree tic-tac-toe)
p = sequenceᴶ (selections board₀ ) (payoff-function tic-tac-toe)