
Task

Play a game of tic-tac-toe.

Ensure that legal moves are played and that a winning position is notified.


Tic-tac-toe   is also known as:

   naughts and crosses 
   tic tac toe 
   tick tack toe 
   three in a row 
   tres en rayo       and
   Xs  and  Os


See also
   MathWorld™, Tic-Tac-Toe game.
   Wikipedia tic-tac-toe.


type Brick =
 | Empty
 | Computer
 | User
 
let brickToString = function
 | Empty -> ' '
 | Computer -> 'X'
 | User -> 'O'
 
// y -> x -> Brick
type Board = Map<int, Map<int, Brick> >
 
let emptyBoard =
  let emptyRow = Map.ofList [0,Empty; 1,Empty; 2,Empty]
  Map.ofList [0,emptyRow; 1,emptyRow; 2,emptyRow]
 
let get (b:Board) (x,y) = b.[y].[x]
 
let set player (b:Board) (x,y) : Board =
  let row = b.[y].Add(x, player)
  b.Add(y, row)
 
let winningPositions = 
  [for x in [0..2] -> x,x] // first diagonal
  ::[for x in [0..2] -> 2-x,x] // second diagonal
  ::[for y in [0..2] do
     yield! [[for x in [0..2]->(y,x)]; // columns
             [for x in [0..2] -> (x,y)]]] // rows
 
let hasWon player board = 
  List.exists
    (fun ps -> List.forall (fun pos -> get board pos = player) ps)
    winningPositions
 
let freeSpace board =
  [for x in 0..2 do
     for y in 0..2 do
       if get board (x,y) = Empty then yield x,y]
 
type Evaluation =
 | Win
 | Draw
 | Lose
 
let rec evaluate board move =
  let b2 = set Computer board move
  if hasWon Computer b2 then Win
  else
    match freeSpace b2 with
    | [] -> Draw
    | userChoices -> 
       let b3s = List.map (set User b2) userChoices
       if List.exists (hasWon User) b3s then Lose
       elif List.exists (fun b3 -> bestOutcome b3 = Lose) b3s
       then Lose
       elif List.exists (fun b3 -> bestOutcome b3 = Draw) b3s
       then Draw
       else Win
 
and findBestChoice b =
  match freeSpace b with
  | [] -> ((-1,-1), Draw)
  | choices -> 
    match List.tryFind (fun c -> evaluate b c = Win) choices with
    | Some c -> (c, Win)
    | None -> match List.tryFind (fun c -> evaluate b c = Draw) choices with
              | Some c -> (c, Draw)
              | None -> (List.head choices, Lose)
 
and bestOutcome b = snd (findBestChoice b)
 
let bestChoice b = fst (findBestChoice b)
 
let computerPlay b = set Computer b (bestChoice b)
 
let printBoard b =
  printfn "   | A | B | C |"
  printfn "---+---+---+---+"
  for y in 0..2 do
   printfn " %d | %c | %c | %c |"
    (3-y)
    (get b (0,y) |> brickToString)
    (get b (1,y) |> brickToString)
    (get b (2,y) |> brickToString)
   printfn "---+---+---+---+"
 
let rec userPlay b =
  printfn "Which field do you play? (format: a1)"
  let input = System.Console.ReadLine()
  if input.Length <> 2
     || input.[0] < 'a' || input.[0] > 'c'
     || input.[1] < '1' || input.[1] > '3' then
     printfn "illegal input"
     userPlay b
  else
     let x = int(input.[0]) - int('a')
     let y = 2 - int(input.[1]) + int('1')
     if get b (x,y) <> Empty then
       printfn "Field is not free."
       userPlay b
     else
       set User b (x,y)
 
let rec gameLoop b player =
  if freeSpace b = [] then
    printfn "Game over. Draw."
  elif player = Computer then
    printfn "Computer plays..."
    let b2 = computerPlay b
    printBoard b2
    if hasWon Computer b2 then
      printfn "Game over. I have won."
    else
      gameLoop b2 User
  elif player = User then
    let b2 = userPlay b
    printBoard b2
    if hasWon User b2 then
      printfn "Game over. You have won."
    else
      gameLoop b2 Computer
 
// randomly choose an element of a list
let choose =
  let rnd = new System.Random()
  fun (xs:_ list) -> xs.[rnd.Next(xs.Length)]
 
// play first brick randomly
printfn "Computer starts."
let b = set Computer emptyBoard (choose (freeSpace emptyBoard))
printBoard b
gameLoop b User