Author |
Topic: search tree techniques (Read 4365 times) |
|
fotland
Forum Guru
Arimaa player #211
Gender: 
Posts: 216
|
 |
Re: search tree techniques
« Reply #15 on: Aug 14th, 2006, 10:26pm » |
 Quote  Modify
|
I haven't been here for a while, but thanks for the compliments. I don't have any plans soo nto work on Bomb. I implemented all of the easy and obvious things, but to make it much stronger I would have to take a more disciplined approach with regression testing and tuning and fixing bugs. That's much less interesting than just writing code. At this point there is no chance to win the arimaa challenge, so I'm not very motivated.
I won't sell the code, but I don't mind answering questions about how it works. I think most of the strength is due to better evaluation of trap and goal threats. This avoids lots of additional searching. Otherwise it is a pretty standard iterative deepening alpha-beta searcher with transposition table and null move and some search extensions.
Bomb prunes using null move at any step, forcing a pass for the remaining steps in that move, and reducing search depth by 4 steps.
It also prunes by doing an early evaluation if the remaining steps are all by the same side, to see if it can get a cutoff.
Otherwise it does a full alpha-beta search to a fixed depth (with extensions).
The search display shows the full width depth, and the actual minimum and maximum depths.
Quiescense search is not difficult. The evaluation function finds all pieces that can be captured by the side to move during the remainder of this move. This is done with a decision tree matching about 50 patterns. When there is a match it records which step leads to the capture. This information makes it easy to generate moves for the quiescence search.
The quiescence search also generates the forced moves that follow a push ( a sort of singluar extension).
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: search tree techniques
« Reply #16 on: Aug 15th, 2006, 1:55pm » |
Quote Modify
|
on Aug 14th, 2006, 10:26pm, fotland wrote:| Quiescense search is not difficult. The evaluation function finds all pieces that can be captured by the side to move during the remainder of this move. This is done with a decision tree matching about 50 patterns. When there is a match it records which step leads to the capture. This information makes it easy to generate moves for the quiescence search. |
|
That's funny. I had read Haizhi's thesis, and I thought I understood how he used decision trees in his evaluation function to consider traps and goals, but it never occurred to me that the same decision tree could be used for move generation. I suppose I shouldn't feel too bad to miss that subtlety if a computer science student didn't figure it out either.
Haizhi's thesis says, "Implementing the cases for all 4 steps [rather than only 3 steps] will make it better, but considering the difficulty involved, it is not critical," and much later says, "But in Arimaa, where every move is composed of up to 4 steps, Quiescence Search is not practical for it is too costly." I guess he wouldn't have considered implementing 4-step decision trees too difficult if he had realized it would make quiescence search cheap!
That leads me to another question. Does your quiescence search handle goals as well as captures? It is not rare for a capture to produce a goal threat. It would be a shame if QS let the opponent respond to your capture with a capture of his own if your initial capture produced a goal threat that QS didn't see.
Haizhi estimated over 100 cases would be necessary to handle the four-step goal decision tree. That sounds hard enough in itself, but it seems that you would almost have to go eight steps out to allow QS to consider moves that are merely goal threats. It would be great if QS could consider a series of goal threats and defenses to goal threats to see if an attack will break through, but maybe that's just not feasible.
Quote:| I won't sell the code, but I don't mind answering questions about how it works. |
|
Fantastic. It is extremely kind of you to share your expertise. I wish I could reciprocate by sharing useful insights into Arimaa strategy, but I'm afraid my ideas are so nebulous I might actually point you in the wrong direction. In fact I think I already once did give you some bad strategy advice.
Back when the EH attack was first showing some good results against Bomb, opinion on how to meet the EH was divided between (1) trying to get more aggressive with the friendly camel, (2) trying to frame the hostage horse, and (3) trying to pass the hostage horse off to the friendly camel. Experience has shown that (1) is the wrong answer, but I believe you implemented it on my advice!
Anyway, now that you have explained about quiescence search, my most burning question is how Bomb uses threats in evaluation. Is each threat just worth a simple value, which is linearly added in to the total evaluation, or does something more complex happen?
It seems to me that, since the opponent can usually deal with the largest threat, that only the second-largest threat matters. Thus two threats to kill dogs are worth more than a camel threat plus a rabbit threat, since in each case the opponent will block the top threat.
On the other hand, it changes depending on the size of the opponent's threat. If he's threatening a horse, then my two dog threats are no better than one dog threat. I'll just get a dog for a horse either way. If he happens to have a horse threat, I'd much rather have the camel threat plus the rabbit threat, because he'll have to give up on his threat to stop my bigger one.
I'm guessing that your go experience would lead you to handle threats in some sophisticated way, but I can't quite imagine how.
Quote:| At this point there is no chance to win the arimaa challenge, so I'm not very motivated. |
|
That's quite a shame. I would like very much for you to be motivated. Would it help you be motivated if Bomb loses the Computer Championship this year?
When you say that there is no chance to win the Arimaa Challenge at this point, does that mean you are optimistic for 2020 when computers are 100 times faster than today? Or does it mean that you were only optimistic for the first year and after that, Omar can count on keeping his money, because the Challenge is safe?
I'm surprised that you are so pessimistic now given your earlier optimism. Are the new human insights into strategy really so impossible to code? At one point I expected each new advance in Arimaa theory to only temporarily benefit humans, as developers would quickly modify their hard-coded evals to keep up. Do you think the deepening body of Arimaa theory actually gives a permanent advantage to humans?
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: search tree techniques
« Reply #17 on: Aug 5th, 2008, 12:22am » |
Quote Modify
|
on Aug 14th, 2006, 10:26pm, fotland wrote:| Bomb prunes using null move at any step, forcing a pass for the remaining steps in that move, and reducing search depth by 4 steps. |
|
Is that a good idea? Why do that instead of only doing the null-move pruning at the start of a player's turn?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: search tree techniques
« Reply #18 on: Aug 5th, 2008, 5:44am » |
Quote Modify
|
I don't know how it works out in practice, but null-move pruning after one or two steps makes intuitive sense to me. The idea behind null-move pruning is that if a move superficially appears so weak that I can pass in response and still come out ahead, I can spare myself the full search to prove that I come out ahead. It's resolving not to spend time on moves that appear to actually weaken the moving player's position.
By the same token, if a move is so weak that it has a one-step or two-step refutation, it is probably not worth a full search to prove that it has a four-step refutation. I guess I might wonder, though, whether less of a depth reduction is appropriate given that a two-step refutation is lesser sign of weakness than a one-step refutation or zero-step refutation.
By the time search gets to three steps of a turn, I would be suspicious that any reduction is appropriate. Often some three-step move is nearly as good as any four-step move, and sometimes a three-step move is even best, so it doesn't seem to make sense to treat it as a humiliation to the opponent's move in the way that a pass is a humiliation.
That's my intuitive take, but as a non-developer, my intuitions might not be that great. 
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: search tree techniques
« Reply #19 on: Aug 5th, 2008, 8:14am » |
Quote Modify
|
on Aug 5th, 2008, 5:44am, Fritzlein wrote:| I guess I might wonder, though, whether less of a depth reduction is appropriate given that a two-step refutation is lesser sign of weakness than a one-step refutation or zero-step refutation. |
|
This is exactly the concern I had when making that post. For null-move pruning to improve a bot's play rather than have inappropriate cutoffs deteriorate it, it's important that the lack of accuracy in evaluation at a shallower depth is sufficiently compensated by how much the potential "refuter" is disadvantaged by having a fewer number of steps at its disposal. In light of that, dropping four steps regardlessly from the search might be a considerably bad thing to do, especially when the compensation is as little as a single null step and especially considering how rudimentary I assume the current state of knowledge to be with respect to Arimaa evaluation and the consequent dependence on the search.
Perhaps something can be said for the idea of having the search depth be shallower by the same amount of steps as the number of passed steps, but it's not clear to me how that would be advantageous over just having whole-move reductions for whole-move skips.
It would be interesting to find out what the case in this regard is with the other bots.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: search tree techniques
« Reply #20 on: Aug 5th, 2008, 12:11pm » |
Quote Modify
|
Perhaps Janzert, being particularly interested in depth reductions, will test this for us. 
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: search tree techniques
« Reply #21 on: Aug 5th, 2008, 2:05pm » |
Quote Modify
|
I think I experimented with similiar ideas when I added null move pruning to opfor but didn't find any improvement. I know I tried several different schemes with dynamic pruning depths and ended up just using a static 4 step reduction. But I did nowhere near enough testing to really know for sure one way or the other. In actuality I don't have the resource to do anywhere near enough testing to prove it one way or the other. I've known for quite some time to really prove an improvement with type of small difference you need a at least several hundreds of games. Recently though Robert Hyatt started a thread on the Chess Computer Club forum arguing that even 25000 games are not enough. So for now at least I've pretty much given up on even thinking about trying to prove whether these things are beneficial or not and just going by feel. :/
[Edit: I should have mentioned for those not familiar with Robert Hyatt, he is the creator of crafty and also previously cray-blitz.]
Janzert
|
| « Last Edit: Aug 5th, 2008, 2:23pm by Janzert » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: search tree techniques
« Reply #22 on: Aug 5th, 2008, 2:37pm » |
Quote Modify
|
But do you do that 4-step reduction only after a pass, or also after 1-step, 2-step, and 3-step refutations?
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: search tree techniques
« Reply #23 on: Aug 5th, 2008, 4:09pm » |
Quote Modify
|
It is tried at any number of steps into a move as long as it isn't in the middle of a push.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: search tree techniques
« Reply #24 on: Aug 5th, 2008, 8:09pm » |
Quote Modify
|
on Aug 5th, 2008, 2:05pm, Janzert wrote:
Thanks for the link. I read that entire flame war, and I am amazed that so many smart people (including Hyatt himself) could fail to see what is wrong with his tests. The flaw in his methodology is right there in the information he provides, yet all the blistering attacks fail to point out how he could fix his test. I'm registering for an account in that forum just so that I can explain.
Anyway, here is the Elo difference that can be detected (at 95% confidence) by various sizes of test suites:
Positions Points
--------- ------
30 . 133
100 . 70
300 . 40
1000 . 22
3000 . 13
10000. 7
So I don't expect you (having no cluster) to be able to detect fine improvements in playing strength, but Hyatt should be able to...
|
| « Last Edit: Aug 5th, 2008, 8:10pm by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: search tree techniques
« Reply #25 on: Aug 5th, 2008, 8:21pm » |
Quote Modify
|
Ahh, so you're saying that the number of starting positions he uses is too low? I wondered about that. Won't this vary, at least somewhat, by how much the games vary from the particular positions?
And wow, I read a good portion of the flamefest but it got to be rather too much for me to finish all of it. I'm also afraid that anything you might post will have a very difficult time overcoming the built up emotions.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: search tree techniques
« Reply #26 on: Aug 5th, 2008, 9:15pm » |
Quote Modify
|
on Aug 5th, 2008, 8:21pm, Janzert wrote:| Ahh, so you're saying that the number of starting positions he uses is too low? |
|
Yes, exactly. Multiple playouts from the same position will not be mathematically independent. If you work out the math, enough dependence means his results are not at all extreme, certainly not on the order of winning the lottery.
Quote:| Won't this vary, at least somewhat, by how much the games vary from the particular positions? |
|
Hmmm, I'm not sure what you are asking. Are you talking about variations in the playouts or variations among the set of positions?
Quote:| I'm also afraid that anything you might post will have a very difficult time overcoming the built up emotions. |
|
That's OK. It's worth writing it up just to clarify it in my own mind.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: search tree techniques
« Reply #27 on: Aug 5th, 2008, 9:39pm » |
Quote Modify
|
on Aug 5th, 2008, 9:15pm, Fritzlein wrote:
Hmmm, I'm not sure what you are asking. Are you talking about variations in the playouts or variations among the set of positions? |
|
Variation in the playouts. To expand a little; a position from which the exact same game always results would give no information content at all. As well it would seem a position that either ends with the same side or same player always winning would seem to give no information either. Of course these are the extreme cases of zero information being given. Conversely doesn't the maximum amount of information that can be gained from a single position depend on how much the playouts differ, i.e. the difference in the two sets of possible games that can result from the position under the specific conditions of the testing?
Janzert
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: search tree techniques
« Reply #28 on: Aug 5th, 2008, 11:03pm » |
Quote Modify
|
on Aug 5th, 2008, 4:09pm, Janzert wrote:| It is tried at any number of steps into a move as long as it isn't in the middle of a push. |
|
But wouldn't you agree with the reasoning behind why having a fixed 4-step reduction then should be problematic?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: search tree techniques
« Reply #29 on: Aug 6th, 2008, 6:56am » |
Quote Modify
|
on Aug 5th, 2008, 9:39pm, Janzert wrote:| Variation in the playouts. To expand a little; a position from which the exact same game always results would give no information content at all. As well it would seem a position that either ends with the same side or same player always winning would seem to give no information either. Of course these are the extreme cases of zero information being given. Conversely doesn't the maximum amount of information that can be gained from a single position depend on how much the playouts differ, i.e. the difference in the two sets of possible games that can result from the position under the specific conditions of the testing? |
|
Yes, your intuition is exactly right. There is a maximum information that can be extracted from a single position if it's playouts have _any_ dependence. If there is no variation in results, then the first trial tells you all you will ever know. On the other extreme, if each playout was an independent representation of the population of positions as a whole, then repeated playouts of one position would be just as good as playouts from new positions. The variance would grow linearly with the number of trials, so the standard deviation (square root of variance) gets proportionally smaller in the square root of the number of trials.
The in-between case where there is some variation and some correlation is hard for me to describe, in part because I don't understand it perfectly, but here's the general idea. In addition to variance, you have covariance to consider. The repeated trials of the same position each have covariance with each other. With one repetition, there are zero correlated pairs. With two repetitions, there is one correlated pair. With three repetitions, there are three pairs, and with four repetitions there are six pairs. As you see, the number of covariance terms is increasing quadratically, because the number of correlated pairs is increasing quadratically.
Now your standard deviation is the square root of (variance plus covariance). Before the variance was growing linearly in the number of trials, so taking the square root was driving the proportion as low as we wanted. But with the covariance growing quadratically, taking the square root means we are just breaking even. Asymptotically sqrt(x)/x can be made arbitrarily small, but sqrt(x + cx(x-1))/x is bounded by sqrt(c). This is the floor to what we are going to learn from repetition. And if c=1, then the expression is constant in x, i.e. we learned everything on the first trial.
The correlation between repeated playouts, expressed in the constant c, can be greater or lesser depending on how random the playouts are. In any case, however, there is an absolute bound to what we can learn from this one position even if we run an infinite number of trials on it.
I don't know if this handwaving math leaves you any better off than you were with your straight intution, but it's the best I can do for now! 
|
| « Last Edit: Aug 6th, 2008, 7:01am by Fritzlein » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print