Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Fairy
        
(Message started by: Swynndla on May 14^th, 2006, 6:10pm)

Title: Fairy
Post by Swynndla on May 14^th, 2006, 6:10pm

Hi unic ... in a game comment (Game 31561) you said:

Quote:

=== 95/12.4/17 -649 8466018 2808700 26.25 (ee3e ef3w Mf2n Mf3x) re2e Eb3e mb2n Ec3n mb3e mc3x ee3s He4s He3e Hf3x ee2n He5n He6s He5e

and:

Quote:

=== means it has finished a nominal search depth. 95 is the nominal search depth... 10 = 1 step. (It increments this by 5 at a time, which makes sense due to search extensions of partial steps.) 12.4 is the average actual depth evaluations were made at. 17 is the deepest depth reached. -649 is its evaluation. A rabbit is 1000, a camel 5000. The next three numbers are number of nodes visited, number of evaluations made, and time in seconds used. Rest is the Principal Variation - the sequence of moves that Fairy is expecting.

and:

Quote:

Average depth that positions were evaluated at was 12.4 steps. I don't know lowest - but at a guess, 8 or 9 steps or so. Deepest was 17 steps. Nominal search depth was 95, which means that almost (except for negative search extensions, see below) all positions were searched to at least (95/10, rounded up) 10 steps depth.

Nodes includes internal (non-terminal nodes) in the search tree, which do not cause a call of the evaluation function. Also, some terminal nodes (i.e. a hash hit (fairly common), win by goal, or win by immobilization) don't cause a call to the evaluation function.

Pruning is not done currently... I have some ideas for it that I do want to try out in the future - but want to improve its evaluation function first.

What is done is search extensions. Mostly, this causes Fairy to search "interesting" lines deeper (which is why the average depth is a couple of steps deeper than the depth indicated by the nominal depth). In some cases though, Fairy thinks a line looks very uninteresting and then it will do a negative extension, i.e. search that branch slightly less deep.

This in very interesting stuff!

So if Fairy took 26 seconds to search 12 steps on average, then that's 3 ply (if 1 ply is a 4-step turn).

I'm comparing this to Gnobot_2005 and Gnobot_2006 from this post:
http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display;num=1145410863
.... ie
Quote:

Gnobot:
1 ply - less than 1 sec
2 ply - about 5 sec, but varies quite a bit with the position
3 ply - about 4 minutes, but varies quite a bit...
4 ply - no chance

... I'm not trying to run any bot down, I'm just trying to understand ... if Fairy looks 3 ply in 26 seconds, then if that position (from the game you were commenting on) is a typical one, then it's a lot faster than Gnobot (which doesn't use pruning either). Why is this? What languages were the two bots programmed in? How does this compare to other bots? I'd be interested in other people's comments.

Title: Re: Fairy
Post by unic on May 14^th, 2006, 6:42pm

You can't really compare an average evaluation depth to a minimum evaluation depth. Say we have eleven nodes at ten ply. One of them gets extended a step, yielding ten new nodes. That means we have 10 nodes evaluated at a depth of 10 steps, and 10 nodes evaluated at a depth of 11 steps... so an average evaluation depth of 10.5. On the other hand, only one eleventh of the tree was searched to a depth of 11, so one could argue that this corresponds to a depth of 10.09.

With several extensions going on, the difference gets even more extreme. Hash hits further confuse the numbers. My point is that what you want to compare is the nominal depth in steps... in which case my figures are close to GnoBot's - perhaps a low factor (2-3) slower or quicker... hard to say without comparing a specific position.

Also, search depth is highly dependent upon the position in question. In the opening position, Fairy reaches a nominal depth of around 120 (=12 steps = 3 ply)... in a complicated midgame position, the nominal depth might be only be around 80 (=8 steps = 2 ply) (or even less). Though hopefully the extensions means it will have looked at critical variations a bit longer than that.

So, from the start position, I get:

Code:

