Geeks With Blogs

News I have joined Anti-IF Campaign
Subscribe in a reader
Lukas Domagala

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

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

 

 

Posted on Wednesday, June 17, 2009 6:07 AM .Net , F# | Back to top


Comments on this post: Connect Four in F# (Part 1)

# re: Connect Four in F# (Part 1)
Requesting Gravatar...
I can't wait to try this, when I get home from work.
Left by Gustavo Keener on Jun 26, 2009 9:00 PM

Your comment:
 (will show your gravatar)


Copyright © Domagala | Powered by: GeeksWithBlogs.net