Author |
Topic: bot functions speed (Read 7885 times) |
|
rbarreira
Forum Guru
Arimaa player #1621
Gender: 
Posts: 605
|
 |
Re: bot functions speed
« Reply #30 on: May 10th, 2011, 12:20pm » |
 Quote  Modify
|
on May 10th, 2011, 12:15pm, 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!
|
|
 IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #31 on: May 10th, 2011, 12:27pm » |
Quote Modify
|
on May 10th, 2011, 12:20pm, 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 
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
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: bot functions speed
« Reply #32 on: May 10th, 2011, 3:58pm » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #33 on: May 10th, 2011, 4:42pm » |
Quote Modify
|
on May 10th, 2011, 3:58pm, 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?
|
| « Last Edit: May 10th, 2011, 4:49pm by JimmSlimm » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #34 on: May 10th, 2011, 5:13pm » |
Quote Modify
|
on May 10th, 2011, 4:42pm, 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.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
s
« Reply #36 on: May 12th, 2011, 6:01pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: s
« Reply #37 on: May 12th, 2011, 6:26pm » |
Quote Modify
|
on May 12th, 2011, 6:01pm, 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.
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #38 on: May 15th, 2011, 6:39pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: bot functions speed
« Reply #39 on: May 15th, 2011, 8:59pm » |
Quote Modify
|
JimmSlimm, some questions if I may (from someone who is only learning these things)...
on May 15th, 2011, 6:39pm, 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!
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #40 on: May 15th, 2011, 9:31pm » |
Quote Modify
|
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.
|
| « Last Edit: May 15th, 2011, 9:32pm by JimmSlimm » |
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: bot functions speed
« Reply #41 on: May 15th, 2011, 10:14pm » |
Quote Modify
|
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.
|
| « Last Edit: May 15th, 2011, 10:16pm by lightvector » |
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: bot functions speed
« Reply #42 on: May 15th, 2011, 11:52pm » |
Quote Modify
|
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?
|
| « Last Edit: May 15th, 2011, 11:57pm by Swynndla » |
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #43 on: May 16th, 2011, 6:48am » |
Quote Modify
|
Ah, thanks lightvector for that idea.
Yes Swynndla I am currently doing width-first
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #44 on: May 16th, 2011, 8:16am » |
Quote Modify
|
on May 15th, 2011, 11:52pm, 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.
|
| « Last Edit: May 16th, 2011, 8:18am by rbarreira » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print