5 ms·
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:
by Peaker 15y ago
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 http://www.cs.utexas.edu/~shmat/courses/cs345/whyfp.pdf
- loup-vaillant 15y agoI'm sure the OP would appreciate a Haskell implementation optimized for clarity (not for speed). I wonder how speedy that would be.
- phnguyen 15y agoThis 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 https://github.com/phuc/Score4-haskell/blob/master/Main.hs
- Peaker 15y agoWhy not work with the code/examples in "Why FP matters"?
- ttsiodras 15y agoActually, 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).
- ttsiodras 15y agoAdded to the repos - can you please provide your prefered optimization parameters to GHC ? e.g. a Makefile?
- phnguyen 15y agoHey 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 :)
- ttsiodras 15y agoExcellent. And committed - I will study your code, Haskell is next on my agenda :-)
- phnguyen 15y agoSo I updated my code to also print out debug. And Haskell now is almost 4 times faster than F# on my computer ;)
- ttsiodras 15y agoHmm... 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 :-)
- phnguyen 15y agoHi 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 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.