nim

import strformat
import tables

#               (matches, color), (bestMove, heuristic)
var transposition = initTable[(int, int), (int, int)]()

func negaMax(matches: int, color: int, tTable: Table[(int, int), (int, int)]): (int, int) = 
  var key = (matches, color)
  if tTable.hasKey(key):
    return tTable[key]
    
  var bestMove = 0

  if matches == 1:
    return (bestMove, color * -1)

  var v = -10 * color

  for move in 1..3:
    if matches - move > 0:

      var (_, score) = negaMax(matches - move, -color, tTable)

      if score * color > v * color:
        v = score
        bestMove = move

  var value = (bestMove, v)
  # tTable.add(key, value)
  tTable[key] = value

  return value

proc playNim(matches: int) =
  var turn = 1
  var matchesLeft = matches

  var movesEcho = ""
  while matchesLeft != 1:
    var (move, _) = negaMax(matchesLeft, turn, transposition);

    movesEcho &= &"{matchesLeft}: {turn} plays {move}\n"

    matchesLeft -= move
    turn = -turn
  
  echo movesEcho
  echo &"{-turn} won"

playNim(6)