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

        Arimaa >> Bot Development >> bot functions speed
        
(Message started by: JimmSlimm on Apr 12th, 2011, 1:27am)
Title: bot functions speed
Post by JimmSlimm on Apr 12th, 2011, 1:27am
hi, I have just started working on a bot.

I feel that first step should be to make the functions/methods as fast as possible.

My bot is in c# (C.NET).

Last few days I have been working on the function to get all possible moves in a turn for a chosen player, and it would be useful to compare speed to other developers.

for this board:

Code:
2g
+-----------------+
8| r r r c c r r r |
7| r h d e m d h r |
6|     x     x     |
5|                 |
4|                 |
3|     x     x     |
2| R H C M E C H R |
1| R R R D D R R R |
+-----------------+
  a b c d e f g h


I can get all possible moves for Gold in 524ms(without evaluating positions/material score)
question is: is it fast enough to compete against the top ranked bots or do I need to make it faster?
Title: Re: bot functions speed
Post by lightvector on Apr 12th, 2011, 2:17am
Welcome aboard!

For reference, my bot completes a 4-step search of a typical 2g in about 1/10 to 1/20 of a second. This is not just the time to generate the moves, but also sorting them, and evaluating the positions after the moves.

However, importantly, this is also using a hash table for pruning the huge number of moves that lead to identical positions (such as moves that are simply permutations of the same steps). You might not have implemented this yet. I think something like 90% of moves in a typical midgame position can be pruned this way.

If you don't have a hash table, then 1/2 a second is not unreasonable, I think.

Actually, I find that the speed of the move generator is not so relevant in my bot. The biggest bottleneck for me is the evaluation time, and the move generator is only a small fraction of that. I haven't timed it recently, but my guess would be less than 20% of the total time, possibly as little as 10% or 5%.

Good luck on your bot!
Title: Re: bot functions speed
Post by JimmSlimm on Apr 12th, 2011, 4:02am

on 04/12/11 at 02:17:02, lightvector wrote:
Welcome aboard!

For reference, my bot completes a 4-step search of a typical 2g in about 1/10 to 1/20 of a second. This is not just the time to generate the moves, but also sorting them, and evaluating the positions after the moves.

However, importantly, this is also using a hash table for pruning the huge number of moves that lead to identical positions (such as moves that are simply permutations of the same steps). You might not have implemented this yet. I think something like 90% of moves in a typical midgame position can be pruned this way.

If you don't have a hash table, then 1/2 a second is not unreasonable, I think.

Actually, I find that the speed of the move generator is not so relevant in my bot. The biggest bottleneck for me is the evaluation time, and the move generator is only a small fraction of that. I haven't timed it recently, but my guess would be less than 20% of the total time, possibly as little as 10% or 5%.

Good luck on your bot!



Thanks for the quick and good answer!

wow, seems that there's alot of improvements just on my move-generator to be done!

1. I am not using hash-tables
2. There are duplicated moves
3. No evaluation is made on each move in this speed-test(I think this would add almost 5 seconds lol)
Title: Re: bot functions speed
Post by JimmSlimm on Apr 12th, 2011, 8:23am
oops, I just realized that the speed I wrote was involving up to 5 moves instead of 4! lol that changes the numbers quite alot...

the speed to get ALL moves(22816 according to my function) on the above board state is:
44.3ms

again, that is without any kind of evaluation, and it produces alot of duplicate board states

edit: seems to be only 3331 unique moves of the 22816 generated
Title: Re: bot functions speed
Post by rbarreira on Apr 12th, 2011, 9:03am

on 04/12/11 at 08:23:54, JimmSlimm wrote:
oops, I just realized that the speed I wrote was involving up to 5 moves instead of 4! lol that changes the numbers quite alot...

the speed to get ALL moves(22816 according to my function) on the above board state is:
44.3ms

again, that is without any kind of evaluation, and it produces alot of duplicate board states

edit: seems to be only 3331 unique moves of the 22816 generated


That means you're generating about 515,000 full moves per second, which looks pretty good to me.
Title: Re: bot functions speed
Post by rbarreira on Apr 12th, 2011, 9:38am
I just remembered something though... As you may already be aware of, you will have to port your bot to Linux if you're intending to enter the official Arimaa competitions.

Is there a usable C# implementation for Linux? I know there's Mono but I'm not sure if it's good enough for what you're doing since my knowledge of C# is very low.

Look forward to seeing your bot playing games in any case :)
Title: Re: bot functions speed
Post by JimmSlimm on Apr 12th, 2011, 10:56am

on 04/12/11 at 09:38:03, rbarreira wrote:
I just remembered something though... As you may already be aware of, you will have to port your bot to Linux if you're intending to enter the official Arimaa competitions.

Is there a usable C# implementation for Linux? I know there's Mono but I'm not sure if it's good enough for what you're doing since my knowledge of C# is very low.

Look forward to seeing your bot playing games in any case :)


I didnt know that, thanks for telling me :P
Though I am far away from having a decent bot, so I'll figure something out when it's good enough for real competition :) (Even I can probably beat it right now, and I never played a game of arimaa)
Title: Re: bot functions speed
Post by thomastanck on Apr 13th, 2011, 3:42am
Ow! Play some games of arimaa and you'll know why you can beat it! The best way to improve your own bot is to play against it and see why it decides to do a bad move! Correct it, and play again for more bad moves! Your bot would be as good as you in no time!
Title: Re: bot functions speed
Post by rbarreira on Apr 13th, 2011, 3:49am

on 04/13/11 at 03:42:14, thomastanck wrote:
Ow! Play some games of arimaa and you'll know why you can beat it! The best way to improve your own bot is to play against it and see why it decides to do a bad move! Correct it, and play again for more bad moves! Your bot would be as good as you in no time!


Personally speaking I disagree. Your mileage may vary of course. (especially if you're a good Arimaa player unlike me)

For me, the way to improve my bot was to see its moves against stronger opponents, mostly other bots. I would watch the games live and look at the search output while watching. After a while, despite not being a good Arimaa player, I could often recognize the moves that led it to trouble (I guess it's easier to recognize bad moves than good moves).

Correlating these observations to the search output usually would let me understand where the problems were. Some problems I would try to correct, others I would almost ignore due to knowing that they were almost impossible to fix at the stage the bot was at.
Title: Re: bot functions speed
Post by omar on Apr 13th, 2011, 11:09pm

on 04/12/11 at 10:56:07, JimmSlimm wrote:
I didnt know that, thanks for telling me :P
Though I am far away from having a decent bot, so I'll figure something out when it's good enough for real competition :) (Even I can probably beat it right now, and I never played a game of arimaa)


If you can get it to run under Mono on a Linux box you should be OK.

You might want to consider programming in Cobra, which is a very clean language that translates to C#.

http://cobra-language.com/
Title: Re: bot functions speed
Post by JimmSlimm on Apr 14th, 2011, 3:47pm
First bot to test against people is complete!

name: bot_Phosphatherium
it's not using the time limits very well, it will use max 2 minutes

it only played one game in the gameroom, and it was against me, I lost some pieces and gave up(it was my first game also :P)

I hope it won't crash

edit: it sucks vs real opponent :( need a better eval-system
Title: Re: bot functions speed
Post by Fritzlein on Apr 14th, 2011, 5:09pm

on 04/14/11 at 15:47:38, JimmSlimm wrote:
edit: it sucks vs real opponent :( need a better eval-system

No worries; it's impressive just to get a bot up and running that fast.  Also, although it is always a gift to the community to leave your bot up for open play, you can get a quicker idea of how you are progressing by playing the ladder bots.
Title: Re: bot functions speed
Post by JimmSlimm on Apr 14th, 2011, 5:20pm

on 04/14/11 at 17:09:59, Fritzlein wrote:
No worries; it's impressive just to get a bot up and running that fast.  Also, although it is always a gift to the community to leave your bot up for open play, you can get a quicker idea of how you are progressing by playing the ladder bots.


Thanks, I learned a lot watching the last game it played, a loss can probably teach me much more to make it better,  opposed to a win. :P
Title: Re: bot functions speed
Post by JimmSlimm on May 8th, 2011, 6:56pm
ok, a little update.

the functions in the bot are now fast enough to evaluate all of my own(bots) moves that are possible, AND all of opponents possible moves he can react with if I make that move. This is well within 15 seconds most of the time. If there is time left, I evaluate one level further(ply?).

Using hashtables really helps.

Although I am happy with the speed, there are still improvements to be made, mostly evaluation quality but also speed.
Title: Re: bot functions speed
Post by rbarreira on May 9th, 2011, 7:25am

on 05/08/11 at 18:56:46, JimmSlimm wrote:
the functions in the bot are now fast enough to evaluate all of my own(bots) moves that are possible, AND all of opponents possible moves he can react with if I make that move. This is well within 15 seconds most of the time.


So no alpha-beta cuts yet?
Title: Re: bot functions speed
Post by JimmSlimm on May 9th, 2011, 7:54am

on 05/09/11 at 07:25:24, rbarreira wrote:
So no alpha-beta cuts yet?


I don't think so, I'm not 100% sure what alpha-beta is.

does alpha-beta mean eliminating bad moves from further evaluation, or sorting the moves by evaluation score to find the best move faster?
Title: Re: bot functions speed
Post by rbarreira on May 9th, 2011, 8:03am

on 05/09/11 at 07:54:01, JimmSlimm wrote:
I don't think so, I'm not 100% sure what alpha-beta is.

does alpha-beta mean eliminating bad moves from further evaluation, or sorting the moves by evaluation score to find the best move faster?


It means cutting branches of the search tree as soon as the returned score from a sub-branch is good enough to prove that some ancestor node already has a better move.

http://en.wikipedia.org/wiki/Alpha-beta_pruning
Title: Re: bot functions speed
Post by JimmSlimm on May 9th, 2011, 8:17am
ah, in that case, no I am not using alpha-beta pruning
Title: Re: bot functions speed
Post by Druzil on May 9th, 2011, 6:38pm
JimmSlimm, you say that you are evaluating eight steps (all your moves and opponents replies) using only hashtables and minimax.  Can you clarify as this seems to be alot of moves for just 15 secs.

if we take a step branching factor of 20.  Then 8 steps would be 20^8 = 25 600 000 000

Even if hash tables eliminated 90% of those its still excessive.  I've got a c# bot using PVS with a move ordering table and hash table and I'm able to get to 8/9 ply in 10 sec (where a ply can be 1 or 2 steps - on a push/pull)
Title: Re: bot functions speed
Post by JimmSlimm on May 9th, 2011, 6:54pm

on 05/09/11 at 18:38:04, Druzil wrote:
JimmSlimm, you say that you are evaluating eight steps (all your moves and opponents replies) using only hashtables and minimax.  Can you clarify as this seems to be alot of moves for just 15 secs.

if we take a step branching factor of 20.  Then 8 steps would be 20^8 = 25 600 000 000

Even if hash tables eliminated 90% of those its still excessive.  I've got a c# bot using PVS with a move ordering table and hash table and I'm able to get to 8/9 ply in 10 sec (where a ply can be 1 or 2 steps - on a push/pull)


hmm, that does sound like alot of evaluations... but it's true, unless I have some bug(I find alot of those, its over 15k lines already). Keep in mind that this is a very fast evaluation that's just for sorting the moves by score for further investigation by a better evaluation if there is time left.

maybe I am alpha-beta pruning after all after sorting?
Does those 8-9 ply you generate in 10 seconds include any kind of evaluation?
Title: Re: bot functions speed
Post by 99of9 on May 9th, 2011, 8:19pm
It's unlikely that you're accidentally alpha-beta pruning.

I think Druzil's estimates are a little off for the beginning of the game.  Check out Janzert's branching factor study http://arimaa.janzert.com/bf_study/.  If you only consider the very first (non-setup) move from each player, the number of unique moves is something like 3300x3300 = 11 million.  This is doable in 15 seconds.
Title: Re: bot functions speed
Post by Druzil on May 9th, 2011, 11:22pm
Sure for the beginning of the game the step branching factor is 8-11.  JimmSlimm were you only referring to the beginning of the game?
Title: Re: bot functions speed
Post by Fritzlein on May 9th, 2011, 11:34pm

on 05/09/11 at 18:54:37, JimmSlimm wrote:
hmm, that does sound like alot of evaluations... but it's true, unless I have some bug

Couldn't you verify simply by counting the number of evaluations you do?  That count should jibe with the depth attained and the branching factor.
Title: Re: bot functions speed
Post by JimmSlimm on May 10th, 2011, 9:21am

on 05/09/11 at 23:22:45, Druzil wrote:
Sure for the beginning of the game the step branching factor is 8-11.  JimmSlimm were you only referring to the beginning of the game?


No, I was referring to any game state.


Quote:
Couldn't you verify simply by counting the number of evaluations you do?  That count should jibe with the depth attained and the branching factor.


It's all of the moves I generate, if there is a bug, it would be in the move generator.

As I said, the evaluator is very fast. I am only using GAME at this stage, no positional evaluation is used at the first stage.
Title: Re: bot functions speed
Post by tize on May 10th, 2011, 11:00am

on 05/09/11 at 18:38:04, Druzil wrote:
if we take a step branching factor of 20.  Then 8 steps would be 20^8 = 25 600 000 000


I think the average branching factor per move is something like 17000 unique moves, which gives "just" 289 000 000 position after 2 plies on an average position. Then you only need to go through ~20Mnps, which is very high compared to what marwin gets but it should be doable with good hardware and a light evaluator.
Title: Re: bot functions speed
Post by Fritzlein on May 10th, 2011, 11:03am

on 05/10/11 at 09:21:56, JimmSlimm wrote:
It's all of the moves I generate, if there is a bug, it would be in the move generator.

Right, the point being that a move count could potentially reveal a bug if the count doesn't seem to jibe with the search depth.  A "nodes per second" measure is something a lot of developers take an interest in for a variety of other reasons as well, for example to get a quick assessment of the effect of changing hardware.
Title: Re: bot functions speed
Post by rbarreira on May 10th, 2011, 11:10am
Even with a simple evaluator, searching 2 plies in an average of 15 seconds without any cut-offs only seems possible to me with quite fast hardware and using all the cores of the CPU.

Is your bot multi-threaded?
Title: Re: bot functions speed
Post by JimmSlimm on May 10th, 2011, 11:23am

on 05/10/11 at 11:10:04, rbarreira wrote:
Even with a simple evaluator, searching 2 plies in an average of 15 seconds without any cut-offs only seems possible to me with quite fast hardware and using all the cores of the CPU.

Is your bot multi-threaded?


I do have good hardware, 3.2ghz i7 quad core and DDR3 RAM(not sure what speed they are, but I think it's fast). I have overclocked most things on my system.

"without any cut-offs", I am not sure how to define that, because when only evaluating material and not position, alot of speed can be gained by even using hashtables for GAME. The move generator also keeps track of material changes so I don't need to parse the game state one extra time when evaluating, the GAME evaluation is therefore only used a few of times, the rest is done by the hashtable.

This is a great method imo for deep searching when only material evaluation is used. And you can probably even go 3-4 moves ahead in 120+ seconds(just guessing).

edit: I am not using multiple threads yet
Title: Re: bot functions speed
Post by rbarreira on May 10th, 2011, 11:35am

on 05/10/11 at 11:23:56, JimmSlimm wrote:
I do have good hardware, 3.2ghz i7 quad core and DDR3 RAM(not sure what speed they are, but I think it's fast). I have overclocked most things on my system.

"without any cut-offs", I am not sure how to define that, because when only evaluating material and not position, alot of speed can be gained by even using hashtables for GAME. The move generator also keeps track of material changes so I don't need to parse the game state one extra time when evaluating, the GAME evaluation is therefore only used a few of times, the rest is done by the hashtable.

This is a great method imo for deep searching when only material evaluation is used. And you can probably even go 3-4 moves ahead in 120+ seconds(just guessing).

edit: I am not using multiple threads yet


When I say "without cut-offs" I'm just referring to the fact that you evaluate all possible moves to a depth of 2 plies (the alpha-beta algorithm does not always look at all moves).

Your CPU is fast and those optimizations you mentioned look good indeed, but my hunch is that a 2-ply search in an average of 15 seconds seems too fast when only using one core. It would mean you're evaluating 20 million unique moves per second, even the fastest chess programs don't go anywhere near that with a single core.

You might want to count the number of evaluations you're doing, to check that the number makes sense meaning you have no bugs.
Title: Re: bot functions speed
Post by JimmSlimm on May 10th, 2011, 12:15pm

on 05/10/11 at 11:35:12, rbarreira wrote:
When I say "without cut-offs" I'm just referring to the fact that you evaluate all possible moves to a depth of 2 plies (the alpha-beta algorithm does not always look at all moves).

Your CPU is fast and those optimizations you mentioned look good indeed, but my hunch is that a 2-ply search in an average of 15 seconds seems too fast when only using one core. It would mean you're evaluating 20 million unique moves per second, even the fastest chess programs don't go anywhere near that with a single core.

You might want to count the number of evaluations you're doing, to check that the number makes sense meaning you have no bugs.


You could say I am using cut-offs/pruning, since I don't "truly" evaluate even a fraction of the moves, most of them doesn't lead to any change in material(and that is identified very fast by the move generator).

To sum up:
1. All steps for me(at my turn) are generated, and evaluated only if we know that there is a change in material for that specific node
2. Steps for opponent is different, steps are only generated and investigated further if they can possibly lead to a material change within near future(within the opponent move), OR if they make a difference instantly. The part that investigates if a step can lead to a future "kill" is actually a small hashtable that's just focusing on a part of the board, this hashtable contains information about:
  1. Can I execute any moves that 100% leads to a material change?
  2. How many steps are required for those moves?

lol this is getting complicated, sorry... but after the specifics about a material changing move is found, bot looks in another hash-table if this change has already been evaluated, if it already has been evaluated, we dont need to evaluate it again, it would waste a few fractions of a millisecond. If this change needs to be evaluated, we run a evaluation and save the results to speed up the future checks.

So basicly hashtables for everything, even previously generated moves.

Sorry I am probably explaining the details very badly, but I hope you get the picture :)
Title: Re: bot functions speed
Post by rbarreira on May 10th, 2011, 12:20pm

on 05/10/11 at 12:15:49, JimmSlimm wrote:
2. Steps for opponent is different, steps are only generated and investigated further if they can possibly lead to a material change within near future(within the opponent move), OR if they make a difference instantly. The part that investigates if a step can lead to a future "kill" is actually a small hashtable that's just focusing on a part of the board, this hashtable contains information about:
  1. Can I execute any moves that 100% leads to a material change?
  2. How many steps are required for those moves?


This was the part I hadn't gotten yet!

It makes sense now, what you're doing is pruning some of the opponent moves so that does make the 15 second search plausible!
Title: Re: bot functions speed
Post by JimmSlimm on May 10th, 2011, 12:27pm

on 05/10/11 at 12:20:59, rbarreira wrote:
This was the part I hadn't gotten yet!

It makes sense now, what you're doing is pruning some of the opponent moves so that does make the 15 second search plausible!


Thanks for putting it into better words :) I didn't even know from the start I was pruning, I didnt know there was a word for it before I started with this bot. I am learning alot from these forums :P

I really don't see the moves as a tree of nodes, at least not when going from one player to another, more like one tree for my moves and many mini-trees for the opponents possible responses
Title: Re: bot functions speed
Post by lightvector on May 10th, 2011, 3:58pm
The base-line is where you recurse on *every* legal move and evaluate it. Not just legal moves that could matter, or legal moves that change the material, etc, but every legal move.

Any time you deviate from this and don't search a move (in your case, if it doesn't change the material balance), it's called pruning.   ;)
Title: Re: bot functions speed
Post by JimmSlimm on May 10th, 2011, 4:42pm

on 05/10/11 at 15:58:33, lightvector wrote:
The base-line is where you recurse on *every* legal move and evaluate it. Not just legal moves that could matter, or legal moves that change the material, etc, but every legal move.

Any time you deviate from this and don't search a move (in your case, if it doesn't change the material balance), it's called pruning.   ;)


thanks, I think I got it now :)

