Author |
Topic: bot functions speed (Read 7888 times) |
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender: 
Posts: 86
|
 |
Re: bot functions speed
« Reply #15 on: May 9th, 2011, 7:54am » |
 Quote  Modify
|
on May 9th, 2011, 7:25am, 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?
|
|
 IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #16 on: May 9th, 2011, 8:03am » |
Quote Modify
|
on May 9th, 2011, 7:54am, 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
|
| « Last Edit: May 9th, 2011, 8:05am by rbarreira » |
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #17 on: May 9th, 2011, 8:17am » |
Quote Modify
|
ah, in that case, no I am not using alpha-beta pruning
|
|
IP Logged |
|
|
|
Druzil
Forum Junior Member
Arimaa player #6252
Gender:
Posts: 6
|
|
Re: bot functions speed
« Reply #18 on: May 9th, 2011, 6:38pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #19 on: May 9th, 2011, 6:54pm » |
Quote Modify
|
on May 9th, 2011, 6:38pm, 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?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: bot functions speed
« Reply #20 on: May 9th, 2011, 8:19pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Druzil
Forum Junior Member
Arimaa player #6252
Gender:
Posts: 6
|
|
Re: bot functions speed
« Reply #21 on: May 9th, 2011, 11:22pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot functions speed
« Reply #22 on: May 9th, 2011, 11:34pm » |
Quote Modify
|
on May 9th, 2011, 6:54pm, 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.
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #23 on: May 10th, 2011, 9:21am » |
Quote Modify
|
on May 9th, 2011, 11:22pm, 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.
|
|
IP Logged |
|
|
|
tize
Forum Guru
Arimaa player #3121
Gender:
Posts: 118
|
|
Re: bot functions speed
« Reply #24 on: May 10th, 2011, 11:00am » |
Quote Modify
|
on May 9th, 2011, 6:38pm, 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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: bot functions speed
« Reply #25 on: May 10th, 2011, 11:03am » |
Quote Modify
|
on May 10th, 2011, 9:21am, 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.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #26 on: May 10th, 2011, 11:10am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #27 on: May 10th, 2011, 11:23am » |
Quote Modify
|
on May 10th, 2011, 11:10am, 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
|
| « Last Edit: May 10th, 2011, 11:24am by JimmSlimm » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: bot functions speed
« Reply #28 on: May 10th, 2011, 11:35am » |
Quote Modify
|
on May 10th, 2011, 11:23am, 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.
|
| « Last Edit: May 10th, 2011, 11:36am by rbarreira » |
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: bot functions speed
« Reply #29 on: May 10th, 2011, 12:15pm » |
Quote Modify
|
on May 10th, 2011, 11:35am, 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 
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print