Author |
Topic: bot functions speed (Read 7883 times) |
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender: 
Posts: 86
|
 |
bot functions speed
« on: Apr 12th, 2011, 1:27am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: bot functions speed
« Reply #1 on: Apr 12th, 2011, 2:17am » |
Quote Modify
|
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!
|
| « Last Edit: Apr 12th, 2011, 2:21am by lightvector » |
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #2 on: Apr 12th, 2011, 4:02am » |
Quote Modify
|
on Apr 12th, 2011, 2:17am, 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)
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #3 on: Apr 12th, 2011, 8:23am » |
Quote Modify
|
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
|
| « Last Edit: Apr 12th, 2011, 8:32am by JimmSlimm » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #4 on: Apr 12th, 2011, 9:03am » |
Quote Modify
|
on Apr 12th, 2011, 8:23am, 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.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #5 on: Apr 12th, 2011, 9:38am » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #6 on: Apr 12th, 2011, 10:56am » |
Quote Modify
|
on Apr 12th, 2011, 9:38am, 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 
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)
|
|
IP Logged |
|
|
|
thomastanck
Forum Senior Member
6366th Person to register!
Gender:
Posts: 30
|
|
Re: bot functions speed
« Reply #7 on: Apr 13th, 2011, 3:42am » |
Quote Modify
|
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!
|
|
IP Logged |
Thomas Tan, a very bad Arimaa player.
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #8 on: Apr 13th, 2011, 3:49am » |
Quote Modify
|
on Apr 13th, 2011, 3:42am, 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.
|
| « Last Edit: Apr 13th, 2011, 3:51am by rbarreira » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: bot functions speed
« Reply #9 on: Apr 13th, 2011, 11:09pm » |
Quote Modify
|
on Apr 12th, 2011, 10:56am, JimmSlimm wrote:
I didnt know that, thanks for telling me
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/
|
| « Last Edit: Apr 13th, 2011, 11:09pm by omar » |
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #10 on: Apr 14th, 2011, 3:47pm » |
Quote Modify
|
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 )
I hope it won't crash
edit: it sucks vs real opponent  need a better eval-system
|
| « Last Edit: Apr 14th, 2011, 4:34pm by JimmSlimm » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot functions speed
« Reply #11 on: Apr 14th, 2011, 5:09pm » |
Quote Modify
|
on Apr 14th, 2011, 3:47pm, 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.
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #12 on: Apr 14th, 2011, 5:20pm » |
Quote Modify
|
on Apr 14th, 2011, 5:09pm, 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.
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #13 on: May 8th, 2011, 6:56pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #14 on: May 9th, 2011, 7:25am » |
Quote Modify
|
on May 8th, 2011, 6:56pm, 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?
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print