Author |
Topic: "real" branching factor ? (Read 1392 times) |
|
chessandgo
Forum Guru
Arimaa player #1889
Gender: 
Posts: 1244
|
 |
"real" branching factor ?
« on: Apr 18th, 2006, 8:41pm » |
 Quote  Modify
|
Hi !
I wondered : roughly, how many moves (ply or steps) do existing bots search at every position ? Is it of the same order as the total number of possible moves, or do they reject a big part of them, like 9/10 or 99/100, before going on exploring ahead ?
I guess it depends of the bots but ...
Thx !
Jean
|
|
 IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: "real" branching factor ?
« Reply #1 on: Apr 19th, 2006, 11:26pm » |
Quote Modify
|
Ahhhh, that would be giving away their secrets 
But seriously, I'm under the impression from various discussions (but I don't really know) that Gnobot is the only bot that has severe pruning on it's search tree. I'm also guessing that some will drop branches that are clearly bad (eg moving a phant into an unsupported trap square), and some will search all branches.
Also, some will explore "interesting" braches further than the rest of the branches.
So I'm guessing that most bots search most braches before moving to the next ply (and therefore would be about the same order as the total number of possible moves).
I'd be interested to hear what some of the bot developers have to say about this. How long does it take for their bots to search 1 ply, 2 ply, 3 ply, 4 ply etc?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: "real" branching factor ?
« Reply #2 on: Apr 20th, 2006, 3:38am » |
Quote Modify
|
on Apr 19th, 2006, 11:26pm, Swynndla wrote:| Gnobot is the only bot that has severe pruning on it's search tree. |
|
No, quite the opposite. Gnobot_2005+ does not prune at all. Gnobot_2004 did severe pruning... but 2004 failed for many reasons.
Quote:| I'd be interested to hear what some of the bot developers have to say about this. How long does it take for their bots to search 1 ply, 2 ply, 3 ply, 4 ply etc? |
|
Gnobot:
1 ply - less than 1 sec
2 ply - about 5 sec, but varies quite a bit with the position
3 ply - about 4 minutes, but varies quite a bit...
4 ply - no chance
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: "real" branching factor ?
« Reply #3 on: Apr 20th, 2006, 3:45am » |
Quote Modify
|
Now that is interesting!
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: "real" branching factor ?
« Reply #4 on: Apr 20th, 2006, 7:23am » |
Quote Modify
|
on Apr 20th, 2006, 3:38am, 99of9 wrote:
Gnobot_2005+ does not prune at all. Gnobot_2004 did severe pruning... but 2004 failed for many reasons. |
|
What sort of reasons? Are there too many combinations of tricky moves that would be cut out when doing severe pruning?
It's intreging, as we all know that humans use sever pruning (and in my case too much). Although good players can analyse quite well, I'm thinking that it's their refined pruning (ie knowing which branches to look at and which not) makes a big difference to their strength (that and also being able to assess whether or not a position is good or bad, but I think that is really refined pruning in disguise). This is obtained from experience. I guess it'd be hard to program a person's experience into a bot in terms of refined pruning. Even more awesome would be to get an AI program to refine it's pruning based on it's own experience. I suppose that's where maybe a neural net could be used.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: "real" branching factor ?
« Reply #5 on: Apr 20th, 2006, 7:44am » |
Quote Modify
|
Gnobot_2004 searched each 4 steps at full width, and evaluated all the resulting positions. 10 moves were selected, and searched deeper, etc.
The problem is, it's eval wasn't able to guarantee that the best move would be amongst those 10. So if, for example, the opponent had a possible goal next move, I just had to hope that one of those 10 moves would block it!
So yes, in order to be able to do good pruning, you have to be able to do good evaluation. And it probably should not be so harsh (10 out of 20,000 considered! )... but because I had coded it myself, the code was really slow.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: "real" branching factor ?
« Reply #6 on: Apr 23rd, 2006, 6:25am » |
Quote Modify
|
on Apr 20th, 2006, 3:38am, 99of9 wrote:
Gnobot_2005+ does not prune at all. Gnobot_2004 did severe pruning... |
|
Doesn't Gnobot_2005 not even use any kind of minimax pruning whatsoever? ... like even if one move was Ec2n Ec3x then you wouldn't analyse everything from that branch, would you? (maybe you would?).
Also, what does Gnobot_2006 do?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: "real" branching factor ?
« Reply #7 on: Apr 23rd, 2006, 6:42am » |
Quote Modify
|
2005+ have no pruning at all (just like the sample bot).
The example you suggest is something I'd like to include .
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print