|
||||
|
Title: "real" branching factor ? Post by chessandgo on Apr 18th, 2006, 8:41pm 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 |
||||
|
Title: Re: "real" branching factor ? Post by Swynndla on Apr 19th, 2006, 11:26pm 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? |
||||
|
Title: Re: "real" branching factor ? Post by 99of9 on Apr 20th, 2006, 3:38am on 04/19/06 at 23:26:57, Swynndla wrote:
No, quite the opposite. Gnobot_2005+ does not prune at all. Gnobot_2004 did severe pruning... but 2004 failed for many reasons. Quote:
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 |
||||
|
Title: Re: "real" branching factor ? Post by Swynndla on Apr 20th, 2006, 3:45am Now that is interesting! |
||||
|
Title: Re: "real" branching factor ? Post by Swynndla on Apr 20th, 2006, 7:23am on 04/20/06 at 03:38:23, 99of9 wrote:
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. |
||||
|
Title: Re: "real" branching factor ? Post by 99of9 on Apr 20th, 2006, 7:44am 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. |
||||
|
Title: Re: "real" branching factor ? Post by Swynndla on Apr 23rd, 2006, 6:25am on 04/20/06 at 03:38:23, 99of9 wrote:
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? |
||||
|
Title: Re: "real" branching factor ? Post by 99of9 on Apr 23rd, 2006, 6:42am 2005+ have no pruning at all (just like the sample bot). The example you suggest is something I'd like to include ;-). |
||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |