Negamax Tic-Tac-Toe

Plays the perfect game of Tic-Tac-Toe using the Negamax algorithm.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36:

let wins = [[1;2;3];
            [4;5;6];
            [7;8;9];
            [1;4;7];
            [2;5;8];
            [3;6;9];
            [1;5;9];
            [3;5;7]]

let Contains number = List.exists (fun n -> n = number)

let ContainsList list = List.forall (fun n -> list |> Contains n)

let ExceptList list = List.filter (fun n -> not (list |> Contains n))

let Available (player: int list) (opponent: int list) =
    [1..9]
    |> ExceptList (List.append player opponent)  

let IsWin (squares: int list) = 
    wins |> List.exists (fun w -> ContainsList squares w)

let IsDraw player opponent =
    List.isEmpty (Available player opponent)

let rec Score (player: int list) (opponent: int list) =
    if (IsWin player) then 1
    else if (IsDraw player opponent) then 0
    else
        let opponentsBestMove = BestMove opponent player
        let opponentsNewPosition = opponentsBestMove::opponent
        -Score opponentsNewPosition player

and BestMove (player: int list) (opponent: int list) =
    Available player opponent
    |> List.maxBy (fun m -> Score (m::player) opponent)

val wins : int list list

Full name: Script.wins

val Contains : number:'a -> ('a list -> bool) (requires equality)

Full name: Script.Contains

val number : 'a (requires equality)

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val exists : predicate:('T -> bool) -> list:'T list -> bool

Full name: Microsoft.FSharp.Collections.List.exists

val n : 'a (requires equality)

val ContainsList : list:'a list -> ('a list -> bool) (requires equality)

Full name: Script.ContainsList

Multiple items
val list : 'a list (requires equality)

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val forall : predicate:('T -> bool) -> list:'T list -> bool

Full name: Microsoft.FSharp.Collections.List.forall

val ExceptList : list:'a list -> ('a list -> 'a list) (requires equality)

Full name: Script.ExceptList

val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter

val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

val Available : player:int list -> opponent:int list -> int list

Full name: Script.Available

val player : int list

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val opponent : int list

val append : list1:'T list -> list2:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.append

val IsWin : squares:int list -> bool

Full name: Script.IsWin

val squares : int list

val w : int list

val IsDraw : player:int list -> opponent:int list -> bool

Full name: Script.IsDraw

val isEmpty : list:'T list -> bool

Full name: Microsoft.FSharp.Collections.List.isEmpty

val Score : player:int list -> opponent:int list -> int

Full name: Script.Score

val opponentsBestMove : int

val BestMove : player:int list -> opponent:int list -> int

Full name: Script.BestMove

val opponentsNewPosition : int list

val maxBy : projection:('T -> 'U) -> list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.maxBy

val m : int

Raw view Test code New version

More information

Link:	http://fssnip.net/n2
Posted:	11 years ago
Author:	Richard Dalton
Tags:	tic-tac-toe , ai , recursion