Last time we saw how to implement the basic miniMax algorithm, this time we will continue by designing game board representation.
Basically I want to start out with the “simplest thing that might possibly work” and optimize from there. The simplest thing to use for this in F# is a 2 dimensional list. The problem is that we get some really bad performance for random access into them, because unlike C# Lists, called ResizeArray in F#, they really are represented by lists internally. To be precise they are actually just this:
type list<'T> =
| ( [] )
| ( :: ) of 'T * 'T list
Ok so what do we choose instead of lists? We could take Array2D which is just what we need, but we would loose all the nice functional methods we have on other F# collections. So we will have to stick with an array of arrays I guess. So what put into those lists? In C# i would probably have started with something Byte, but F# has the nice concept of discriminated unions which are basically types which can be in one of the given states. Here is what we will be using for now:
type field = Yellow | Red | Empty
Usually we could just stick with our nice discriminated unions, but again we have to think at least a little about performance. Discriminated unions are represented by classes that hold integers for every state the union can be in, which would mean we had references which are huge compared to a small byte. Well I guess we cant always get the the easiest thing possible, so we will go with bytes this time. –1y for one player, 0y for the other and 1y for the second player.
Now we need some way to initialize a 2D list to be filled with 0y, to get our starting game board. In an imperative language i might have used something like to nested loops to fill in the lists. There is nothing wrong with this approach but its not really functional and kind of discouraged in the F# world. The closest you might see would be something like:
let createEmptyBoard rows cols =
[for i in 0..(rows-1) do
for y in 0..(cols-1) -> 0y]
This is using something called sequence expressions which is really useful for creating all kinds of sequences, lists and so on. There is an easier way though:
static member EmptyPosition cols rows =
Position((Array.create 7 (Array.create 6 0y)),1y)
Now that we can create an empty board lets think about how we would drop in a disc to create a new board. Notice that we do not want to change the old board, but to create a new one. We already know what our function definition should look like so lets work from there:
let toggle player=
player * -1y
member p.CanDropIn x =
if board.[x] |> Array.tryFindIndex (fun y -> y = 0y) = None then false
else true
member p.DropIn x =
if not (p.CanDropIn x) then failwith "you tryed to put into a full slot"
else
let idx = board.[x] |> Array.findIndex (fun y -> y = 0y)
let updatedRow = board.[x] |> Array.mapi ( fun y field -> if y = idx then player else field)
let newFields = board |> Array.mapi (fun y row -> if y = x then updatedRow else row)
Position (newFields, (toggle player))
Firs we check if its possible to dropIn at that position we create the new board by mapping the Empty slot we found with the color we were provided. We already have most of the things we need to finish our board representation, which will make writing the AI really easy.
Next time we will encapsulate all this into a class so that it is easier to use and I will show you how we can calculate a reasonable score for a board position. I´m actually still not sure if i should build a class or put all of this into a module. Some input would be very welcome.