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

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

users.softlab.ece.ntua.gr

95 pointsttsiodras30 comments

Very nicely done. Thanks!

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.

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.

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.

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.

And in any case, if it wasn't, if your code is clean you can move fairly easily between OCaml and F#.

Agreed - on all your points. And... glad you liked it :-)

In fairness, modern C# probably looks more functional than what's in this code. For example, it probably would return a Tuple rather than two out parameters. I don't think for a problem of this nature there would be complex object graphs -- those usually come about trying to model enterprise objects and interactions.

You can't move on to OCaml; you can only move back!

I like the idea. And at least this is a post that

- says from the start that the solutions aren't optimal

- shares the code that gives the quoted results right away

- makes it easy to verify/check/contribute

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.

While my F# is rusty, I doubt that this is a good idea, probably neither beautiful nor fast..

Edit: Another couple of comments. Things that weren't immediately obvious to me after reading the blog entry alone:

- 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.

- 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.

Thank you for your kind words. To your points:

- You are right about measuring the startup time of the binaries with "time"; but in this case, where the execution time for F# is measured in the order of ten seconds, the comparisons are still valid and useful, especially in the context of seeing what kind of an impact switching to imperative-style has (10->8, 1.7->1.4, etc)

- Passing the whole board as arguments has little (if any) effect on the execution time: e.g. you can see for yourself that if you pass NO arguments (i.e. clean board) the time ratios between languages remain the same. In a game like Score4, the human has to think anyway - and you can see that using C++, even the nasty cmd-line interface leads to response times of less than a second.

- About F# exceptions: in the absence of "break"... can I do anything else to abort a loop early?

Thanks for your feedback, much appreciated.

You could use a while loop or recursion instead of a for loop. A couple of simple things I noticed is that the complexity of your functional code is higher than the imperative - it shows the speed of ocaml that it was able to get you so much performance.

Although, one way to give some advantage back to F# would be to parallelize your code. Last I checked F# allows you to do this more easily due to constructs like async and agents and .net parallel stuff and in a better way since OCaml has a GIL.

------------

  List.map (abMinimax (not maximizeOrMinimize) (otherColor color) (depth-1)) 
  |> List.map snd

iterates through the list twice. You could just as easily have removed the second List.map.

You can replace (map |> filter) with a fold.

  allData |> List.sortBy getScore |> List.rev |> List.head

could sort by negative score. There are a couple other suggestions I could give to replace the use of reference cells and for loops with recursion, comprehensions, unfolds or folds. Some would not be speed improvements but would yield shorter more colloquial code. But I unfortunately can't afford to donate that time at the moment. Sorry I could not give more concrete advice.

I replaced the exceptions from the functional F# code with mutable flags and while loops - and its speed improved from being 6 times slower than OCaml, to being 5 times slower.

I also replaced the sort with a fold... and there was no speed improvement (the lists are so small it made no difference).

Oh well, what can you do? :-)

It may not speed up F# enough to reach OCaml, but it may be enough to bring C# within range.

The Why Functional Programming Matters[1] paper builds a minimax in a lazy functional language and then enhances it to an alpha-beta.

The minimax looks like:

  evaluate = maximize . maptree static . prune 5 . gametree

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.

The alphabeta is more complicated, but also fits well within a pageful.

[1]: http://www.cs.utexas.edu/~shmat/courses/cs345/whyfp.pdf

I'm sure the OP would appreciate a Haskell implementation optimized for clarity (not for speed). I wonder how speedy that would be.

This is my attempt to translate from the functional OCaml version, focusing on elegancy. If you like to, please help me optimize it while retaining elegancy :) https://github.com/phuc/Score4-haskell/blob/master/Main.hs

Added to the repos - can you please provide your prefered optimization parameters to GHC ? e.g. a Makefile?

Hey ttsiodras, "ghc -O2 Main.hs" should be enough. I've updated the code a bit. It's now half F#'s execution time on my computer :)

Excellent. And committed - I will study your code, Haskell is next on my agenda :-)

So I updated my code to also print out debug. And Haskell now is almost 4 times faster than F# on my computer ;)

Hmm... the scores you printed are not correct (look at the two board edges):

C++: sh -c "time ./bin.release/score4 o53 y43 -debug" Depth 7, placing on 0, score:2 Depth 7, placing on 1, score:8 Depth 7, placing on 2, score:8 Depth 7, placing on 3, score:8 Depth 7, placing on 4, score:8 Depth 7, placing on 5, score:8 Depth 7, placing on 6, score:2 5

Your Haskell code:

sh -c "time ./score4.bin o53 y43 -debug" Depth 7, placing on 0, score 0 Depth 7, placing on 1, score 8 Depth 7, placing on 2, score 8 Depth 7, placing on 3, score 8 Depth 7, placing on 4, score 8 Depth 7, placing on 5, score 8 Depth 7, placing on 6, score 0 5

I'll try to see why your code miscalculates on the two borders, but I don't speak Haskell so don't expect much :-)

Hi ttsiodras, thanks for poiting out :D. I looked at the code and figured out where it went wrong. I discussed my problem further on https://github.com/phuc/Score4-haskell/issues/1. Btw I don't know whether Github notifies everytime I respond. I'm so inefficient at communicating, lol.

Why not work with the code/examples in "Why FP matters"?

Actually, I very much appreciate the fact that he didn't - this way the comparison is more fair - and easier to follow for people new to functional programming (like me).

Well, I think it's nice to take the best representative of each language, and not some arbitrary point. That way the comparison is more meaningful, and people can learn more from the code.

Stay tuned. I will do the one in this paper once I have time ;)

For fun I did a trivial translation of the C++ version to Go.

Results (with gcc 4.2 -03 -mtune=native -DNDEBUG, head Go -B, Ocamlopt 3.12.0 -unsafe -rectypes -inline 1000):

C++: 0m0.611s

OCaml: 0m1.457s

Go: 0m1.043s

This is on a Macbook Pro 2.53 Ghz Core 2 Duo running OS X 10.5.8.

Go source: http://pastie.org/2199969

(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.)

Ah. Looks like he updated the C++ version to have the optimization I spoke of. So, here's the matching Go version: http://pastie.org/2202611

Time: 0m0.796s

Committed to the repository - thanks!

Ah. Ok then. I spent another few minutes with it after I posted that and made it a little nicer, but not particularly faster: http://pastie.org/2202963

May want to use that instead.

Added it, thanks.

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.

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.

Me too: It took me two failed attempts before my third version (the current incarnation of scoreBoard), could finally best me.

Reply on news.ycombinator.com