Lately there has been a lot of buzz about functional programming, mostly because it is supposed to be the cure to all of our concurrency troubles. The answer to this from MS has been to productize F#, a functional, object oriented language, running on.Net. There have been a lot of great blog posts and articles about F# in the internet, so if you are looking for a basic introduction this is not really the place.
This series is supposed to fill in the whole i saw while searching for F# content. It seems to me that there are no real step by step guides to building anything bigger then a little script, so I will be trying to build a Connect Four game using F#. I will be concentrating on the AI part of the program but might implement some kind of GUI too if I feel like it any some is reading this:)
I will start with the basic implementation of the AI, because its not that hard to do in F#. Basically we will be using the MiniMax algorithm and we will be making it better over time. So here is mine:
let rec minMax (position:Position) depth player= let heuristic = (runHeuristic position) * player if depth = 0 || heuristic = Int32.MaxValue || heuristic = Int32.MinValue then heuristic else let newPositions = position.NewPositions if newPositions |> Seq.length = 0 then heuristic else newPositions |> Seq.map (fun pos -> -(minMax pos (depth-1) -player)) |> Seq.max
let miniMax (position:Position) depth = let positions = position.Moves let result = positions |> Seq.map (fun pos -> -(minMax (position.DropIn pos) (depth-1) -1), pos) |> Seq.maxBy fst |> snd result
(http://11011.net/software/vspaste)
The miniMax function takes a position, which is just a representation of the game board, and the depth it should search to. It asks the position for all possible moves from here and then calls minMax with the moves applied, returning the move with the highest score. MinMax on the other hand recurs until either the maximum depth is reached or the game is won. It switches players on every recursion so that we do not have to write two nearly identical functions.
What is really nice here is that the F# code is very close to the Pseudo Code used to describe the algorithm. If we checked for a full board in the runHeuristic function we might even be shorter. I will show you the heuristic function next time, but it does not do much more then check if someone has won the game and if not it gives a basic score for the board. We will use the score to our advantage when we switch to a better miniMax implementation.
If you have any comments, they very welcome:)
Technorati Tags:,,,,,