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
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.InputRequested += new EventHandler
game.GameEnded += new EventHandler
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.