c:\Dev-Cpp\unic\arimaa>arimaa startpos.txt
Hash-table turned off.
Entries in hashtable : 16777216
Hash mask : 0XFFFFFF
Memory reserved : 536870912
Evaluating traps:
c6 is worth Gold (0) - Silver (150).
f6 is worth Gold (0) - Silver (150).
c3 is worth Gold (150) - Silver (0).
f3 is worth Gold (150) - Silver (0).
a8 is worth 995 due to being immobile.
b8 is worth 995 due to being immobile.
c8 is worth 995 due to being immobile.
d8 is worth 995 due to being immobile.
e8 is worth 995 due to being immobile.
f8 is worth 995 due to being immobile.
g8 is worth 995 due to being immobile.
h8 is worth 995 due to being immobile.
a1 is worth 995 due to being immobile.
b1 is worth 995 due to being immobile.
c1 is worth 995 due to being immobile.
d1 is worth 995 due to being immobile.
e1 is worth 995 due to being immobile.
f1 is worth 995 due to being immobile.
g1 is worth 995 due to being immobile.
h1 is worth 995 due to being immobile.
Material value Gold (45560) - Silver (45560)
Trap value Gold (300) - Silver (300)
Rabbit value Gold (0) - Silver (0)

Searching position:
Move 2, Step 0, Gold at move.
+-----------------+
8| r r r r r r r r |
7| h d c m e c d h |
6| . . - . . - . . |
5| . . . . . . . . |
4| . . . . . . . . |
3| . . - . . - . . |
2| H D C M E C D H |
1| R R R R R R R R |
+-----------------+
a b c d e f g h
Hashkey: 0X1753B73F19826A48

