Author |
Topic: Bot Performance (Read 5603 times) |
|
speek
Forum Guru
Arimaa player #5441
Gender: 
Posts: 75
|
 |
Bot Performance
« on: Jul 22nd, 2010, 8:31am » |
 Quote  Modify
|
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)?
|
|
 IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Bot Performance
« Reply #1 on: Jul 22nd, 2010, 8:52am » |
Quote Modify
|
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?
|
| « Last Edit: Jul 22nd, 2010, 8:54am by rbarreira » |
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Bot Performance
« Reply #2 on: Jul 22nd, 2010, 9:04am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Bot Performance
« Reply #3 on: Jul 22nd, 2010, 9:31am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Bot Performance
« Reply #4 on: Jul 22nd, 2010, 9:45am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Bot Performance
« Reply #5 on: Jul 22nd, 2010, 10:01am » |
Quote Modify
|
on Jul 22nd, 2010, 9:45am, speek wrote: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. |
|
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).
|
|
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Bot Performance
« Reply #6 on: Jul 22nd, 2010, 10:31am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Bot Performance
« Reply #7 on: Jul 22nd, 2010, 10:42am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Bot Performance
« Reply #8 on: Jul 22nd, 2010, 1:47pm » |
Quote Modify
|
on Jul 22nd, 2010, 10:42am, 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%.
|
| « Last Edit: Jul 22nd, 2010, 1:58pm by Fritzlein » |
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Bot Performance
« Reply #9 on: Jul 22nd, 2010, 2:53pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Bot Performance
« Reply #10 on: Jul 22nd, 2010, 9:47pm » |
Quote Modify
|
on Jul 22nd, 2010, 1:47pm, 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.
|
| « Last Edit: Jul 22nd, 2010, 9:50pm by rbarreira » |
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Bot Performance
« Reply #11 on: Jul 23rd, 2010, 7:10am » |
Quote Modify
|
What does "search" refer to?
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Bot Performance
« Reply #12 on: Jul 23rd, 2010, 9:23am » |
Quote Modify
|
Things like checking the repetition/mandatory board change rules, the killer-moves heuristic, checking for terminal states, the alpha-beta algorithm itself etc.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Bot Performance
« Reply #13 on: Jul 26th, 2010, 4:30am » |
Quote Modify
|
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.
|
| « Last Edit: Jul 26th, 2010, 4:42am by rbarreira » |
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Bot Performance
« Reply #14 on: Jul 26th, 2010, 9:18am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print