This is not important, but I wonder, the pruning itself is a low level evaluation isn't it? and if you answer no, why?
Title: Re: bot functions speed
Post by rbarreira on May 10th, 2011, 5:13pm

on 05/10/11 at 16:42:56, JimmSlimm wrote:
thanks, I think I got it now :)

This is not important, but I wonder, the pruning itself is a low level evaluation isn't it? and if you answer no, why?


Evaluation is giving a score to a position without searching moves from it (which is why sometimes it's called static evaluation).

Pruning is something you use while searching to decide which moves not to search.

You could use evaluation to decide when to prune or not, but they're two different concepts.
Title: Re: bot functions speed
Post by JimmSlimm on May 12th, 2011, 4:35pm
funny game: http://arimaa.com/arimaa/games/jsShowGame.cgi?gid=183621&s=w
or not :(
Title: s
Post by Swynndla on May 12th, 2011, 6:01pm
I found 48 to be a strange move.  Did the bot think that it is worth giving up a rabbit to save a cat?  http://arimaa.janzert.com/eval.html seems to say that the gold rabbit is worth more than the silver cat, and so perhaps 48s should have been to take the gold rabbit.  What did the bot's material evaluation think?
Title: Re: s
Post by JimmSlimm on May 12th, 2011, 6:26pm

on 05/12/11 at 18:01:38, Swynndla wrote:
I found 48 to be a strange move.  Did the bot think that it is worth giving up a rabbit to save a cat?  http://arimaa.janzert.com/eval.html seems to say that the gold rabbit is worth more than the silver cat, and so perhaps 48s should have been to take the gold rabbit.  What did the bot's material evaluation think?


yep very strange indeed, what happened is that the bot saw that gold had a chance to go for a goal threat on the east side, and it's offering a rabbit in hope that opponent will not see that opportunity. Generally it works well against my old bots, but a better solution is needed :) 3-ply moves are very time-consuming so I need a better evaluator for scoring threats and positions

The material evaluator always prefer cats over rabbits, I am using GAME, it never scores rabbits over cats even if it's only 1 rabbit left.
Title: Re: bot functions speed
Post by JimmSlimm on May 15th, 2011, 6:39pm
huge improvement at generating moves!

generating all 22816 moves for gold at the map from first post now only in 6.67ms! But this does NOT include any evaluation, also there are a lot of moves that produce the exact same result.

To generate the 3331 unique moves that does not produce any duplicate results, it takes a little longer: 10.6ms. This method will be used instead of the first one, because evaluation will require much more time on each board-state than the time required to generate them.

The speedup came from:
1. using byte[64] to represent board-state instead of int[8,8]
2. Multi-threading, instead of using only 1 core, I am using 100% of available cores (quad)

To generate 2 full ply's(4 steps for gold and 4 for silver) at this board-state, more than 15 seconds are required
Title: Re: bot functions speed
Post by Swynndla on May 15th, 2011, 8:59pm
JimmSlimm, some questions if I may (from someone who is only learning these things)...


on 05/15/11 at 18:39:34, JimmSlimm wrote:
huge improvement at generating moves!

generating all 22816 moves for gold at the map from first post now only in 6.67ms! But this does NOT include any evaluation, also there are a lot of moves that produce the exact same result.

To generate the 3331 unique moves that does not produce any duplicate results, it takes a little longer: 10.6ms.

What where the speeds of the first move (ie 4 steps) before the improvements? ... ie how much did it speed things up?



Quote:
The speedup came from:
1. using byte[64] to represent board-state instead of int[8,8]

I've heard that using a single array is faster than a multi-dimensional array.  This means you're not using "bitboards" right?  I've heard they are even faster, especially on a 64-bit system.  Are you using a 64-bit system?



Quote:
2. Multi-threading, instead of using only 1 core, I am using 100% of available cores (quad)

How do you split the cores up to help with the search?



Quote:
To generate 2 full ply's(4 steps for gold and 4 for silver) at this board-state, more than 15 seconds are required

And this is with no pruning right?  And only unique moves?

Thanks!
Title: Re: bot functions speed
Post by JimmSlimm on May 15th, 2011, 9:31pm

Quote:
What where the speeds of the first move (ie 4 steps) before the improvements? ... ie how much did it speed things up?

44.3ms to generate the 22816 moves before these improvements, I didn't write down the timing for the 3331 unique moves, and I didn't save the old function :(


Quote:
I've heard that using a single array is faster than a multi-dimensional array.  This means you're not using "bitboards" right?  I've heard they are even faster, especially on a 64-bit system.  Are you using a 64-bit system?

I just googled "bitboard", and it seems to be boolean-arrays, I am not using that, but it sure looks interesting! I will try it, thanks. Yes I am using 64bit system (windows 7).


Quote:
How do you split the cores up to help with the search?

I am using AForge.NET frameworks' Parallel.For-loop to do the multi-threading


Quote:
And this is with no pruning right?  And only unique moves?

Right, no pruning, only unique moves and no evaluation.
I noticed that the problem is the RAM usage, its using 10gb RAM when it's getting to 6-7 steps and thats the limit for me, I'm trying to make it use less RAM, probably I won't be able to save all the resulting boards to memory in all cases.
Title: Re: bot functions speed
Post by lightvector on May 15th, 2011, 10:14pm
Typically, one searches recursively, in a depth-first manner. Then you don't need to keep around all the boards in memory.

To search a board b to depth d, the following is a very common way to do it:

Code:
search(board b, depth d)
 if d <= 0, done searching, return evaluation(b)
 else
 generate all legal moves for b
 for each legal move
    make the move on b
    eval = search(b, d-1)
    undo the move on b
 return the best eval from the for loop


If you do it like this, you have only one board the entire time.

Alternatively, rather than making and undoing a move, you can copy the board and make the move on the copy.
Then you will have at most d copies of the board at any time, where d is the depth you are searching to.
Title: Re: bot functions speed
Post by Swynndla on May 15th, 2011, 11:52pm
Ahhh JimmSlimm must be doing width-first searching?

JimmSlimm, if you want your bot submitted to participate in the computer champs, I don't think it will have that much ram:
http://arimaa.com/arimaa/challenge/2011/hardware.html

and:
http://arimaa.com/arimaa/wcc/2011/rules.html

Thanks lightvector for you help!

Also: I would think that copying the board would be slower than doing the move and undoing it back again, as moves are done incrementally, unless, that is, the copying is some low-level optimized routine?
Title: Re: bot functions speed
Post by JimmSlimm on May 16th, 2011, 6:48am
Ah, thanks lightvector for that idea.

Yes Swynndla I am currently doing width-first
Title: Re: bot functions speed
Post by rbarreira on May 16th, 2011, 8:16am

on 05/15/11 at 23:52:58, Swynndla wrote:
Also: I would think that copying the board would be slower than doing the move and undoing it back again, as moves are done incrementally, unless, that is, the copying is some low-level optimized routine?


My bot used to copy the board before making every step, then I changed to making-unmaking steps and performance didn't noticeably improve.

There are still a few smaller things I copy instead of making/unmaking (some are irreversible like captured pieces, but some could also be unmade instead of copied), so I may be able to copy even less stuff and get an improvement. But at least for me, I don't expect that this change will contribute much...

This may vary among bots and CPU models though, since each bot/cpu will have different cache/memory access patterns which may make the copying heavier.
Title: Re: bot functions speed
Post by Hippo on May 16th, 2011, 9:02am

on 05/16/11 at 06:48:49, JimmSlimm wrote:
Ah, thanks lightvector for that idea.

Yes Swynndla I am currently doing width-first


I cannot beleive it could work ... expanding to 2 or at least 3 full turns must lead to consumption of the whole memory.

I would expect expanding to full width only in one branch.

Of course even more (at least space) effective method does not need to keep full expansion of a level, but generating positions/moves on demand.

The problem with avoiding search of repeated positions could be more difficult when positions are generated on several levels of search concurently.
(Repetition avoiding hash table(s) need several active histories).

I still use the original jdb's engine, but it's step based except the root level so expanding full width of at most 185 moves (except the killers) is not problem.

I am still not sure which option to chose. Generating moves on demand has advantage when the generation is interrupted due to cut in search.
Generating all the moves allow their sorting prior to further search. So it allows more efficient cutting.

So probably on bottom search level generating on demand is preferable while on higher levels generating all the moves (and their sorting) is better.

Generating on demand "presorted" is preferable.
Title: Re: bot functions speed
Post by lightvector on May 16th, 2011, 9:52am
I also copy the board, because it's easier. I don't have to track all the metadata for undoing in the presence of captured pieces.

Optimization of all of this stuff is fine, but as long as you're doing something "not terrible", I've found that it doesn't matter. The bottleneck for me at least is evaluation. I could do any number of different things to optimize move generation, board copying, etc, in the search, and it wouldn't make that big of a difference, since only a small fraction of the time is taken by these things, compared to evaluation.

Beware of premature optimization.
Title: Re: bot functions speed
Post by rbarreira on May 16th, 2011, 10:56am

on 05/16/11 at 09:52:57, lightvector wrote:
I also copy the board, because it's easier. I don't have to track all the metadata for undoing in the presence of captured pieces.

Optimization of all of this stuff is fine, but as long as you're doing something "not terrible", I've found that it doesn't matter. The bottleneck for me at least is evaluation. I could do any number of different things to optimize move generation, board copying, etc, in the search, and it wouldn't make that big of a difference, since only a small fraction of the time is taken by these things, compared to evaluation.

Beware of premature optimization.


In general you are definitely correct, but sometimes profiling the code can be deceptive. As an extreme example a program may have a piece of code which doesn't take that long to run, but which causes the whole cache to get filled with trash. The slowdown will show up in other parts of the code.

For this specific case on copying vs unmaking moves, originally I saw benchmarks from Robert Hyatt with his chess program which indicated that as the number of threads goes up, the unmaking approach starts to get faster. I was unable to reproduce this with my Arimaa bot, but I don't think I tested with as many threads as he did, since I usually only test it on a 6-core CPU.
Title: Re: bot functions speed
Post by Druzil on May 16th, 2011, 7:09pm
JimmSlimm how are you accessing so much memory with C#.  Even with x64 CPU and x64 OS the maximum memory available is ~8.7GB
Title: Re: bot functions speed
Post by JimmSlimm on May 17th, 2011, 6:44am

on 05/16/11 at 19:09:33, Druzil wrote:
JimmSlimm how are you accessing so much memory with C#.  Even with x64 CPU and x64 OS the maximum memory available is ~8.7GB


I don't know, task manager sais >10gb is used by the bot process sometimes
Title: Re: bot functions speed
Post by Swynndla on May 18th, 2011, 9:16pm

on 05/16/11 at 09:52:57, lightvector wrote:
Optimization of all of this stuff is fine, but as long as you're doing something "not terrible", I've found that it doesn't matter. The bottleneck for me at least is evaluation. I could do any number of different things to optimize move generation, board copying, etc, in the search, and it wouldn't make that big of a difference, since only a small fraction of the time is taken by these things, compared to evaluation.

I like what you say.  Please keep up the clear, logical & to-the-point posts!  (I'm learning a lot.)

Will you be making Sharp 2012 multi-threaded (to take advantage of the multiple cores), or will you be concentrating on evaluation & pruning?


Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.