Remaining time: 120.00
Allocated time: 60.00
Depth Value Nodes Evals Time PV
5........ 5 2 1 0.01 Ha2n
5........ 21 4 2 0.01 Db2n|
5........ 36 7 4 0.01 Md2n|
5........ 38 9 5 0.01 Ee2n|
=== 5/ 1.0/ 1 38 12 8 0.01 Ee2n|
10........ 38 14 8 0.01 Ee2n|
=== 10/ / 38 21 8 0.01 Ee2n|
15........ 74 41 23 0.01 Ee2n Md2n|
=== 15/ 2.2/ 4 74 119 74 0.01 Ee2n Md2n|
20........ 74 136 74 0.01 Ee2n Md2n|
=== 20/ 2.3/ 4 74 236 87 0.01 Ee2n Md2n|
25........ 80 457 214 0.01 Ee2n Md2n Rd1n|
=== 25/ 3.1/ 4 80 1126 518 0.01 Ee2n Md2n Rd1n|
30........ 80 1362 529 0.01 Ee2n Md2n Rd1n|
=== 30/ 3.2/ 4 80 2268 636 0.01 Ee2n Md2n Rd1n|
35........ 372 4294 1489 0.03 Ee2n Ee3n Ee4n Ee5n|
=== 35/ 4.0/ 4 372 8740 3100 0.03 Ee2n Ee3n Ee4n Ee5n|
40........ 372 11081 3271 0.05 Ee2n Ee3n Ee4n Ee5n|
=== 40/ 4.0/ 4 372 17387 4015 0.05 Ee2n Ee3n Ee4n Ee5n|
45........ 322 20564 4851 0.06 Ee2n Ee3n Ee4n Ee5n dg7s|
=== 45/ 5.0/ 5 322 28496 6308 0.08 Ee2n Ee3n Ee4n Ee5n dg7s|
50........ 322 31866 6569 0.08 Ee2n Ee3n Ee4n Ee5n dg7s|
=== 50/ 5.0/ 5 322 40627 7436 0.09 Ee2n Ee3n Ee4n Ee5n dg7s|
55........ 322 44071 7512 0.09 Ee2n Ee3n Ee4n Ee5n dg7s|
=== 55/ 6.1/ 8 322 53037 7727 0.09 Ee2n Ee3n Ee4n Ee5n dg7s|
60........ 236 57323 8594 0.11 Ee2n Ee3n Ee4n Ee5n md7s ee7w|
=== 60/ 7.5/ 8 236 67647 9990 0.13 Ee2n Ee3n Ee4n Ee5n md7s ee7w|
65........ 236 72132 10271 0.14 Ee2n Ee3n Ee4n Ee5n md7s ee7w|
=== 65/ 7.6/ 8 236 83293 11132 0.14 Ee2n Ee3n Ee4n Ee5n md7s ee7w|
70........ 125 89309 12448 0.16 Ee2n Ee3n Ee4n Ee5n dg7s cf7s ee7e|
=== 70/ 6.9/ 8 125 102942 14895 0.20 Ee2n Ee3n Ee4n Ee5n dg7s cf7s ee7e|
75........ 125 109979 16016 0.22 Ee2n Ee3n Ee4n Ee5n dg7s cf7s ee7e|
=== 75/ 7.7/ 8 125 123574 16056 0.22 Ee2n Ee3n Ee4n Ee5n dg7s cf7s ee7e|
80........ 104 133664 18356 0.25 Ee2n Ee3n Ee4n Ee5n dg7s cf7s ee7e db7s|
=== 80/ 7.5/ 8 104 150927 20909 0.28 Ee2n Ee3n Ee4n Ee5n dg7s cf7s ee7e db7s|
85........ 104 164271 22811 0.31 Ee2n Ee3n Ee4n Ee5n dg7s cf7s ee7e db7s|
=== 85/ 8.5/10 104 180955 23455 0.33 Ee2n Ee3n Ee4n Ee5n dg7s cf7s ee7e db7s|
90........ 199 212212 33069 0.42 Ee2n Ee3n Ee4n Ee5n dg7s db7s cf7e ee7e Ee6w|
=== 90/ 9.0/10 199 261044 48328 0.56 Ee2n Ee3n Ee4n Ee5n dg7s db7s cf7e ee7e Ee6w|
95........ 199 309105 59058 0.67 Ee2n Ee3n Ee4n Ee5n dg7s db7s cf7e ee7e Ee6w|
=== 95/10.0/12 199 367421 65069 0.75 Ee2n Ee3n Ee4n Ee5n dg7s db7s cf7e ee7e Ee6w|
100........ 258 536377 119588 1.25 Ee2n Ee3n Ee4n Ee5n dg7s db7s cc7w md7w Md2n Dg2n|
===100/10.3/12 258 842889 219817 2.13 Ee2n Ee3n Ee4n Ee5n dg7s db7s cc7w md7w Md2n Dg2n|
105........ 264 1298003 362029 3.36 Ee2n Ee3n Ee4n Ee5n dg7s db7s cc7w md7w Md2n Re1n Dg2n|
===105/11.0/12 264 1716005 426854 4.06 Ee2n Ee3n Ee4n Ee5n dg7s db7s cc7w md7w Md2n Re1n Dg2n|
110........ 264 2394553 615443 5.72 Ee2n Ee3n Ee4n Ee5n dg7s db7s cc7w md7w Md2n Re1n Dg2n|
===110/11.1/12 264 3769175 1004117 9.11 Ee2n Ee3n Ee4n Ee5n dg7s db7s cc7w md7w Md2n Re1n Dg2n|
115........ 381 7487834 1924344 17.41 Ee2n Ee3n Ee4n Ee5n dg7s db7s cc7s md7w Hh2n Hh3n Hh4n Hh5n|
===115/11.9/13 381 16226668 4071994 37.38 Ee2n Ee3n Ee4n Ee5n dg7s db7s cc7s md7w Hh2n Hh3n Hh4n Hh5n|
Hash writes : 5031883 (783640 upper-bounded values, 176071 lower-bounded values, 4072172 exact values)
Hash hits : 11482905 Hash values used : 11194785 (97.5%)
PV moves tried: 129 Invalid PV moves: 0 Good PV moves: 127 Cutoff PV moves: 0
Killer moves tried: 959444 Invalid killer moves: 737480 Good killer moves: 174937 Cutoff killer moves: 174892
Hash moves tried: 140942 Invalid hash moves: 0 Good hash moves: 343 Cutoff hash moves: 343
Shallow moves tried: 36 Invalid shallow moves: 0 Good shallow moves: 1 Cutoff shallow moves: 1
Scout searches done: 2358 Researches done: 57 (2.4%)

... notice how the nominal depth 80 search (=8 steps = 2 ply) has an average search depth of 7.5 - due to the negative extensions of lines where a player kills one of his own pieces. This shares similarities with pruning... but is not quite as drastic - instead of fully cutting away a line, I only search it to a shallower depth.

Either way, if you (or anybody else) have more questions about Fairy, feel free to ask them, and I will do my best to answer them :)

(One point to note is that Fairy is a moving target though - I work on it every day... some days just a little, other days for several hours... so anything I write might be out of date in a week or two.)

Title: Re: Fairy
Post by Swynndla on May 14^th, 2006, 7:23pm

Very interesting!

Thanks for explaining the details to me ... it makes sense now.

Quote:

Very interesting ... I'm not sure if any other bot on here does that.

Title: Re: Fairy
Post by 99of9 on May 14^th, 2006, 8:58pm

on 05/14/06 at 19:23:52, Swynndla wrote:

Very interesting ... I'm not sure if any other bot on here does that.

I tried something like that with gnobot, but ran into troubles:
Gnobot occasionally deliberately suicided a rabbit, because that would bring the horizon along that line a little closer, so that it wouldn't see the forced camel capture the opponent was about to execute.

So for gnobby it was a serious case of hiding your head in the sand.

I'm glad you've got it working in fairy.

Title: Re: Fairy
Post by unic on May 19^th, 2006, 4:34pm

on 05/14/06 at 20:58:57, 99of9 wrote:

I'm glad you've got it working in fairy.

... working and working - this (negative) extension is the first thing I'm running a match to test, and so far, the version with the extension and the version without it are roughly the same - sometimes, one will be ahead, sometimes the other. Neither is showing a statistically significant advantage.

So, in some positions, it probably runs into problems similar to what GnoBot had and therefore plays weaker, while in other positions, it sees a little further and therefore plays stronger.

Title: Re: Fairy
Post by Swynndla on May 20^th, 2006, 7:49pm

Unic, would Fairy be able to see the winning move on move 47b?:
http://www.arimaa.com/arimaa/gameroom/comments.cgi?gid=27019

... or would the "shallow depth" search mean that Fairy wouldn't see it for weeks?

Not that this type of move comes up very often in games! ... this is an extreme example ... I'm just curious if Fairy would find the move, and how long it would take.

Title: Re: Fairy
Post by unic on May 21^st, 2006, 3:29pm

on 05/20/06 at 19:49:39, Swynndla wrote:

... or would the "shallow depth" search mean that Fairy wouldn't see it for weeks?

Shallower search depth doesn't come into it in this position - the move that directly causes the elephant to be captured is one of the opponent's.

It only looks shallower when one of its own moves leads to the immediate (not future) capture of one of its own pieces. (Or corresponding for the opponent.)

After roughly two minutes, Fairy has:
===100/11.6/16 5752 42241491 15640902 124.03 hc4s Cc2s hc3s ra8e rb4e Db3n Rh2n (pass) rd7s dd3e de3w Re2n|
... so it hasn't seen the winning line yet. I'll leave it thinking about the position and see what it comes up with.

Title: Re: Fairy
Post by Swynndla on May 21^st, 2006, 3:37pm

Ahhhh thanks for explaining that Unic ... so what about positions where the winning line is to put you phant in an unprotected trap straight away ... in order to clear a path for a rabbit to goal ... would Fairy see this if it was a one move goal? ... it would right? ... but not if the forced goal was 3 ply? (ie the forced goal might be: Gold sacrifices it's elephant and pushes rabbit, Silver moves, Gold pushes and goals).

Title: Re: Fairy
Post by unic on May 22^nd, 2006, 5:50am

After close to 8 hours, fairy sees the line played in the game - but sees no forced win yet. It is suggesting a different defence for gold than what occured in the actual game.

+++
140........ 5915 -1030673039 -1349685994 28473.52 Rd2s dd3s rf3w ef4s Db3s Cc2s Rd1e Cc1n Cc2n Cc3x dd2w ef3n re3w Df8s Ra4n Db2n Rh2n|

Setting up the position after gold's defensive move Db3s Cc2s Rd1e Cc1n, Fairy can see a forced win:

+++
95........ 499616 30768262 13354022 98.41 Cc2n Cc3x dd2w re3w ef3x rd3s Eg3w Ef3w Ee3w Re1w dc2s dc1n Rd1w rd2s|
=== 95/11.5/16 499616 51280521 21159882 157.41 Cc2n Cc3x dd2w re3w ef3x rd3s Eg3w Ef3w Ee3w Re1w dc2s dc1n Rd1w rd2s|

... notice how Fairy sees this winning line despite it having to sacrifice its own elephant! And it's a 12-ply line, yet gets seen at a depth of 9.5 ply... (or steps - but I think calling each step a ply is logical, as ply really means a layer in the search, and in Fairy, each step is a layer), because positive search extensions outweigh the negative one from capturing its own elephant.

According to Fairy, this is a more resilient defence than what occured in the game... Silver makes goal in the same number of moves, but in a larger number of steps.

I might at some point leave it running for a longer time on the original position... to see when (if) it can see the forced win - but at least it was able to find the right move in the end.