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#.
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.
- 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.
- 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?
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.
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).
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.
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.
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.
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
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.
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#.