|
||||||
|
Title: search tree techniques Post by Swynndla on May 20th, 2006, 8:01pm I'm wondering which bots use pruning or other similar techniques, and which don't. All I know so far is: - Gnobot 2005 & 2006 doesn't prune at all. - Clueless has a rabbit-only search extension? - Fairy (at the moment only) looks deeper at interesting moves, and shallower at bad moves. What does bomb use? Do any of these bots use alpha-beta pruning? |
||||||
|
Title: Re: search tree techniques Post by 99of9 on May 21st, 2006, 12:18am on 05/20/06 at 20:01:28, Swynndla wrote:
I expect all of them do. It is so standard that I don't even call it pruning! |
||||||
|
Title: Re: search tree techniques Post by Swynndla on May 21st, 2006, 5:40am Ohhhhhhhhhhhhhhh gotcha ... so Gnobot 2005 & 06 uses alpha-beta, but doesn't use any real pruning, nor any extensions right? |
||||||
|
Title: Re: search tree techniques Post by unic on May 21st, 2006, 3:14pm Fairy uses alpha-beta (of course), or to be more specific, nega-scout with aspiration windows at the root. I've been running tests on the looking shallower at bad moves lately - cutting search depth by 1 ply, half a ply, or not at all, makes no discernible change in playing strength. So, I'll probably remove that part (as if it makes no difference in strength, I'd rather go with the simplest version. Cutting search depth by 2 ply made it noticeably weaker. Bomb must use various techniques - probably both some pruning (or looking shallower at sequences) and extensions - setup a position in the downloadable bomb, hit Analyze, and look at its output - it gives depth as for example 9 (6-16) - so 9 depth, but real depth varying between 6 and 16. |
||||||
|
Title: Re: search tree techniques Post by unic on May 21st, 2006, 3:15pm on 05/21/06 at 00:18:23, 99of9 wrote:
I'd agree! Thing is, alpha-beta never changes the value of the root node... it never prunes parts of the search tree that might matter. Pruning, to me, generally refers to 'unsafe' pruning - which might (or might not) theoretically change the value of the root node. |
||||||
|
Title: Re: search tree techniques Post by Swynndla on May 21st, 2006, 4:00pm Ahh thanks for explaining all this to me (a newbie to games programming). I'm reading up on alpha-beta ... very interesting. So why is bomb so strong? ... I can't believe that it's because it has better evaluation, because clueless P1 seems to be stronger than bomb P1 ... so does this mean that it comes down to bombCC having better search tree pruning techniques than cluelessCC?? |
||||||
|
Title: Re: search tree techniques Post by Fritzlein on May 21st, 2006, 6:35pm on 05/21/06 at 16:00:04, Swynndla wrote:
In human strategy terms, Bomb is so strong because it understands trap control better than any other bot. It fights to gain control of a trap with more precision than other bots, and when it is doomed to lose control it gives up and cuts its losses sooner than other bots. Bomb isn't perfect at trap control by any means, but it is noticably the best of the bots. In computer science terms, Fotland said that Bomb does "quiescence search". I don't understand how that is possible. In chess, quiescence search means (I think) deepening the search only with capturing and checking moves. But in Arimaa a capture move can take the full four steps, so how can Bomb look at only capture moves without generating a lot of unwanted moves? Alternatively, if the unwanted moves are in there even temporarily, why isn't quiescence search prohibitively expensive? Apparently Fotland has found a way of looking at it that eludes everyone else to this day, at least a year and a half after he shared with everyone that he somehow manages to do quiescence search. I don't know nothing about coding, but from where I stand, it looks like Fotland is some kind of wizard. |
||||||
|
Title: Re: search tree techniques Post by seanick on Jun 16th, 2006, 2:59am I don't know what quiescence search is, or for that matter most of the ideas that are discussed here. yet. but just in case anyone didnt already find this I thought I would mention it .. the thread at http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display;num=1073334799 has a summary of what Fotland claims bomb has. Does he not plan on working on it anymore? it's too bad if that is the case. Would he be willing to sell the code? That time he spent writing it, at least 3 solid months of 40 hour weeks. I am sure that I am not the first to consider that way more very well developed code has been lost due to improper archiving, people leaving companies, companies going out of business, getting acquired, or the source being deleted by the new lab tech who didn't know what was on the drive that he had just formatted, etc. I suppose human knowledge continues to evolve and many systems continue to work without the source even existing anymore, but once we reach a certain point, if anything major breaks, life will become like that in Asimov's Nightfall. Anyway. Bomb is pretty good. So who is going to write the next logical successor? True AI with the additional ability to speak fluent arimaa notation, predict human oversight and accomodate server overload natively? :) |
||||||
|
Title: Re: search tree techniques Post by chessandgo on Jun 16th, 2006, 11:48pm Thanks for the link ! interesting ... still he doesn't technically explain why Bomb is so good :) As for the next bot ... well, we are here and he's not, so it's up to us ;) I'm giving a try, but I fear what Fotland writes in a mn takes me one hour ... Still I'm trying to implement Leo's idea of agents trying to achieve goals ... funny but interesting idea ;) Are you trying to program one, Nick ? I've not heard about Fairy recently ... neither about Nathan's progress ... jdb seems to have a lot of ideas to work on ... are there other people building their bot currently ? |
||||||
|
Title: Re: search tree techniques Post by 99of9 on Jun 17th, 2006, 2:54am I am working on a complete eval overhaul for Gnobby, but it is still a long way off. |
||||||
|
Title: Re: search tree techniques Post by seanick on Jun 17th, 2006, 7:25pm Are there any C++ runtime libraries for linux? the ideas I had for a bot are based on my methods of writing code for windows which may or may not actually work on linux. I could do it in C but then I would not be doing my best work. the reason I want to do it in C++ is to extend some level of evaluation to each of the nodes based on type, then have a list of options generated based on those evaluations and pick them by value to process at a global level. this would allow a much deeper search I think, and based on each object's view of the board which would allow goal based evaluation to be easier too. all of this would be possible with C I am sure but it starts to be complex enough to ensure all of the requirements are considered that it really wouldn't be as attractive an option. I may kick it around a few times anyway though. At the moment I have a few things to learn before I am ready to begin writing my bot. so it may yet be a while for me too. Are you bored with all of the current bots already? :P |
||||||
|
Title: Re: search tree techniques Post by Swynndla on Jun 19th, 2006, 4:55pm There may be more specific compilers on linux, I don't know, but the standard GNU linux compiler "gcc" is designed to compile many different languages, and C++ is one of them. Maybe this helps? ... http://gcc.gnu.org/onlinedocs/libstdc++/documentation.html |
||||||
|
Title: Re: search tree techniques Post by clauchau on Jun 20th, 2006, 6:11am on 05/21/06 at 18:35:10, Fritzlein wrote:
It must be similar to searching for goal moves, which is hard coded in some other bots as well. I think it has to go in increasing numbers of steps and keep those numbers at a tight minimum : - There are no capture possible in one step. - Captures in two steps are made of a push or a pull into an unprotected trap or a push or a pull of a lone trap-protector. - Captures needing three steps are those needing a step before capturing in two steps. That step can only be about getting the pushing or pulling piece next to the pushed or pulled enemy piece, or unfreezing that pushing or pulling piece, or emptying a needed target square. I think. - Captures in 4 steps... well, something a little more complicated along those lines. David Fotland is an engineering wizard :) |
||||||
|
Title: Re: search tree techniques Post by chessandgo on Jun 20th, 2006, 10:46am on 06/17/06 at 02:54:29, 99of9 wrote:
Good luck ! Nick : .... hum .... Well I'd like so much to see another bot get past Bomb :) |
||||||
|
Title: Re: search tree techniques Post by seanick on Jun 22nd, 2006, 11:44am I was looking for a good book on Game AI and found some interesting sites... for one, check out this article... http://ai-depot.com/LogicGames/MiniMax.html but that is just one step along the way, I still need more info to really understand the optimizations and extensions that need to be designed into mine. unfortunately it seems true AI wouldn't actually even be as good as a human at this game. |
||||||
|
Title: Re: search tree techniques Post by fotland on Aug 14th, 2006, 10:26pm 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). |
||||||
|
Title: Re: search tree techniques Post by Fritzlein on Aug 15th, 2006, 1:55pm on 08/14/06 at 22:26:33, fotland wrote:
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:
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:
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? |
||||||
|
Title: Re: search tree techniques Post by aaaa on Aug 5th, 2008, 12:22am on 08/14/06 at 22:26:33, fotland wrote:
Is that a good idea? Why do that instead of only doing the null-move pruning at the start of a player's turn? |
||||||
|
Title: Re: search tree techniques Post by Fritzlein on Aug 5th, 2008, 5:44am 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. ::) |
||||||
|
Title: Re: search tree techniques Post by aaaa on Aug 5th, 2008, 8:14am on 08/05/08 at 05:44:29, Fritzlein wrote:
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. |
||||||
|
Title: Re: search tree techniques Post by Fritzlein on Aug 5th, 2008, 12:11pm Perhaps Janzert, being particularly interested in depth reductions, will test this for us. ;) |
||||||
|
Title: Re: search tree techniques Post by Janzert on Aug 5th, 2008, 2:05pm 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 (http://64.68.157.89/forum/viewtopic.php?topic_view=threads&p=205019&t=22731) 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 |
||||||
|
Title: Re: search tree techniques Post by Fritzlein on Aug 5th, 2008, 2:37pm But do you do that 4-step reduction only after a pass, or also after 1-step, 2-step, and 3-step refutations? |
||||||
|
Title: Re: search tree techniques Post by Janzert on Aug 5th, 2008, 4:09pm It is tried at any number of steps into a move as long as it isn't in the middle of a push. Janzert |
||||||
|
Title: Re: search tree techniques Post by Fritzlein on Aug 5th, 2008, 8:09pm on 08/05/08 at 14:05:33, 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... |
||||||
|
Title: Re: search tree techniques Post by Janzert on Aug 5th, 2008, 8:21pm 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 |
||||||
|
Title: Re: search tree techniques Post by Fritzlein on Aug 5th, 2008, 9:15pm on 08/05/08 at 20:21:41, Janzert wrote:
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:
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:
That's OK. It's worth writing it up just to clarify it in my own mind. |
||||||
|
Title: Re: search tree techniques Post by Janzert on Aug 5th, 2008, 9:39pm on 08/05/08 at 21:15:41, Fritzlein 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? Janzert |
||||||
|
Title: Re: search tree techniques Post by aaaa on Aug 5th, 2008, 11:03pm on 08/05/08 at 16:09:35, Janzert wrote:
But wouldn't you agree with the reasoning behind why having a fixed 4-step reduction then should be problematic? |
||||||
|
Title: Re: search tree techniques Post by Fritzlein on Aug 6th, 2008, 6:56am on 08/05/08 at 21:39:22, Janzert wrote:
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! :P |
||||||
|
Title: Re: search tree techniques Post by Janzert on Aug 6th, 2008, 8:19am on 08/05/08 at 23:03:40, aaaa wrote:
Theoretically yes I can see that a fixed reduction (of any size) shouldn't be ideal. It doesn't violate my reasoning that led to using a 4 step fixed reduction though. That reasoning went more or less like this. I started with a 3 step fixed. Bumped it up to 4 steps and it seemed to be better. Bumped it up to 5 steps and it seemed worse. Tried half a dozen to a dozen different dynamic schemes and none of them seemed to be an improvement. So I just stuck with the simple fixed 4 step. :) Certainly it's not a resolved question and should be explored more in the future and probably changes on the depth of search being done as well. One thing about early bot development and OpFor is certainly still in this phase*, I believe it's more important to get reasonably working components in place than it is to get a perfect component before moving on to the next component. This philosophy pops up all over OpFor. For another example I used FAME material evaluation, not because I think it's the best possible but because I've implemented it before and knew I could do it quickly and it would provide do decent job in most situations. Janzert * Actually I think all Arimaa bots today are still in this phase. |
||||||
|
Title: Re: search tree techniques Post by Janzert on Aug 6th, 2008, 8:25am Thanks for the explanation Fritz. I'm sure the "handwaving" explanation helps me more than any other could. The next question would be how to measure the correlation, but I have a feeling that's where the handwaving has to be left behind. Janzert |
||||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |