Matchgame implementation #7: Further optimization?

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 last post the implementation was sped up by about 200 times, making the original game layout (7, 5, 3, 1) playable.

How can this be optimized further. First let's take a non-scientific approach of the math involved. Non-scientific because I don't have it fresh in my head.
We must first realize that this algorithm does a complete search of all the states. If n denotes the number of sticks in play, then the running time would be proportional to n^c (c= some number > 2), or even worse; e^n. I think the latter is closer to the truth. By realizing this there is also another fact that must be faced. Even if the run time can be cut by a factor of 200, just increase n with a few sticks and run-time still blows up in your face! Try plotting the graph for e^n for various n, and you'll see.

How to approach this?
The best way would be to take a completely different approach on the algorithm. For example exploit the patterns that can be found for winning moves. I will not do that however, how fun would it be to reveal thos patterns? It would render the game completely meaningless.

The second best way would be to give up and lie down. Much money could probably have been better spent if more programmers came to this realization early.

In this post I'm going to do something in between those two ways; try to improve on the already doomed algorithm and perhaps make it better by a constant factor. I really hope that no one getting paid to do this optimization would chose that way!!!

I have two different thoughts on how it could be improved.

1. 1. When doing a complete search, try out the moves that removes the most number of sticks first, since that should quickly bring us to a losing or winning state.
2. 2. Save all states that we already have computed if they are winning or losing, so we don't have to do that over and over again.

Here's the code to test the performace prior to optimization:

#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 run_time_func (func: unit -> 'a) =
let time0 = System.DateTime.Now
let res = func ()
let diff0 = System.DateTime.Now - time0
(diff0, res)

// 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 state =
match maxDepth with
| 0 -> false
| _ ->
(state |> List.map abs |> List.sum = 1)
||
(
let rec HasWinningMove state moves maxDepth =
match moves with
| [] -> false
| a::b -> IsWinnerLeaveRec (maxDepth - 1) (MakeMove state a) || HasWinningMove state b maxDepth
let moves = GenerateValidMoves state
HasWinningMove state moves maxDepth
) = false

let startState = [7;5;3;1]
let (time, result) = run_time_func (fun() -> IsWinnerLeaveRec (List.sum startState) startState)
printfn "%A" time

The results seem to average about 3.5 seconds.


Now let's implement the first approach:

// 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 state =
match maxDepth with
| 0 -> false
| _ ->
(state |> List.map abs |> List.sum = 1)
||
(
let rec HasWinningMove state moves maxDepth =
match moves with
| [] -> false
| a::b -> IsWinnerLeaveRec (maxDepth - 1) (MakeMove state a) || HasWinningMove state b maxDepth
let moves =
GenerateValidMoves state
|> List.sort (fun (_, toRemove1) (_,toRemove2) -> toRemove2 - toRemove1)
HasWinningMove state moves maxDepth
) = false

let startState = [7;5;3;1]
let (time, result) = run_time_func (fun() -> IsWinnerLeaveRec (List.sum startState) startState)
printfn "%A" time

Note now how the list of moves is sorted, so the moves removing the most matches are tested first.
The result is promising, run time seems to average 2.5 seconds now. And that despite the additional step of sorting a list every state that is tested (which is really really unnecessary).
Just for "fun" I changed the sort order and re-ran the test. It took nearly 3 minutes!

So how to avoid the sorting? Change the function "GenerateValidMoves" of course, so it generates the moves in that order from the start!

...
Time passes
...

Ok, Didn't manage to do this in any working way. Making a list in descending order wan't as easy as writing [10 .. 1]. Anybody got a clue there?
So now it's time to follow my own advice. Give up. I mean, who would want to play this game with 100 matches anyway???
Maybe I'll try to make the saving of calculated states in the next post. Wrapping the matchgame in a silverlight UI might be another fun thing to do.