A Novice Learning F#

fredag 24 juni 2011

Not that novice any more

Having worked through the excellent book Real World Functional Programming, and spent a couple of hundred hours with F#, I wouldn't say I'm a novice any more, though far from professional.

I will be writing about F# issues, and my hobby project of writing of an online game using F# on my new blog.

måndag 23 mars 2009

Matchgame implementation #8: Exposing to C#

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.

Complete source code with a C# console UI can be downloaded here.
Executable can be dowloaded here.

Since I'm a C# programmer, I wanted to turn the F# implemntation of the matchgame to something easily usable from C#.

Some requirements came to mind

Object-oriented
Exposing events when something happens

Uhm... that would be it. This would make the class somewhat a Presenter in the MVP pattern. So the Silverlight UI i've been talking about will easily use the presenter. But I don't want the added complexity of Silverlight quite yet (never used it), so the UI will be a console app for now.

I solved the requirements by wrapping the state of the game in a class called MatchStickGame.
It exposes the state as an array property.
It exposes two methods: Begin and MakePlayerMove
It exposes three events: Moved, InputRequested and GameEnded.

Here's the complete F# code:

#light
open System

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

// checks if a leave is winning
let IsWinnerLeave state = IsWinnerLeaveRec (List.sum state) state

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

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

type MatchGameEndedEventArgs(playerWins) =
inherit EventArgs()
member this.PlayerWins : bool = playerWins

type MatchStickGame ()=
let mutable state = [7;5;3;1]

let movedEvent = new Event%lt;EventHandler%lt;EventArgs%gt;,_%gt;()
let requestInputEvent = new Event%lt;EventHandler%lt;EventArgs%gt;,_%gt;()
let gameEndedEvent = new Event%lt;EventHandler%lt;MatchGameEndedEventArgs%gt;,_%gt;()
// let fireMoved, movedEvent = Event.create_
let TriggerMoved this = movedEvent.Trigger (this, new EventArgs())

let RequestPlayerMove this state =
requestInputEvent.Trigger (this, new EventArgs())

let rec RequestComputerMove this state =
// Ask the computer how to move
let computerMove = GenerateWinnerMove state
// do the move and make it the player's turn
ActOnChosenMove this computerMove RequestComputerMove RequestPlayerMove

and ActOnChosenMove this (index, number) currentPlayerRequester nextPlayerRequester =
if not (ValidMove state (index, number)) then
currentPlayerRequester this state
else
// Move, trigger that a move was made and ask the next player for input
state %lt;- MakeMove state (index, number)
TriggerMoved this

if (List.sum state) %lt; 2 then
gameEndedEvent.Trigger(this, new MatchGameEndedEventArgs((currentPlayerRequester = RequestPlayerMove)))
else
nextPlayerRequester this state

// Events
member this.Moved = movedEvent.Publish
member this.InputRequested = requestInputEvent.Publish
member this.GameEnded = gameEndedEvent.Publish
// State property
member this.State = state |%gt; List.to_array

// Methods
member this.Begin() =
TriggerMoved this
RequestPlayerMove this state

member this.MakePlayerMove (index, number) =
ActOnChosenMove this (index, number) RequestPlayerMove RequestComputerMove

