Matchgame implementation #3: determine if a move is winning

The game to implement is
Given four rows of matches:
|||||||
|||||
|||
|
Two players take turns removing any number of matches from ONE single row. The one to remove the last match looses.

A step toward "intelligence"

In the end I want the computer to act as a player of the game. Therefore I must provide a function to evaluate if a move is a good one or a bad one.
Also, for that one to work, there must be a function to generate all moves that are possible / legal to make on a given state.

The very naive code I came up with was this:

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

let rec IsWinnerLeaveNaive list =
let filtered = List.filter (fun x -> x <> 0) list
match filtered with
| [] -> false
| head::tail -> (list |> List.map abs |> List.sum = 1)
||
(GenerateValidMoves list
|> List.map (MakeMove list)
|> List.map IsWinnerLeaveNaive
|> List.fold_left (fun x acc-> x || acc) false) = false

let losingState = [2;2;1]
let winningState = [2;2;0]

printfn "All possible moves on %A are: %A" losingState (GenerateValidMoves losingState)

printfn "If you leave the state %A, you may win=%A" losingState (IsWinnerLeaveNaive losingState)
printfn "If you leave the state %A, you may win=%A" winningState (IsWinnerLeaveNaive winningState)

So what does it do?
Let's skip the first function for now, and dive right into IsWinnerLeaveNaive.

The first row

let filtered = List.filter (fun x -> x <> 0) list

filters out all elements that are zero from the state, as they make no difference. That might not actually do anything meaningful to this function, but makes the problem a little simpler to think of.

Then it's time for a little match on the filtered list.
The first match is quite straightforward.

| [] -> false

The game is lost when you had to pick the last match, so obviously if you leave no matches after your move, you lose.

The next match simply matches a state which still contains sticks. How to tell if you will win leaving that state after your move?
Well, say that you give your opponent no single way to leave a winning state after him. Then you are on your way to victory.
Also, the case where you leave one single stick is also quite simple. You win, that's it.

So you win either if you leave one single match, or you leave no opportunity for your opponent to make a winning move.

Expressed in F# that becomes:

(list |> List.map abs |> List.sum = 1)
||
(GenerateValidMoves list
|> List.map (MakeMove list)
|> List.map IsWinnerLeaveNaive
|> List.fold_left (fun x acc-> x || acc) false) = false

The first row simply sums the list to find out if only one match remains. The abs is probably overkill, since a valid state cannot contain negative number of matches anyway.

The last four lines generates all possible moves your opponent may take, performs all those moves, and checks that none of the new states reached is a winning state.
The last row List.fold_left is a bit cryptic. It takes a list of booleans like this:
[false true true false] and applies the or-operator to all elements and returns true if all those elements were false.

Why did I call the function "Naive"? Well because it is, and turns out extremely unefficient. Don't try to run it with a longer list containing more matches, or you'll have to kill the fsi.exe process!!!

After writing this post, as mentioned, there were some unnecessary lines of code. I removed them, so the complete example now looks like

#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

let rec IsWinnerLeaveNaive list =
List.sum list = 1
||
(
GenerateValidMoves list
|> List.map (MakeMove list)
|> List.map IsWinnerLeaveNaive
|> List.fold_left (fun x acc-> x || acc) false
) = false

let losingState = [2;2;1]
let winningState = [2;2;0]

printfn "All possible moves on %A are: %A" losingState (GenerateValidMoves losingState)

printfn "If you leave the state %A, you may win=%A" losingState (IsWinnerLeaveNaive losingState)
printfn "If you leave the state %A, you may win=%A" winningState (IsWinnerLeaveNaive winningState)