Matchgame implementation #4: Making the computer decide

The game to implement is
Given four rows of matchsticks:
|||||||
|||||
|||
|
Two players take turns removing any number of sticks from ONE single row. The one to remove the last stick loses.

In the previous post there were functions to:

• Verify that a move is valid (ValidMove)
  
• Apply a given move (MakeMove)
• Generate all possible moves for a given state (GenerateValidMoves)
• Verify that a given state is winning when your move is complete (IsWinnerLeaveNaive)

The next step would be to make the computer "think" out a winning move to make, given a state.

Also, the function IsWinnerLeaveNaive is so extremely poor-performing that I have made a new one with a "safety valve" so it does not blow up in your face.

The code so far looks lie:

#light

let ValidMove state (removeAtIndex, removeNumber) =
removeAtIndex >= 0 &&
removeAtIndex < List.length state &&
removeNumber > 0 &&
removeNumber <= List.nth state removeAtIndex

let MakeMove state (removeAtIndex, removeNumber) =
if ValidMove state (removeAtIndex, removeNumber) = false then failwith (sprintf "%A is not a valid move on %A" (removeAtIndex, removeNumber) state)
List.mapi (fun i numberOfMatches -> if removeAtIndex = i then numberOfMatches - removeNumber else numberOfMatches) state

let GenerateValidMoves state =
let mutable validMoves = []
let validIndices = [0 .. List.length state - 1]
for i in validIndices do
let validNumberOfPicks = [1 .. List.nth state i]
for n in validNumberOfPicks do
validMoves <- (i, n)::validMoves
validMoves

// Checks if a leave is winning by complete search. Since it can take extreme time
// to calculate, the parameter maxDepth is used to limit how many look-aheads are
// valid to do (recursion depth).
let rec IsWinnerLeaveRec maxDepth list =
match maxDepth with
| 0 -> false
| _ ->
(list |> List.map abs |> List.sum = 1)
||
(GenerateValidMoves list
|> List.map (MakeMove list)
|> List.map (IsWinnerLeaveRec (maxDepth - 1))
|> List.fold_left (fun x acc-> x || acc) false) = false

// checks if a leave is winning
let IsWinnerLeave list = IsWinnerLeaveRec 6 list

let rec PickWinnerMove state moves =
match moves with
|[] -> failwith "No valid moves"
|a::b when b = []-> a
|a::b when (IsWinnerLeave (MakeMove state a)) -> a
|a::b when not (IsWinnerLeave (MakeMove state a)) -> PickWinnerMove state b
|_ ->failwith "unknown state"

let GenerateWinnerMove state =
let possibleMoves = GenerateValidMoves state
PickWinnerMove state possibleMoves

let state = [3;5;2;1]
let move = GenerateWinnerMove state
printfn "A winning move on the state %A is %A, which brings it to %A" state move (MakeMove state move)

The new function GenerateWinnerMove is very simple. It generates all possible moves in the given state, and lets the function PickWinnerMove select a winning move from those.

So let's look further at PickWinnerMove:

let rec PickWinnerMove state moves =
match moves with
|[] -> failwith "No valid moves"
|a::b when b = []-> a
|a::b when (IsWinnerLeave (MakeMove state a)) -> a
|a::b when not (IsWinnerLeave (MakeMove state a)) -> PickWinnerMove state b
|_ ->failwith "unknown state"

It does a match on the list of supplied moves. If no moves were provided (empty list) it fails.

The following matches are conditional, that is they only match if the "when" is evaluated to true.
the first match of those is:

|a::b when b = []-> a

It will only match if it is a list with elements, but with the condition that the tail is empty i.e. a one-element list. Then there's not much to choose from, is it? We have to pick that move no matter if it is winning or not.

|a::b when (IsWinnerLeave (MakeMove state a)) -> a

This one says that if a is a move which takes us to a state which is winning, then pick a. Should be obvious, we have found our winning move!

|a::b when not (IsWinnerLeave (MakeMove state a)) -> PickWinnerMove state b

This one is the opposite of the previous; if a is not a winning move, keep looking for winning moves among the remaining possible moves

|_ ->failwith "unknown state"

This last one is a bit nasty. It should never be able to happen, since the two previous matches cover up all the cases except the empty list. But the F# compiler obviously has a difficulty figuring that out when using "when".

So now the computer is "smart" and can decide on a move to make. But it is limited by the depth of recursion, so it is really not that smart. Try changing the depth to 5 instead of 6 in the example above, and you will get a different answer, which indeed is not a winning move!
And still the "IsWinnerLeave" function may blow up in your face with enough matchsticks in the state. Jsut not as hard as before. But who gets happier from waiting 1 year for an answer instead of 1000?

But I'm still a novice, and the time for optimization has yet to come!