Here's the complete C# code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GameAsCSharpConsole
{
class Program
{
static void Main(string[] args)
{
MatchGame.MatchStickGame game = new MatchGame.MatchStickGame();
game.Moved += new EventHandler(game_Moved);
game.InputRequested += new EventHandler(game_InputRequested);
game.GameEnded += new EventHandler(game_GameEnded);
game.Begin();
Console.ReadKey();
}

static void game_GameEnded(object sender, MatchGame.MatchGameEndedEventArgs e)
{
Console.WriteLine();
Console.WriteLine("Game ended");
if (e.PlayerWins)
{
Console.WriteLine("you win!");
}
else
{
Console.WriteLine("You lose!");
}
}

static void game_InputRequested(object sender, EventArgs e)
{
Console.Write("Enter a move>");
string input = Console.ReadLine();
string[] parts = input.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);

int index = int.Parse(parts[0]);
int number = int.Parse(parts[1]);

((MatchGame.MatchStickGame)sender).MakePlayerMove(index, number);
}

static void game_Moved(object sender, EventArgs e)
{
Console.WriteLine();
Console.WriteLine("New state:");
DisplayState((MatchGame.MatchStickGame)sender);
}

static void DisplayState(MatchGame.MatchStickGame game)
{
int[] state = game.State;
for (int i = 0; i < j =" 0;">

After the previous GUI implementation directly with F# compared to this one in C#, I'm starting to think C# is actually quite cumbersome. F# becomes more and more appealing!

Ok, what happens in this code?

Let's take a look at the public members first:

member this.Moved = movedEvent.Publish
member this.InputRequested = requestInputEvent.Publish
member this.GameEnded = gameEndedEvent.Publish

member this.State = state |> List.to_array

member this.Begin() =
TriggerMoved this
RequestPlayerMove this state

member this.MakePlayerMove (index, number) =
ActOnChosenMove this (index, number) RequestPlayerMove RequestComputerMove

First comes the three events that the UI should subscribe to.
Moved means that the game state has changed and needs to be redrawn.

InputRequested means that it is the player's turn, so the UI has to ask the player for input and then tell the game what the input was, through MakePlayerMove.

GameEnded means that the game has ended. It uses MatchGameEndedEventArgs, which contains a property telling is the player won or lost the game.

Then comes the property State, which the GUI should use to draw the game. I realize that the array elements are not read only. Not a good thing, but such matters are not the subject of this post, so let's just ignore that!

Begin is a method to get things going. It triggers events so the GUI knows it's time to draw the state and get user input.

MakePlayerMove is the method the GUI should call when the user has entered his/her move.
It propagates the call to its "private" counterpart ActOnChosenMove.

So let's have a look at what that one does.

let rec RequestComputerMove this state =
// Ask the computer how to move
let computerMove = GenerateWinnerMove state
// do the move and make it the player's turn
ActOnChosenMove this computerMove RequestComputerMove RequestPlayerMove

and ActOnChosenMove this (index, number) currentPlayerRequester nextPlayerRequester =
if not (ValidMove state (index, number)) then
currentPlayerRequester this state
else
// Move, trigger that a move was made and ask the next player for input
state <- MakeMove state (index, number)
TriggerMoved this

if (List.sum state) < 2 then
gameEndedEvent.Trigger(this, new MatchGameEndedEventArgs((currentPlayerRequester = RequestPlayerMove)))
else
nextPlayerRequester this state

It is shown along with the function RequestComputerMove. Look at the declaration, it uses and instead of let. Why?
Well, they are mutually recursive and then they obviously need to be declared in that way, or the program won't compile.

So what does ActOnChosenMove do?
It takes the instance of the MatchStickGame to be able to use that in the events (object sender). It takes the desired move.
And it takes two "delegates" to be able to ask for input. The first thing it does is to check if it is a valid move, and if not it immediately asks the current user for new input.
If the move is valid, it is used to put the game in a new state. It then triggers the event which tells that the state has changed, allowing GUI update.

It then checks if the game is pointless to continue (less than two sticks left).
if it is pointless, it trigger the GameEnded event, checking if the current player is the winner.

If the game should continue, it asks the next player for input.

The RequestComputerMove simply generates the computer's move, and Acts on it.

The code actually contains a bug, which will very rarely show. Can you find it, and tell why it probably won't show?

To the "instance variables"

let mutable state = [7;5;3;1]

let movedEvent = new Event<EventHandler<EventArgs>,_>()
let requestInputEvent = new Event<EventHandler<EventArgs>,_>()
let gameEndedEvent = new Event<EventHandler<MatchGameEndedEventArgs>,_>()

The state simply is the state. Mutable, since it can change.

Then comes three event helper variables. I haven't quite gotten the F# event model figured out, but it doesn't use the standard EventHandler signature pattern, so those three lines create "regular .Net"-compatible event thingies. The actual events are exposed as members further down the class.

RequestPlayerMove triggers the InputRequested event, but also matches RequestComputerMove in signature. That is so that the game "engine" ActOnChosenMove doesn't have to have different code for the player's turn or the computer's turn.

Matchgame implementation. Making it usable from C#

I mentioned it would be nice to make a GUI in silverlight for the matchgame. The language will be C#. So first I have to come up with a useful way of exposing the f# functions to C#.

That will be the next post.

söndag 22 mars 2009

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. 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. 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:

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.

måndag 16 mars 2009

Matchgame implementation #6: 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.

The previous post held a working implementation of this game. But it was extremely ineficcient, and I had to limit recursion depth for the algorithm to complete in a reasonable time. Which lead to that the computer did not make the right decision until very few sticks remained.

So let's take a look at the bad function along with the complete code to compute the time it takes to run:

The bad function is "IsWinnerLeaveRec".
Here I also introduced a function which calculates the run time of another: "run_time_func". I "stole" it right away from F# for game development, I hope that's ok

Note in the last row that actually does the execution, the argument maxDepth is set to "(List.sum startState)". Since one move in the game always removes at least one stick, the maximum possible recursion depth is the number of sticks. And here I want to allow that depth to be able to measure properly.

The results on my system averages to 4 seconds.

So what to do?
Let's focus on the following:

(
let moves = GenerateValidMoves list
moves
|> List.map (MakeMove list)
|> List.map (IsWinnerLeaveRec (maxDepth - 1))
|> List.fold_left (fun x acc-> x || acc) false
) = false

The purpose of those lines is to verify that none of the valid moves may lead to a winning state.
What strikes me here is that the number of possible moves may be very large, but ALL of them are ALWAYS checked. That's quite unnecessary to do. Once we fint ONE move that's winning, we can stop. No need to evaluate all the rest!

So I introduce a new function which does just that; Check for ANY winning move, and if found then stop:

let rec HasWinningMove state moves maxDepth =
match moves with
| [] -> false
| a::b -> IsWinnerLeaveRec (maxDepth - 1) (MakeMove state a) || HasWinningMove state b maxDepth

It takes the state, a list of possible moves, and the maxDepth.
It performs a match on moves.
If there are no moves, then obviously there are no winning moves, so it evaluates to false;
If there is at least one move, then the list contains a winning move if the first move generates a winning state
OR if the remaining moves has a winning move.

Simple, right?
the original bad function the becomes:

let rec IsWinnerLeaveRec maxDepth state =
match maxDepth with
| 0 -> false
| _ ->
(state |> List.map abs |> List.sum = 1)
||
(
let moves = GenerateValidMoves state
HasWinningMove state moves maxDepth
) = false

Should be understandable?

Now the test runs in about 0.02 seconds, which is 200 times faster than the original!

The bad thing is that the code won't compile. It doesn't seem like you can have two functions calling each other. I solved that by defining "HasWinningMove" within "IsWinnerLeave"
Here's working code:

#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 = [2;5;3;1]
let (time, result) = run_time_func (fun() -> IsWinnerLeaveRec (List.sum startState) startState)
printfn "%A" time

// Time with this one about 0.02s
// Original: about 4s

// checks if a leave is winning
let IsWinnerLeave list = IsWinnerLeaveRec (List.sum list) list

let rec PickWinnerMove state moves =
match moves with
|[] -> failwith "No valid moves"
|[a]-> 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

open System

let GetMoveFromUser state =
printfn "enter a move (row numberToRemove)>"
let input = Console.ReadLine()
let parts = input.Split([|' '|], StringSplitOptions.RemoveEmptyEntries)
let row = int parts.[0]
let numberToRemove = int parts.[1]
(row, numberToRemove)

let GetMoveFromComputer state =
let move = GenerateWinnerMove state
printfn "The computer moves %A" move
move

let StatePrinter state =
printfn "State:"
List.mapi (
fun i x ->
printf "%i: " i
for n in [1..x] do
printf "|"
printfn ""
) state
|> ignore

let rec main (activePlayerName, activePlayerInputRequest) (otherPlayerName,otherPlayerInputRequest) state=
StatePrinter state
let move = activePlayerInputRequest state
let newState = MakeMove state move
if (List.sum newState) < 2 then
if IsWinnerLeave newState then
StatePrinter newState
printfn "The game was won by %A" activePlayerName
else printfn "The game was lost by %A" activePlayerName
else
main (otherPlayerName, otherPlayerInputRequest) (activePlayerName, activePlayerInputRequest) newState

main ("Player", GetMoveFromUser) ("Computer", GetMoveFromComputer) [7;5;3;1]

ignore (Console.ReadKey())

Can you beat the computer? Can you beat the computer in different ways? Good luck ;)

Matchgame implementation #5: Making a playable game

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, everything for the game was provided, except for control flow wrapping all the pieces together in a playable game.

After some fiddling I managed to put it togather, so here comes the code for a complete playable game:

#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 5 list

let rec PickWinnerMove state moves =
match moves with
|[] -> failwith "No valid moves"
|[a]-> 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

open System

let GetMoveFromUser state =
printfn "enter a move (row numberToRemove)>"
let input = Console.ReadLine()
let parts = input.Split([|' '|], StringSplitOptions.RemoveEmptyEntries)
let row = int parts.[0]
let numberToRemove = int parts.[1]
(row, numberToRemove)

let GetMoveFromComputer state =
let move = GenerateWinnerMove state
printfn "The computer moves %A" move
move

let StatePrinter state =
printfn "State:"
List.mapi (
fun i x ->
printf "%i: " i
for n in [1..x] do
printf "|"
printfn ""
) state
|> ignore

let rec main (activePlayerName, activePlayerInputRequest) (otherPlayerName,otherPlayerInputRequest) state=
StatePrinter state
let move = activePlayerInputRequest state
let newState = MakeMove state move
if (List.sum newState) < 2 then
if IsWinnerLeave newState then
StatePrinter newState
printfn "The game was won by %A" activePlayerName
else printfn "The game was lost by %A" activePlayerName
else
main (otherPlayerName, otherPlayerInputRequest) (activePlayerName, activePlayerInputRequest) newState

let startState = [7;5;3;1]

main ("Player", GetMoveFromUser) ("Computer", GetMoveFromComputer) startState

ignore (Console.ReadKey())

Now let's take a look at what was added. We'll jump right into main and look at the other functions later.

let rec main (activePlayerName, activePlayerInputRequest) (otherPlayerName,otherPlayerInputRequest) state=
StatePrinter state
let move = activePlayerInputRequest state
let newState = MakeMove state move
if (List.sum newState) < 2 then
if IsWinnerLeave newState then
StatePrinter newState
printfn "The game was won by %A" activePlayerName
else printfn "The game was lost by %A" activePlayerName
else
main (otherPlayerName, otherPlayerInputRequest) (activePlayerName, activePlayerInputRequest) newState

It's a function that takes two tuples and the current state of the game.
Each tuple represents a player; the name of the player, and the function to call to get a move from that player.

StatePrinter state

Just displays the state in a way resembling the original game of matches. It might as well just have said "print_any state", but how ugly is that? (it originally looket like that :)

let move = activePlayerInputRequest state

The next step asks the user for which move he/she/it wants to make on the given state. Explanation about those functions later, let's just accept that the function returns a move the player wants to make.

let newState = MakeMove state move

Nothing arcane about the state transition either. We have a state, the user wants to perform a move on it. Well, make the move and we get a new state!

if (List.sum newState) < 2 then
if IsWinnerLeave newState then
StatePrinter newState
printfn "The game was won by %A" activePlayerName
else printfn "The game was lost by %A" activePlayerName

This is to check if the user has won the game. To be honest, the game is so deterministic that even before it has started it is already decided who will win, assuming the winner knows the pattern.
But wouldn't it be boring to just say: You begin therefore you lose.? That gives no room for the "winner-to-be" to make a mistake and let the other player win.

But once we get down to only one or zero sticks left, it might be ok to reveal the winner.
So that's what the outer "if" does, it checks if there are less than two sticks left in the game.
If so it checks if the state is a winning or a losing state, and writes out whether the current player won or lost.

else
main (otherPlayerName, otherPlayerInputRequest) (activePlayerName, activePlayerInputRequest) newState

The outer else runs if there are at least 2 sticks left, that is enough sticks to still allow for mistakes.
What happens is that the main function is called again, but now switching between who is the active and passive player, and providing the new state.

I'll not bother to go throught the "StatePrinter" function unless someone asks.

So lets look at:

let GetMoveFromUser state =
printfn "enter a move (row numberToRemove)>"
let input = Console.ReadLine()
let parts = input.Split([|' '|], StringSplitOptions.RemoveEmptyEntries)
let row = int parts.[0]
let numberToRemove = int parts.[1]
(row, numberToRemove)

The function uses an ordinary Console.ReadLine() to get the user input. It assumes that one number is input for the row index to remove at, and one number for the number of sticks to remove from that row.
It then splits the string and picks out the first part as index, and the second part as number to remove.
It returns a tuple with those two numbers, which happens to be the representation of a move.
What about the parameter "state" which is never used? Well, I needed it to give this function the same signature as the one that asks the computer for a move:

let GetMoveFromComputer state =
let move = GenerateWinnerMove state
printfn "The computer moves %A" move
move

This one is simply just a wrapper for "GenerateWinnerMove", printing out the move that the computer chooses.

Because of the really crappy algorithm limited in recursion depth you should be able to beat the game 10 times out of 10!

Hmm, look where that statement got me when playing in order to be able to get a screen dump:

State:
0: |||||
1: |||
2: |
enter a move (row numberToRemove)>
0 3
State:
0: ||
1: |||
2: |
The computer moves (0, 1)
State:
0: |
1: |||
2: |
enter a move (row numberToRemove)>
1 3
State:
0: |
1:
2: |
The computer moves (2, 1)
State:
0: |
1:
2:
The game was won by "Computer"

And that with a simplified starting state!!! shame on me!
Can you do better?

Ps. The code was a tiny bit modified from the previous post, Thanks for the comment!

Matchgame implementation #4: Making the computer decide

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:

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!