AI: Playing Score4 in functional and imperative style (C++,OCaml,F#,C#)

Very nicely done. Thanks!<p>Just scanning the code, I think showing C++ rocks is pretty much a no-brainer (ducks to avoid food fight) but part of what's happened here, I'll bet, is that you've stayed within the default heap size allocated by the compiler.<p>It's just a nit, and it's an easy fix too, but I wanted to point that out. The .NET examples are probably doing some mem-safe allocations each trip around, while the C++ is just burning through what it already has.<p>Also there's another point that needs to be drawn out: your code is much cleaner in imperative because you've solved it functionally first. Most imperative programmers wouldn't write anything that looked like what you did. OO guys would still be constructing object graphs. The language you choose plays a major role in how you solve problems.<p>As far as the F# speed difference, I've struggled with staying with F# or moving on to OCaml. Right now, I think I'd rather have more libraries and slower speed, so I'm staying with F#. For some reason OCaml seems to be a tougher language to pick up -- the community is a bit scattered and finding help on easy topics isn't easy (at least for me). Plus I like the fact that a lot of stuff developed in Windows for .NET can just plop over in linux and still work. That's worth a bit of speed.<p>And in any case, if it wasn't, if your code is clean you can move fairly easily between OCaml and F#.

I like the idea. And at least this is a post that<p>- says from the start that the solutions aren't optimal<p>- shares the code that gives the quoted results right away<p>- makes it easy to verify/check/contribute<p>First thing I notice though is that it's (looking at the functional F# code) using exceptions for control flow. It seems the author uses a 'NoMoreWork' exception as a kind of break out of a loop.<p>While my F# is rusty, I doubt that this is a good idea, probably neither beautiful nor fast..<p>Edit: Another couple of comments. Things that weren't immediately obvious to me after reading the blog entry alone:<p>- The make benchmark passes really just one board with two moves to an executable. Just like the time commands before. So what we're measuring is the startup time of the process (native vs. managed/clr) and the cost to find a single/first move.<p>- The whole engine thing is designed around the concept of 'I pass the whole board as arguments'. So the driver seems to compute a string representation of the board after each move and _create a new process of the engine_. So - yes, this is a bad idea for managed code. Or anything that could otherwise use JIT.

The Why Functional Programming Matters[1] paper builds a minimax in a lazy functional language and then enhances it to an alpha-beta.<p>The minimax looks like:<p><pre><code> evaluate = maximize . maptree static . prune 5 . gametree </code></pre> maximize finds the maximum value. static is a heuristic analysis of the value of the board. prune cuts the tree to a certain depth. gametree generates the infinite game tree.<p>The alphabeta is more complicated, but also fits well within a pageful.<p>[1]: <a href="http://www.cs.utexas.edu/~shmat/courses/cs345/whyfp.pdf" rel="nofollow">http://www.cs.utexas.edu/~shmat/courses/cs345/whyfp.pdf</a>

For fun I did a trivial translation of the C++ version to Go.<p>Results (with gcc 4.2 -03 -mtune=native -DNDEBUG, head Go -B, Ocamlopt 3.12.0 -unsafe -rectypes -inline 1000):<p>C++: 0m0.611s<p>OCaml: 0m1.457s<p>Go: 0m1.043s<p>This is on a Macbook Pro 2.53 Ghz Core 2 Duo running OS X 10.5.8.<p>Go source: <a href="http://pastie.org/2199969" rel="nofollow">http://pastie.org/2199969</a><p>(With a trivial optimization, the Go version can be improved by ~13%, but I decided not to do that because it'd be a slightly different algorithm.)

Ocaml was the first functional language I ever used. I always heard it was fast. I didn't realize it was that fast. That I think is the most interesting thing about this post. I know he says C++ is significantly faster than the other languages. But, I think most people would agree its much easier to solve harder problems quicker in Ocaml thank C++.

I implemented this in java when I first learned about minimax in an AI class, so this all looks very familiar to me.<p>My scoring function must have been weak though. I remember being frustrated that I could still beat the algorithm. It was completely blind to traps that didn't matter in the near term, but that decided the game later when the board was filling up.