Hi all,
I really need your advice/help with something I was not expecting! let
me explain...
after spending almost a week experimenting with different designs for my
chess minimax algorithm, I settled down on a design that I like. I like
it because it is rather functional (as opposed to my Java one 3 years
ago) and at least in theory, most of the job should be done in parallel.
To be hoenst it never occurred to me to use hash-maps for such a purpose
until I realised that a purely 'looping via map' -approach would not
allow me to keep track of the indices easily so even though i would have
the numeric result easily, I would not know which move this result
originated from. So, that is where it occurred to me to nest hash-maps
(instead of seqs via mapping) where I can always keep the originating
node as a key. I do think my solution is quite elegant and completely in
line with the functional lessons/obsessions/practices etc etc and for
that I'm really happy...Of course you can argue the oppposite - no
problem about that...:-)
As i was saying the design is pretty and elegant (and
lazy!)...Unfortunately it is terribly slow! I mean unbelievably
slow...4-5 min to reach level 4? How am I ever going to train by
evolutionary means if searching takes so much time is beyond me! Ok
let's see inside:
the core algorithm is here:
-------------------------------------------------------------------------------------------------------------------------------
(defn game-tree
"Generate the game tree up to a level lazily (via 'map')."
[root? dir board successors-fn depth]
{:node board
:direction dir
:children (if (zero? depth) '()
((if root? pmap map) ;start futures at the top via pmap
#(game-tree false (- dir) % successors-fn (dec depth))
(successors-fn board dir)))})
(defn search "The recursion of min-max algorithm."
[eval-fn tree]
(letfn [(minimize [tree] (if (seq (:children tree))
(apply min
(map #(maximize %) (:children tree)))
(eval-fn (:node tree) (:dir tree))))
(maximize [tree] (if (seq (:children tree))
(apply max
(map #(minimize %) (:children tree)))
(eval-fn (:node tree) (:dir tree))))]
(minimize tree)))
(defn evaluator
"Returns a fn that expects a tree to start searching using this eval-fn."
[eval-fn]
(fn [t]
(search eval-fn t)))
(defn best-next-state
"Get the best next state for the given game tree."
[tree eval-fn]
(->> (:children tree)
(apply max-key (evaluator eval-fn))
(:node)))
(defn next-level
"Generate the next level of the tree using b as the current state."
[b dir]
(let [team (filter #(= dir (:direction %)) b) ;all the team-mates (with
same direction)
team-moves (concat (for [piece team
coords (core/getMoves piece)]
(core/dest->Move @curr-game piece coords)))]
(vec (map core/try-move team-moves))))
--------------------------------------------------------------------------------------------------------------------------
As you can see all the usual suspects are there...letfn, pmap, max-key,
closures etc etc. I thought it was rather clever using pmap when
branching out from the root node but it turns out it only makes a tiny
positive difference overall (20-30 sec)...also looking at mu cpus, not
all of them are working even though there is so much work to be done on
each branch (where futures were created). Is pmap just too good to be
true? It is the first time i am using it seriously...
Or am I looking at it completely the wrong way here? I mean, I have done
this before in Java but it was only for checkers - not chess...we all
know that chess has a staggering branching factor especially as soon as
the game opens up a bit. Is it perhaps plain naive hoping to reach at
least level 6 in reasonable time (< 2min) functionally?
I really want to hear your thoughts especially if someone has done
anything similar...I honestly wish i had started coding checkers first
so I could compare with the Java one! at least i would knew whether to
pursuit it further or not...
thanks a lot for your patience and looking forward to comments :-)
Jim
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
