tictactoe typst

#let player = "x"
#let computer = "o"

#set table(columns: (2em,2em,2em),rows: (2em,2em,2em), align: center)
#set page(width: 10em,height: 12em)
#show link: underline
#show link: it => text(blue,it)
#show: it => align(center,it)

#let get-page(state) = link(label(state))[.]
#let fill_comp(c) = {
  if c == "." {return computer}
  return c
}
#let get-best-move(state) = {
  assert(state.len()==9)
  // immediate win opportunities
  for i in range(3) {
    let row = state.slice(i*3,count :3)
    if row.matches(computer).len() == 2 and row.matches(".").len() == 1 {
      return state.slice(0,i*3)+computer*3+state.slice((i+1)*3)
    }
  }
  for i in range(3) {
    let col = state.at(i)+state.at(i+3)+state.at(i+6)
    if col.matches(computer).len() == 2 and col.matches(".").len() == 1 {
      return state.slice(0,i)+computer+state.slice(i+1,count :2)+computer+state.slice(i+4,count :2)+computer+state.slice(i+7)
    }
  }
  let diag1 = state.at(0)+state.at(4)+state.at(8)
  let diag2 = state.at(2)+state.at(4)+state.at(6)
  if diag1.matches(computer).len() == 2 {
    return computer+state.slice(1,4)+computer+state.slice(5,8)+computer
  }
  if diag2.matches(computer).len() == 2 {
    return state.slice(0,2)+computer+state.at(3)+computer+state.at(5)+computer+state.slice(7)
  }

  // if no immediate win, close player wins
  for i in range(3) {
    let row = state.slice(i*3,count :3)
    if row.matches(player).len() == 2 and row.matches(".").len() == 1 {
      return state.slice(0,i*3)+fill_comp(row.at(0))+fill_comp(row.at(1))+fill_comp(row.at(2))+state.slice((i+1)*3)
    }
  }
  for i in range(3) {
    let col = state.at(i)+state.at(i+3)+state.at(i+6)
    if col.matches(player).len() == 2 and col.matches(".").len() == 1 {
      return state.slice(0,i)+fill_comp(state.at(i))+state.slice(i+1,count :2)+fill_comp(state.at(i+3))+state.slice(i+4,count :2)+fill_comp(state.at(i+6))+state.slice(i+7)
    }
  }
  if diag1.matches(player).len() == 2 and diag1.matches(".").len() == 1 {
    return fill_comp(state.at(0))+state.slice(1,4)+fill_comp(state.at(4))+state.slice(5,8)+fill_comp(state.at(8))
  }
  if diag2.matches(player).len() == 2 and diag2.matches(".").len() == 1 {
    return state.slice(0,2)+fill_comp(state.at(2))+state.at(3)+fill_comp(state.at(4))+state.at(5)+fill_comp(state.at(6))+state.slice(7)
  }

  // arbitrary placement if nothing found
  for i in range(9){
    if state.at(i) == "."{
      return state.slice(0,i)+computer+state.slice(i+1)
    }
  }

  state // fallback if tie
}
#let winner(state) = {
  for i in range(3) {
    let row = state.slice(i*3,count :3) // :3
    if row.matches(row.at(0)).len() == 3 {
      return row.at(0)
    }
  }
  for i in range(3) {
    let col = state.at(i)+state.at(i+3)+state.at(i+6)
    if col.matches(col.at(0)).len() == 3 {
      return col.at(0)
    }
  }
  let diag = state.at(0)+state.at(4)+state.at(8)
  if diag.matches(diag.at(0)).len() == 3 {
    return diag.at(0)
  }
  let diag = state.at(2)+state.at(4)+state.at(6)
  if diag.matches(diag.at(0)).len() == 3 {
    return diag.at(0)
  }
  return "."
}
#let tictactoe(state,norefs: false) = [
  #if winner(state)!="." {norefs=true}
  #let symbols = ("","","","","","","","","")
  #for i in range(9) {
    if state.at(i) == "." {
      if norefs {symbols.at(i)="."}
      else {symbols.at(i) = get-page(get-best-move(state.slice(0,i)+player+state.slice(i+1)))}
    } else {
      symbols.at(i) = state.at(i)
    }
  }
  #figure(
    table(..symbols)
  )
  #label(state)
]

#let generate(state,used:()) = {
  if state in used {return ([],used)}
  let c = []
  assert(state.len()==9,message:"err "+state)

  c+=tictactoe(state)
  if state.matches(".").len()<=0 {return (c+[Tie. \ #link(label("........."))[Go back] #pagebreak()],used+(state,))}
  if winner(state)!="."{return (c+[Winner: #winner(state) \ #link(label("........."))[Go back] #pagebreak()],used+(state,))}
  for i in range(9){
    if state.at(i)=="."{
      let v = generate(get-best-move(state.slice(0,i)+player+state.slice(i+1)),used:used+(state,))
      c+=v.at(0)
      used=v.at(1)
    }
  }
  c+=pagebreak()
  (c,used+(state,))
}
#generate(".........").at(0)