Hi all,
this is basically a continuation of my previous thread "Functional
performance vs imperative complexity"...for those of you who are still
interested here is what I learnt during the process. I should note that
i finally got the performance I was after without sacrificing any
immutability at all! so , how did I do that after all that moaning and
complaining? well, if I'm honest I *cheated* !!! let me explain:
first some history:
--precalculating all the logical moves of chess pieces (except pawn)
had a dramatic improvement (cheat #1)
--after realizing that i should not be starting the search at depth 4
but at depth 3 instead (because the algorithm only starts searching on
the children of the root node - that means that whenever i was starting
with 4 it was actually going down to level 5), time went down
dramatically. apparently, combinatorial explosion dominates after level 4.
--so, in essence i was able to go down to level 4 in roughly 12 sec, but
without checking if the king is left exposed! as soon as i added that
check (on every single move) time went back up to 5 minutes! you can
easily see why that is (for every move you have to check all the
opponents moves)...essentially it goes another level down on every node!).
so again i was very disappointed with performance...this is where cheat
#2 comes in! I don't really need to check if a move exposes the king
during search do I? I only need to check this when people are playing on
the actual gui...not while searching the game-tree!!! I CAN CHEAT! *I
can give the king a ridiculously high value (100 or 1000) and skip the
'exposes?' check!* so, yes, on the way down it will explore a move which
exposes the king but , on the way up, it will simply NOT choose it!!!
there is no way losing 100 points can be compensated! now, of course
this is for the naive static evaluator...I need to slightly alter when a
game ends in order to have the same behaviour working with a different
eval. function that doesn't consider the pieces values. and I can cheat
again!!!
very simply:
I need to end the game when some team is missing a king!!! as opposed to
looking whether the king is threatened and whether he cannot move
(checkmate)! It is also cheaper, to say 'give me the 2 kings and
whichever is nil the other is the winner', than 'give me all the moves
of this team to check if some threatens the king and then give all the
moves of the king to check if he can escape'. Of course for the gui, we
might want the fancy version that ends the game a la checkmate, but for
training genetically merely ending the game when someone loses his king
suffices!!! That organism that gave up his king will simply not evolve
(cheat #4)!!
Presumably i don't have to tell you that I'm now back down to 12 sec
which makes me very happy and everything works great!
so what is the lesson?
you don't really need the right algorithm - you just need to cheat!!!
(half-joking) :-)
Jim
ps: checkers goes down to level 6 potentially 8 quite easily...of
course in checkers half the time you MUST make a jump so the whole team
has a single move, so things are indeed very different.
--
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
