Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Bot Performance
        
(Message started by: speek on Jul 22^nd, 2010, 8:31am)

Title: Bot Performance
Post by speek on Jul 22^nd, 2010, 8:31am

I hesitate to ask because I don't want to start a bragging contest, but I've been working on my Arimaa game processing (it's not a bot yet, I'm just getting the mechanics down), and I'm basically wondering if I'm in the ballpark performance-wise.

I'm disappointed with my results so far compared with previous efforts with a chess engine, but then I guess that's what happens when there are on average 17,000 moves per ply vs 30-40. But it still seems I must be doing something wrong. For generating all possible unique moves for a given position, I'm only processing about 500 positions per second. With chess, this number would be more like 150,000 (or more, that was 3-4 years ago). How do bots perform on average with arimaa and generating legal and unique move lists (not steps, but rather, full moves)?

Title: Re: Bot Performance
Post by rbarreira on Jul 22^nd, 2010, 8:52am

I haven't benchmarked the specific number you ask for, but it seems to be more or less the same as the number of nodes where a position is evaluated, i.e. a leaf node in the search tree (on a bot with no quiescence search like mine).

With that assumption, I just benchmarked the number of calls to evaluate and I'm getting a number of 280,000 per second. Considering that the evaluation function is taking up about 50% of the run time, the speed would be doubled if evaluation came for free (i.e. if the bot spent time mostly on move generation and other search-related stuff). So for me, a very rough answer would be 560,000 per second.

This was on a 2.27 GHz 32-bit system with one core, it would probably go up by 1.7-2x on a 64-bit system.

What programming language are you using?

Title: Re: Bot Performance
Post by speek on Jul 22^nd, 2010, 9:04am

If I understand you right, you're saying that your bot is generating and calling evaluation on 280,000 positions/second. In my case, I'm saying I'm generating all the legal full moves of a given position - 500/second, which, if average number of legal moves from a given position is around 17,000 that means I'd be calling evaluation 500 * 17,000, which is 8,500,000 evaluations/second. Of course, my currently non-existent evaluation function is extremely fast, but this does not seem right either. However, it does suggest I'm in the ballpark.

That is, if I understand you right, which I'm really not sure about :)

I'm using Java, btw.

Title: Re: Bot Performance
Post by rbarreira on Jul 22^nd, 2010, 9:31am

Oh, I had misread what you said.

I don't have an optimized function for generating all unique moves from a position, but from a quick test it seems my bot's doing about 250 positions per second (on a position with only 1263 unique moves).

So I'd say your code may actually be faster than mine, and in any case you're definitely in good shape (at least when compared to me).

Title: Re: Bot Performance
Post by speek on Jul 22^nd, 2010, 9:45am

Thanks, I just felt the need for a sanity check - it's so different from chess just because of the sheer size of the search tree.

Also, I read in the forum about bots that search 2-ply and I wondered, do they mean a full-width 2-ply? How do they do that? That would be 100+ million positions.

Title: Re: Bot Performance
Post by rbarreira on Jul 22^nd, 2010, 10:01am

on 07/22/10 at 09:45:26, speek wrote:

The good part is that you rarely have to generate all the unique moves from a position, either by using step-by-step search, or by generating moves in batches instead of all at once (I think almost everyone is using the former solution). Whenever there's a cutoff in the search, you will avoid generating a lot of moves below that node.

A full-width 2-ply search is not hard to do once you have alpha-beta implemented. Transposition tables help a lot too if you're doing step-by-step search (in order to eliminate repeated positions). It takes just a few seconds even in bad cases on my bot (on a faster system than the one I used for the tests above).

Title: Re: Bot Performance
Post by speek on Jul 22^nd, 2010, 10:31am

Well, I do eliminate duplicate positions as they arise during the step-by-step search process, so I don't even allow those steps to make it into my step storage buffer. As for alpha-beta, I'm not there yet, as I am just generating the legal moves of a single position and trying to optimize my memory and cpu usage while doing so.

I noticed some talk about doing evaluations and alpha-beta cutoffs on a step-by-step basis as opposed to a move-by-move basis. I was automatically going for move-by-move before I read that. Most bots do it step-by-step though, right?

Title: Re: Bot Performance
Post by rbarreira on Jul 22^nd, 2010, 10:42am

Yes, most bots do search step-by-step (including cutoffs), which is simpler to program efficiently. An efficient move-based search would have to be very careful not to waste too much time generating moves that will never be looked at. Doing it step-by-step, at most you'll waste a few dozen generated steps when a cutoff happens. Then there are other potential reasons to do it step-by-step, for example many people have found that it pays off to do iterative deepening on a step-by-step basis.

For this reason, if I were you I wouldn't worry too much about optimizing a function which generates all unique moves from a position - you probably will end up not using it in the time intensive parts of your bot. For me, the important parts to focus on were step generation and generating a resulting game state from a single step.

Title: Re: Bot Performance
Post by Fritzlein on Jul 22^nd, 2010, 1:47pm

on 07/22/10 at 10:42:55, rbarreira wrote:

Yes, most bots do search step-by-step (including cutoffs), which is simpler to program efficiently.

Note, however, that there can be no alpha-beta cutoffs in the first ply, i.e. the first four steps. Only after the side to move changes does an alpha-beta cutoff even make sense. So searching step-by-step creates no payoff in the first ply.

For later plies, my understanding is that better move ordering can make alpha-beta searching hugely more efficient, so iterating by steps is worth it for the move-ordering alone. Furthermore, if the branching factor is 2^14, each additional ply of search depth should take 2^7 times longer than the previous. How often are you going to have over a hundred times longer to think about another ply? Iterating just one step deeper, however, gives you a real chance of completing that iteration. So while step-by-step search gives you nothing on the first ply, it can pay huge dividends on later ply.

Quote:

I wouldn't worry too much about optimizing a function which generates all unique moves from a position - you probably will end up not using it in the time intensive parts of your bot. For me, the important parts to focus on were step generation and generating a resulting game state from a single step.

By the way, how much time do you spend in move (or step) generation? I'm guessing it is 5-10%.

Title: Re: Bot Performance
Post by speek on Jul 22^nd, 2010, 2:53pm

rbarreira mentioned he spends about 50% of his time in evaluation. So I would guess at least 25% of the time is in move/step generation, and probably more.

Title: Re: Bot Performance
Post by rbarreira on Jul 22^nd, 2010, 9:47pm

on 07/22/10 at 13:47:43, Fritzlein wrote:

By the way, how much time do you spend in move (or step) generation? I'm guessing it is 5-10%.

A bit less than 5%, after all the optimizations.

10%+ on transposition table stuff (looks a bit high, then again it's accessing RAM so...).
15% on search.
15% on move making. (incrementally updates some stuff to help the evaluation too)
40%+ on evaluation.

Roughly.

Title: Re: Bot Performance
Post by speek on Jul 23^rd, 2010, 7:10am

What does "search" refer to?

Title: Re: Bot Performance
Post by rbarreira on Jul 23^rd, 2010, 9:23am

Things like checking the repetition/mandatory board change rules, the killer-moves heuristic, checking for terminal states, the alpha-beta algorithm itself etc.

Title: Re: Bot Performance
Post by rbarreira on Jul 26^th, 2010, 4:30am

I was thinking about this thread the other day and realized that the reason for my apparently bad performance result - considering the position had so few legal moves - should be because I don't check for repeated states except at the leaf nodes (in the move generation that is).

So for example when generating the 4 step moves, redundant permutations of the first three steps will all live on to generate the last step. For a position with many unique moves it could effectively be generating millions of redundant permutations.

Did you optimize for this in your code? I don't plan to since I don't use this code in the search as I said earlier. But if you did, you might be able to remove that optimization if you're still interested in knowing where your step generation's performance stands.

Otherwise, I think the only easy way to compare performance in alpha-beta bots is really the number of nodes per second in an actual search. And even that has its limits, due to heavier/lighter eval, etc.

Title: Re: Bot Performance
Post by speek on Jul 26^th, 2010, 9:18am

I do weed out repeated positions as they arise in the step search to avoid generating steps that are redundant. By doing so, it generates about 1.8 million unique positions/sec. I am happy with that, as that little amount of time is going to get swamped by evaluation time. I did a little test for a simple eval function, and it dropped that number right down to less than 100,000/sec.

Thank you for your help, btw.

Title: Re: Bot Performance
Post by jdb on Jul 26^th, 2010, 10:01am

Here is the test case from clueless for the routine to generate all unique moves for a position. The ones with 300K legal moves take around .25 sec each on my machine. The position text is the same as the one used by the arimaa server. To get something human readable replace "%13" with "/n".

Code:

package arimaa3;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class GenTurn2Test {

private GenTurn2 turn;
private long result[];

@Before
public void setUp() throws Exception {
turn = new GenTurn2();
result = new long[800000];
}

String text[] = {
"10w %13 +-----------------+%138| r r r r r |%137| r m c c h r r |%136| d d |%135| E |%134| |%133| H e D |%132| R C C R |%131| R R R D M R R R |%13 +-----------------+%13 a b c d e f g h%13TS: 80%13",
"21w %13 +-----------------+%138| r r r r |%137| r m h c r r |%136| d E d |%135| r |%134| |%133| H e D |%132| R C C R |%131| R R R M R R R |%13 +-----------------+%13 a b c d e f g h%13TS: 168%13",
"22w %13 +-----------------+%138| r r r r |%137| r m h c r r |%136| d E d |%135| r |%134| |%133| H e D |%132| R C C R |%131| R R R M R R R |%13 +-----------------+%13 a b c d e f g h%13TS: 176%13",
"6b %13 +-----------------+%138| r r r m r r r |%137| r c d r |%136| h c h |%135| d E |%134| |%133| H H e M |%132| D D R C C |%131| R R R R R R R |%13 +-----------------+%13 a b c d e f g h%13TS: 52%13",
"23b %13 +-----------------+%138| r r r m r r r |%137| r d c r |%136| D d E h |%135| h H c |%134| C H |%133| R e M D |%132| R C R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13TS: 188%13",
"11w %13 +-----------------+%138| r r r r r r |%137| c r c |%136| d h |%135| h |%134| E d |%133| C e H |%132| R D D C R |%131| R R R M R R R |%13 +-----------------+%13 a b c d e f g h%13TS: 88%13",
"18b %13 +-----------------+%138| r r r m r r r |%137| r c d c d r |%136| h h |%135| |%134| R E |%133| H e H |%132| M D C C D R |%131| R R R R R R |%13 +-----------------+%13 a b c d e f g h%13TS: 148%13",
"25w %13 +-----------------+%138| r r m r r r |%137| r c d c d r |%136| h e E h |%135| |%134| R |%133| H H |%132| D D C C |%131| R R R M R R |%13 +-----------------+%13 a b c d e f g h%13TS: 200%13",
"40w %13 +-----------------+%138| r r m r r |%137| r c d h d r R |%136| e E r |%135| |%134| |%133| D H |%132| D C C |%131| R R R M R R |%13 +-----------------+%13 a b c d e f g h%13TS: 320%13",
"14b %13 +-----------------+%138| r r r m r r r |%137| r d d c c r |%136| h h |%135| |%134| |%133| H e H E |%132| R D D C M C R |%131| R R R R R R |%13 +-----------------+%13 a b c d e f g h%13TS: 116%13",
"24b %13 +-----------------+%138| r r r m r r r |%137| r d d c c r |%136| h h |%135| |%134| |%133| C H e R H |%132| R D D E C R R |%131| R R R M R |%13 +-----------------+%13 a b c d e f g h%13TS: 196%13",
"12w %13 +-----------------+%138| r e |%137| |%136| |%135| |%134| |%133| |%132| |%131| R E |%13 +-----------------+%13 a b c d e f g h%13TS: 44%13",
"48b %13 +-----------------+%138| r D r |%137| r r |%136| c |%135| c |%134| R r h |%133| D r E |%132| C d R R d R |%131| R R |%13 +-----------------+%13 a b c d e f g h%13",
"48b %13 +-----------------+%138| r D r |%137| r r |%136| c |%135| c |%134| R r h |%133| r e E |%132| D C d R R d R |%131| R R |%13 +-----------------+%13 a b c d e f g h%13",
"20w %13 +-----------------+%138| r r m h r |%137| r M r r |%136| r E |%135| R H |%134| e |%133| D C R |%132| H C R |%131| R R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"16w %13 +-----------------+%138| e |%137| R |%136| |%135| E |%134| |%133| R |%132| |%131| |%13 +-----------------+%13 a b c d e f g h%13", // Endgame
"16b %13 +-----------------+%138| e |%137| |%136| |%135| E |%134| |%133| R |%132| |%131| |%13 +-----------------+%13 a b c d e f g h%13", // Endgame
"16w %13 +-----------------+%138| e |%137| |%136| |%135| E |%134| |%133| R |%132| |%131| |%13 +-----------------+%13 a b c d e f g h%13", // Endgame
"26b %13 +-----------------+%138| r r r r r r r |%137| M E d h |%136| h D C c c R H |%135| R R R R r m e |%134| H R |%133| |%132| R |%131| |%13 +-----------------+%13 a b c d e f g h%13",
"46b %13 +-----------------+%138| |%137| |%136| |%135| |%134| r r |%133| r r E D r |%132| R M e R m R |%131| h R |%13 +-----------------+%13 a b c d e f g h%13",
"61w %13 +-----------------+%138| r H r |%137| m E |%136| r R d c r |%135| R R R R r |%134| R D e R r C r |%133| |%132| |%131| |%13 +-----------------+%13 a b c d e f g h%13",
"58b %13 +-----------------+%138| |%137| |%136| |%135| |%134| C M r |%133| R e r E |%132| D r r r R |%131| R R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"40b %13 +-----------------+%138| r r r |%137| r c |%136| D |%135| H R |%134| M |%133| m H |%132| E e R r |%131| R R |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r r r H |%137| c r R h r |%136| d H R |%135| e |%134| h E r C |%133| d R c R |%132| R |%131| |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r |%137| E M C |%136| |%135| D H D |%134| H C |%133| R |%132| R R R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r |%137| E H C |%136| |%135| D H D |%134| M C |%133| R |%132| R R R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r |%137| C H E |%136| |%135| D H D |%134| M C |%133| R |%132| R R R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r |%137| C H E |%136| |%135| D H D |%134| M C |%133| R |%132| R R R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r |%137| C H E |%136| |%135| D M D |%134| H C |%133| R |%132| R R R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r |%137| C H E |%136| |%135| D M D |%134| C H |%133| R |%132| R R R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r |%137| E H C |%136| |%135| D M D |%134| C H |%133| R |%132| R R R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13",
"63w %13 +-----------------+%138| r |%137| E H C |%136| |%135| D M D |%134| C H |%133| R |%132| R R R |%131| R R R R |%13 +-----------------+%13 a b c d e f g h%13",
};

long correct_move_count[] = {
20229,20203,18569,25293,17386,23695,22409,31866,17622,10232,14361,79,8596,
16477,48665,358,19,150,3598,161,2549,141,2030,3045,336488,337916,337922,
337922,338030,338034,338034,315908,
};

@Test
public void testGenAllTurns() {
// Run test positions
for (int i=0; i<text.length; i++ ) {
String pos_text = text[i];
GameState position = new GameState(pos_text);
turn.genAllTurns(position, result);
long total_moves = result[0]/2;
assertEquals(correct_move_count[i],total_moves);
}
}

}

Title: Re: Bot Performance
Post by speek on Jul 26^th, 2010, 10:52am

Great, thanks!

Title: Re: Bot Performance
Post by speek on Jul 27^th, 2010, 9:13pm

Regarding the position with just the elephant 19 legal moves for silver - I only see 18 legal moves. Not changing the position isn't a legal move, right? What am I missing?

Title: Re: Bot Performance
Post by Fritzlein on Jul 27^th, 2010, 9:40pm

on 07/27/10 at 21:13:37, speek wrote:

Regarding the position with just the elephant 19 legal moves for silver - I only see 18 legal moves. Not changing the position isn't a legal move, right? What am I missing?

Suicide is legal. By my count the elephant can reach 18 different squares or go bye-bye for 19 total legal moves.

Title: Re: Bot Performance
Post by speek on Jul 27^th, 2010, 10:23pm

That's how I get to 18. The possible moves are:

a6,a7,a8 3
b5,b6,b7,b8 4
c6,c7 2
d6,d7,d8 3
e6,e7,e8 3
f7,f8 2
g8 1

total = 18

Which square did I miss?

Title: Re: Bot Performance
Post by Fritzlein on Jul 27^th, 2010, 10:45pm

on 07/27/10 at 22:23:21, speek wrote:

That's how I get to 18. The possible moves are:

a6,a7,a8 3
b5,b6,b7,b8 4
c6,c7 2
d6,d7,d8 3
e6,e7,e8 3
f7,f8 2
g8 1

total = 18

Which square did I miss?

You missed d5.

Title: Re: Bot Performance
Post by speek on Jul 28^th, 2010, 8:35am

I have the gold elephant at d5. A lot of the pieces appear "in between" columns when I replace %13 with \n. Probably this is why my code is often off by a few tens of moves on some of these positions. Any pointers on how to properly read these charts?

Title: Re: Bot Performance
Post by Fritzlein on Jul 28^th, 2010, 9:26am

The way text is displayed by the forum collapses anything more than five spaces down to five spaces. I couldn't get the board to display properly from cutting and pasting JDB's post. I had to quote JDB's post, and then cut and paste from the window where I was editing my supposed reply to his message. Then I had the right number of spaces.

Title: Re: Bot Performance
Post by jdb on Jul 28^th, 2010, 9:33am

on 07/28/10 at 08:35:36, speek wrote:

String readable_text = pos_text.replaceAll("%13","\n");
System.out.println(readable_text);

Should print out the position in a nice format.

Title: Re: Bot Performance
Post by speek on Jul 28^th, 2010, 9:34am

on 07/28/10 at 09:26:00, Fritzlein wrote:

I had to quote JDB's post

Ah, thanks for the secret!

Title: Re: Bot Performance
Post by jdb on Jul 28^th, 2010, 9:35am

on 07/28/10 at 09:26:00, Fritzlein wrote:

I didn't know about the 5 space thing. Is there a way for me to fix that on my end?

Title: Re: Bot Performance
Post by Fritzlein on Jul 28^th, 2010, 9:44am

on 07/28/10 at 09:35:15, jdb wrote:

I didn't know about the 5 space thing. Is there a way for me to fix that on my end?

Not that I know of. When I use non-proportional font to make tables, I have to put in periods to stop the spaces from collapsing and to make it display correctly in the forum. >:( For example:

Elephant File 2005 2006 2007 2008 2009 2010
------------- ---- ---- ---- ---- ---- ----
d . . . 98.1 79.5 85.3 89.9 90.0 81.6
c . . . . 13.7 9.4 9.5 10.0 13.2
b . . . 1.9 6.3 5.3 . . 5.2
a . . . . 0.5 . 0.6

Rabbits Forward 2005 2006 2007 2008 2009 2010
--------------- ---- ---- ---- ---- ---- ----
ah . . 55.6 56.3 76.5 59.5 57.1 52.4
a . . . 2.5 15.3 4.1 0.6 5.0 12.8
none . . 14.4 22.6 10.0 6.0 2.1 10.8
cf . . 23.1 . . 8.3 1.4 6.6
ac . . . . . 0.6 . 5.2
c . . . 3.1 . . . . 3.8
acfh . . 0.6 . . 14.9 22.1 3.5
af . . . . . . 0.7 2.1
ach . . . . . . 1.4 1.0
acf . . . . . . . 1.0
ad . . . . . . . 0.3
ce . . . . . . . 0.3
adh . . . 2.6 4.1 10.1 10.0
adeh . . . 2.6 4.1
ag . . . 0.5 1.2
abgh . . 0.6

Setup Balance 2005 2006 2007 2008 2009 2010
------------- ---- ---- ---- ---- ---- ----
Symmetrical . 56.9 50.5 54.1 50.0 35.7 20.1
Balanced . 22.5 30.0 34.1 42.3 42.9 31.2
Unbalanced . 20.6 19.5 11.8 7.7 20.7 48.6

Gold Move 2w 2005 2006 2007 2008 2009 2010
------------ ---- ---- ---- ---- ---- ----
E up 4 . . 68.8 26.3 25.9 13.1 20.0 22.9
E up 3 over 1 11.3 11.6 1.2 3.6 14.3 9.7
E up 3; X up 1 6.3 41.1 40.0 45.2 45.7 33.3
E up 2; X,Y up 1 3.8 10.5 23.5 27.4 17.1 21.5
E, X, Y, Z up 1 3.8 3.2 . 1.2 . 4.2
Other . . 6.3 7.4 9.4 9.5 2.8 8.3

Title: Re: Bot Performance
Post by speek on Jul 28^th, 2010, 9:55am

Ok, I am mostly getting the right answers. Positions 2 and 3 for instance, spot on. Position 1, off by 1??? But, I am using two different hashes of the board to key unique positions, so it's entirely possible two different positions have the same two hashes once in a great while.

Title: Re: Bot Performance
Post by rbarreira on Jul 28^th, 2010, 9:58am

on 07/28/10 at 09:55:18, speek wrote:

As long as your zobrist keys have enough bits (64 is more than enough) and they're random enough it is more likely to be struck by lightning than finding a hash collision by just looking at a few thousand positions.

Title: Re: Bot Performance
Post by jdb on Jul 28^th, 2010, 10:25am

on 07/28/10 at 09:44:57, Fritzlein wrote:

Not that I know of. When I use non-proportional font to make tables, I have to put in periods to stop the spaces from collapsing and to make it display correctly in the forum. >:( For example:

Ok thanks for the info.

Maybe there is a setting in the forum software Omar can set?

Title: Re: Bot Performance
Post by jdb on Jul 28^th, 2010, 10:30am

on 07/28/10 at 09:55:18, speek wrote:

If you want, I can post some positions with reduced material and their move count.

Title: Re: Bot Performance
Post by speek on Jul 28^th, 2010, 10:39am

I think I'm good. I changed my second hash algorithm slightly, and got the right answer. I did work up from the 'smaller' positions that are there. Right now, of the 4 positions I am testing, I'm correct on all. Sadly, I had to remove my duplicates detection during step generation and only do it at the end, so my code is pretty slow :-(