|
||||||
|
Title: Capturing Moves Post by jdb on Aug 6th, 2005, 1:17pm I am working on generating all possible capture moves from a given position. I am looking for static tests that can rule out the possibilitiy of a capture on a given trap. Here are the three I use now: 1) Enemy elephant touching trap 2) Three or more enemy pieces touching trap 3) 1 non dominated enemy piece AND any other enemy piece touching trap. A dominated piece is a piece that is touching a stronger enemy piece. In a normal position these tests eliminate around 30-40% of the traps. Any ideas for some more simple tests? |
||||||
|
Title: Re: Capturing Moves Post by 99of9 on Aug 7th, 2005, 7:24pm 4) Two enemy pieces touching the trap that are both dominated by the same friendly piece AND neither are dominated by any others. 5) One enemy piece touching the trap that has no dominating friendly pieces within 3 steps of it. 6) No friendly pieces within 1 step of the trap AND no dominated friendly pieces 2 steps from the trap. 7) No friendly pieces within 2 steps of the trap :-). Do you want more like these, or are these too strange? |
||||||
|
Title: Re: Capturing Moves Post by jdb on Aug 8th, 2005, 8:25am These are exactly what I was looking for. The actual generation of the capture moves is hundreds of times more expensive than these simple tests. So they don't have to be true very often to be effective. 4 and 5 are great, but I dont quite follow number 6 and 7. Could you please explain these a little more? I don't see how they handle this case: 1w Ec5 2b rf5 8 ) No enemy piece within two steps of the trap. |
||||||
|
Title: Re: Capturing Moves Post by 99of9 on Aug 8th, 2005, 6:25pm Arrgghh, sorry, I mixed up friendly and enemy teams in 6 and 7. So my rule 7 should read the same as your rule 8. 9) No friendly piece within 4 steps of the trap. (So even if they're hanging a rabbit, we can't get to it.) [EDIT actually this turns out to be a less-discerning version of #5] [EDIT rule 7 also turns out to be a less-discerning version of #6] |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 12th, 2005, 11:56am Why don't you just build a trap-local search decision tree? It's simpler than I though. I make one that solve all up tp 3-step cases( about 30-40 totally), it only takes about 200 lines of code, and make a 5-ply search almost as good as an 8-ply search. The number of 4-step cases is less than 60, so it is also doable. Goal-local search has much more cases and is harder to build. |
||||||
|
Title: Re: Capturing Moves Post by jdb on Aug 12th, 2005, 2:29pm Haizhi, What is a "trap-local search decision tree"? What is "goal-local search"? Thanks |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 13th, 2005, 11:10pm Sorry for my clumsy english. Is there any chance you speak Chinese, Jeff? ::) Here is something from my paper: For every position at level 4n+m (0≤m<4), we calculate the possibility that any enemy piece can be trapped in the next 4-m steps, and subtract the material value of the most valuable piece that can be trapped from the evaluation score. Therefore, search step 4n+m (0≤m<4) will give us a roughly a 4n+4 step result. A piece at c4, c5, f4, f5, d3, e3, d6 or f6 can be captured into two different traps. For these squares, the threats from both sides need to be calculated. During the process of trapping an enemy’s piece, sacrificing a friendly piece may be unavoidable. In this case, the evaluation depends on the comparison of the values of the lost piece and the gained piece. For every position at level 4n+m (0≤m<4), we check the possibility that any Rabbit of the player to move can achieve the goal in the next 4-m steps, and if so score the situation as infinite (win) or minus infinite (lost). It can discover an unavoidable win or loss situation up to 4 steps earlier, saving further search and greatly improving the performance of the endgame play. The difficulty in finding out the situation of trapping or reaching the goal in 4 steps is obvious. There are many different paths. Pulling, pushing, blocking, freezing and supporting: all these rules make the situation very hard to handle. The easiest way to solve the problem is to generate all the legal moves of the next turn. This method is simple to implement, but not practical due to the time-consuming cost of move generation. To make the program fast, we have to use decision trees to handle all the trapping and goal situations case by case. |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 13th, 2005, 11:15pm In Fotland's evaluation function, there is also a trap/goal evaluating decision tree (in fact we got this idea from him). But he doesn’t evaluate trap/goal by completing unfinished steps left in the current move as we did. Instead, he statically evaluates how many steps it will take to trap each piece on the board (1 to 6 steps) or have each Rabbit reach the goal (1 to 8 steps), assuming no intervening moves by the opponent. I think my way is simpler and easy to understand. |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 13th, 2005, 11:20pm So far our decision tree can handle all the cases that take up to 3 steps to trap or goal, but the 4 steps cases are not accomplished yet. Step Trap case Goal case ≤1 1 1 ≤2 3 4 ≤3 10 29 ≤4 >40 >100 Table 3.2: Number of trap evaluation and goal evaluation cases. Table 3.3 shows the result of trap and goal evaluation. It can make a 5-step search roughly equivalent to an 8-step search, which is a great improvement. It also helps to give Iterative Deepening a better move ordering. Implementing the cases for all 4 steps will make it better, but considering the difficulty involved, it is not critical. Search Roughly equivalent search Without ≤4 With ≤4 5-7 step 8 step 8 step 8 step 11 step 12 step 9-11 step 12 step 12 step 12 step 15 step 16 Step Table 3.3: Result of trap evaluation and goal evaluation. Sorry, I cannot make it more readable. |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 13th, 2005, 11:23pm Step Trap case Goal case ---------------------------------------------- >=1 1 1 >=2 3 4 >=3 10 29 >=4 >40 >100 Table 3.2: Number of trap evaluation and goal evaluation cases. Search Roughly equivalent search Without <=4 With<=4 ------------------------------------------------------------ 5-7 step 8 step 8 step 8 step 11 step 12 step 9-11 step 12 step 12 step 12 step 15 step 16 Step Table 3.3: Result of trap evaluation and goal evaluation. Better? |
||||||
|
Title: Re: Capturing Moves Post by PMertens on Aug 14th, 2005, 12:08am nice :-) how much time does this safe you ? |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 14th, 2005, 2:19am on 08/14/05 at 00:08:05, PMertens wrote:
I beg your pardon? |
||||||
|
Title: Re: Capturing Moves Post by jdb on Aug 14th, 2005, 8:48am Thanks for your detailed and informative reply. Quote:
Your english is fine. I was just unfamiliar with the terms you used. Sorry, I don't speak Chinese. If I understand correctly, A decision tree answers a question with a boolean result. A local search generates the actual moves satisfying a specific objective. I think a decision tree is a good way to go for the goal search. The number of cases to consider is formidable. Clueless has about 900 lines of code to detect goals and there are still cases it will miss. For the capture search, actually generating the moves can be helpful. During the search, clueless generates these moves first. It makes a huge difference in move ordering. A decision tree is most useful at the leaves. Capture move generation can be used anywhere in the search tree. Your approach of considering each enemy piece individually is interesting. Clueless analyzes each trap square individually. Quote:
I disagree with this. Having full four step goal detection is very important. It prunes the search tree very efficiently in endgame situations. |
||||||
|
Title: Re: Capturing Moves Post by PMertens on Aug 14th, 2005, 10:36am on 08/14/05 at 02:19:17, haizhi wrote:
I would be interested how much faster is your solution compared to a full move generation ? |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 14th, 2005, 4:06pm Oh, I shouldn't use the word "local search" and "decision tree" together, it was confusing. In fact it is only a decision tree, almost nothing with "search". Jeff, I think we were talking diffrent stuff. By finding all the capture moves, You were trying to do some forward pruning, and I am trying to better the evaluation. I didn't test the capture/goal moves in the move generation, so no any pruning there. But in evaluation, I try to adjust their final scores based on what these nodes will go with the unseached steps in the same turn. If we only consider material and goal in the evaluation, with all 3-step cases implemented, we can make a 5-ply search working as an 8-ply search. A normaly 5-ply search find I can capture a dog and think it is a good move, but with the "capture decition tree" a 5-ply search will find that doing so we will lost a horse in the next turn. Normally we need a 8-ply seach to find that. Imlementing all the 4-step cases can make a 4-ply search working as an 8-ply search, of course it is better, but I still don't think it's very critical. (I confess that got this conclusion is partially because I am too lazy.) See, Pmertens, my approach doesn't make a bot any faster, but make it much stronger with same search depth for sure. |
||||||
|
Title: Re: Capturing Moves Post by Janzert on Aug 14th, 2005, 9:11pm Just for comparison purposes though. What is the average time to do a 5 step+decision tree search compared to the same position with a full 8 step search and no decision tree? I think this is what PMertens is getting at, and I'd also be interested in hearing the answer. Janzert |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 14th, 2005, 10:32pm Oh, the decision tree in the evaluation function doesn't make the program visibly slow. A 5-ply search with it is almost as fast as a normal 5-ply search, cost less than 1 sec per move. Normally my bot take about 5-10 sec to finish a 8-ply search. |
||||||
|
Title: Re: Capturing Moves Post by PMertens on Aug 14th, 2005, 11:07pm That is what I wanted ;-) nice ... So until now its only 3 step because you are lazy ? Do you think it might make sense to make even more than 4 steps ? If you dont want to type the code yourself, how about letting the computer generate it (once, in advance) ? |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 15th, 2005, 1:00pm search <=3 <=4 4 4 8 5 8 8 6 8 8 7 8 8 8 8 12 9 12 12 10 12 12 11 12 12 12 12 16 Well, before blaming my laziness, let me explain more. See the table above. The difference that the 4 step captrue/goal cases will bring is only when we search 4n step deep. In a 3 minutes time limit, I can not finish a 12-step search, so no matter the depth of our finished search is 9 or 11, what I get is still a roughly 12-step result. That is why I am not so eager to implement 4 step cases into my bot. There is another reason makes the 12-step an ugly bottleneck: transportation tables doesn't work if the search is less than 3 moves (12 step). Automatic generate a decision tree? Theoritcally it is doable, but is it worth it? I don't think it is a good idea to make it deeper than a complete turn(4 steps). However, Fortland's decision tree is as deep as 6-step or 8-step. I cannot imagine how can he accomplished that. |
||||||
|
Title: Re: Capturing Moves Post by PMertens on Aug 15th, 2005, 1:04pm sorry about the lazyness comment - just quoted you there ;-) 8-step ? that is very interesting. I will have to experiment with this. Thanks for sharing this information. Why don't you think it is a good idea to make it deeper ? |
||||||
|
Title: Re: Capturing Moves Post by jdb on Aug 15th, 2005, 1:41pm Quote:
Maybe we're talking about different things here, but transposition tables will still help if the search is less than 12 steps. 1w Ra1 Rb1 Rc1 1b ea7 One search could be: 2w Ra2 Rc2 Another could be: 2w Rc2 Ra2 The second one will be a hit in the transposition table. Quote:
True, it is most useful at a 4n step deep search, but it still can be used at the other levels. In the search, finish out the turn with pass steps. Then run the 4step goal search. If the opponent can goal, then the static eval on the position (before the pass steps) is highly questionable and the position needs to be looked at in more detail. Quote:
I agree. After 4 steps, the opponent has four steps to mess up your plans anyway. What would be the benefit of a five step goal search? I highly doubt Fotland's goal search detects 8 step wins. I would guess it detects situations that will require *at least* 8 steps to win. This is alot easier to do. |
||||||
|
Title: Re: Capturing Moves Post by haizhi on Aug 15th, 2005, 2:27pm Jeff, my bot only generates all the distinct moves, all other moves are pruned before search. I agree with you, 4-step cases can help even it is not a 4n step search. I will implement it before the end of this year. I carefully read Fortland's paper word by word, but was still not very clear what he did in his captrue/goal decition tree. PMertens, nothing you said needs a "sorry". :o |
||||||
|
Title: Re: Capturing Moves Post by aaaa on May 6th, 2009, 1:56pm on 08/14/05 at 23:07:07, PMertens wrote:
on 08/15/05 at 13:00:02, haizhi wrote:
I've just succeeded in doing exactly this with respect to goal patterns. |
||||||
|
Title: Re: Capturing Moves Post by BlackKnight on May 8th, 2009, 11:26am on 05/06/09 at 13:56:53, aaaa wrote:
|
||||||
|
Title: Re: Capturing Moves Post by aaaa on May 8th, 2009, 12:58pm on 05/08/09 at 11:26:42, BlackKnight wrote:
I used retrograde analysis to incrementally determine all possible combinations of features necessary for goaling and then constructed a covering decision tree. Quote:
I would think so, given that my bot now needs practically no time to prevent any preventable goals-in-two by the opponent and it can even find some winning goals-in-three under tournament time controls (e.g. RonWeasley's famous elephant sac). Quote:
Most definitely not. I'm already severely pushing it, with the generated code running in the tens of thousands of lines! To get above-mentioned behavior, I just let the search extend on goal threats (once), for a relatively cheap combined increase in search depth of 8 steps for the purpose of finding goals. Suffice it to say that swindling Quad should be a whole lot of harder now. |
||||||
|
Title: Re: Capturing Moves Post by jdb on May 8th, 2009, 1:04pm on 05/08/09 at 12:58:57, aaaa wrote:
This is similar to what clueless does. I think it is pretty much an essential component for a bot. |
||||||
|
Title: Re: Capturing Moves Post by Fritzlein on May 27th, 2009, 6:30pm Congratulations, aaaa. I'm not a programmer, but achieving perfect static goal detection with an automatically generated decision tree sounds like quite a feat to me. Thanks for using that new feature to verify all the missed goal-in-three opportunities from my Challenge game against Clueless. Out of curiosity, what does your bot now think of the position before move 37g in game 47333? Can it avoid the forced loss that Bomb fell into, and if so how long does it take to settle on the correct move? |
||||||
|
Title: Re: Capturing Moves Post by aaaa on May 27th, 2009, 10:48pm For now I can tell that chessandgo's 36s rh3s rh6s rh5s is not goal in three. 37g Ef5e Eg5e rh4s Eh5s for one prevents it long enough. |
||||||
|
Title: Re: Capturing Moves Post by aaaa on May 28th, 2009, 12:20pm It takes my bot almost 14 minutes to discover that 37g He3w rf3w Hf4s Ef5s loses, but well over two hours to find 37g Ef5e Eg5e Eh5s Eh4s as an alternative. It wasn't able to determine that that's the only non-losing move before I aborted the process. I'm very close to accomplishing the same thing with regard to captures and I need the CPU cycles. |
||||||
|
Title: Re: Capturing Moves Post by Fritzlein on May 28th, 2009, 2:43pm OK, so we're not quite up to avoiding goal in three in a live game, but getting within hailing distance. Even playing the non-losing move after two hours is impressive, because I don't think any other bot finds the non-losing move at all! Thanks for checking this out. I don't want to pull you away from perfecting your static capture detection, but a possibly interesting exercise could be run on my Challenge game with Clueless. You say you verified that I missed eight goal-in-three opportunities, and there were no more. Your bot is clearly going to avoid any goal-in-two losses, but how many of those eight goal-in-three situations would it have avoided, given two minutes to think in each situation? (I'm assuming that Clueless could have avoided each goal-in-three if it had been smarter, but I could be wrong about that, in which case I must have at some point played the starting move of a forced goal-in-four without realizing it.) |
||||||
|
Title: Re: Capturing Moves Post by aaaa on May 28th, 2009, 6:14pm If I'm understanding you correctly, you are asking me whether my bot would be able to recognize that a move would give the opponent goal-in-3 under tournament time controls. That comes down to a nominal search depth of 16 steps. Unless virtually all the possible first moves are immediately recognized as losing, I can already say right now that what you are asking for is simply way too much. |
||||||
|
Title: Re: Capturing Moves Post by doublep on Oct 2nd, 2009, 1:17pm aaaa, how did you test your implementation? I.e., how are you certain that it is indeed complete? I'm currently struggling with writing something similar. |
||||||
|
Title: Re: Capturing Moves Post by aaaa on Oct 3rd, 2009, 2:48am You could try putting conditional code in the bot that looks out for false positives and negatives by verifying static detections dynamically and vice versa respectively. |
||||||
|
Title: Re: Capturing Moves Post by doublep on Oct 3rd, 2009, 6:02am That's basically what I'm doing. In my case I don't build source code, but rather a pattern database which is then processed with a fairly simple matcher. I.e. the hard part is to build the database, not the matcher. And it turns out to be *huge*. I also struggle with filtering away 'excessive' patterns --- those which include simpler subpatterns, i.e. contain some not really needed requirements. Like "there must be an own piece at c5", but in fact the move will work fine without it --- so the pattern is excessive and is not needed in the database. Removing such patterns helps to at least keep the database size in reasonable limits. Maybe I miss something, but here the pattern generator is very complicated (despite still being incomplete) and quite slow. Without automated regression testing in systemic way I wouldn't be able to write it for sure. |
||||||
|
Title: Re: Capturing Moves Post by lightvector on Mar 28th, 2010, 8:50am For testing my capture and goal trees, I ran them over the entire database of games ever played here on this site. That is, for every game, for every position reached after every step, for each player in that position, I ran a 4 step search (as if it were the start of that player's turn) and compared it with the static tree. If it works over every position that has ever occurred in a game of Arimaa on this site, then it's probably good enough. Empirically, if I try to break the tree in any way, it's almost always detected within a few hundred games, and within a few thousand for rare corner cases. |
||||||
|
Title: Re: Capturing Moves Post by doublep on Mar 30th, 2010, 10:35am I combine similar automated verification with regression testing. I.e. if I find an error (either with automated play through the games or otherwise), I create a test for it. So, any changes can be tested quickly for whether they reintroduce a previously fixed bug. |
||||||
|
Title: Re: Capturing Moves Post by JimmSlimm on Jun 24th, 2013, 5:35am Sorry for bumping an old thread. I am trying to implement FAST, static capture detection in 4 steps and I really like the first few posts with the very simple rules :) I got a problem with these two different situations: Code:
Code:
I can't really explain why one is true and the other is false in a simple decision tree, at least not without using loops. Is there a simple rule (like the 1-9 rules in the first posts) to see the difference? edit: I should note that I am using bitboards, one ulong for each unit type and player(12 bitboards total) |
||||||
|
Title: Re: Capturing Moves Post by mattj256 on Jun 25th, 2013, 3:21am Wow that's a hard one! Thanks for the mental workout! :) First you need a false protection check, which I'm assuming you've already done. Then you need to check if it's "true" false protection or "false" false protection. (What I'm saying is clunky but you know what I mean.) We start with basic false protection. If two enemy units are next to a trap and they're dominated by two different friendly pieces, a capture might be possible. Then you layer in the "frozen" part. If both pieces are dominated and both dominators are unfrozen, then a capture is possible. If both dominators are frozen, the capture is impossible. (Unless it's possible by following some other rule, like if an enemy piece is dominated by multiple friendly pieces.) If one is frozen and one is not, the capture is possible if and only if: 1. The enemy pieces are on adjacent sides of the trap. 2. The frozen dominator is at the corner. Note that there are two squares where the nonfrozen dominator could be. A simple way to express "adjacent sides of the trap" is "next to the trap and sharing neither a row nor a column." A simple pattern you could check for is: enemies at b6 and c5, friendly at b5. There are 16 versions of this: each of the four traps has four corners. If this preliminary test doesn't pass then you don't have to do the rest of the test. Have you thought of adding two bitboards, one for each player, to keep track of which pieces are frozen? Otherwise you'll have to put that information into your static evaluation, which is probably a pain. |________| |________| |________| |________| |________| |________| |________| |________| |__x_rx__| |__x_rxr_| |__x_rx__| |__x_rx__| |____Dr__| |____D_E_| |____Dr__| |____Dr__| |____eE__| |____e___| |____eD__| |____eDC_| |__x__x__| |__x__x__| |__x__x__| |__x__x__| |________| |________| |________| |________| |_______R| |_______R| |_______R| |_______R| These are some examples to think about. My board #1 (left) is copied from your example. The capture is possible because after the elephant pushes it unfreezes the dog. In my second example there's no capture because the push doesn't unfreeze. (The push will always take the friendly piece into the square of the enemy piece, so the rule is "two enemies on adjacent corners to a trap.") My third example looks like the first, but now the dog is frozen and no capture is possible. And in my final example the dog is unfrozen and it becomes the same as the first example. Ok, this is super complicated and I hope I got it right. Good luck! Matthew |
||||||
|
Title: Re: Capturing Moves Post by JimmSlimm on Jun 25th, 2013, 4:09am Wow, that's a excellent answer, I am impressed! And thanks for the examples you provided. Later on I will upload my database with most of the example boards I have used to build my decision tree, I am sure it will help others, I accidentally deleted the first ones. However, at the time of writing this, there are more than 60. Quote:
I didn't think about that, it's a great idea, it would(should) speed up move generating as well as static capture detection |
||||||
|
Title: Re: Capturing Moves Post by JimmSlimm on Jun 25th, 2013, 4:51am It doesnt work :( your second example: Code:
E can PULL to D, making it unfrozen, and D can push to capture edit: Also, my first example: Code:
both conditions are true, but a capture is still impossible, did I misunderstand the conditions? |
||||||
|
Title: Re: Capturing Moves Post by mattj256 on Jun 25th, 2013, 11:26pm on 06/25/13 at 04:09:01, JimmSlimm wrote:
You're welcome. Yeah it took me forever and I knew that it would be still not fully correct. My thing that I was saying about a bitboard for frozen states.. I saw that in a bot somewhere, maybe Hippo_bot? Also one thing I've seen is, instead of having the bitboard represent a class of pieces (like cats), you have it represent that class and greater, like cats and greater. So if you want cats you do ("cats" AND NOT "dogs or greater".) This makes it slightly slower to figure out where the cats are, but it's much easier to do the "domination" checks that are so important for checking frozenness. Another thing I've seen is, rather than having six classes, if BOTH players have had all their cats captured, you drop that bitboard and now each player only has five bitboards. So dogs get demoted to cats, horses get demoted to dogs, and so on. Of course if you do that you have to make sure your evaluation function still works as expected. There's a thread about this somewhere but I don't have the energy to look it up. 1. The enemy pieces are on adjacent sides of the trap = FALSE (they share the same row) 2. The frozen dominator is at the corner = TRUE |________| |________| |__x_rxr_| |____D_E_| |____e___| |__x__x__| |________| |_______R| Yes, I was only thinking about push-push captures, but you're totally right. In my mind, there's one set of tests for push-push, one for push-pull, one for pull-push, and one for pull-pull. In this case the capture only works if you do pull-push, but if you take away the silver elephant both rabbits could be captured in two different ways each, for a total of four captures. In my mind, this case belongs in the category of the position where you remove the silver elephant, not the category of the push-push captures we're discussing. That's just how I think of it; you can do it however you want. But I think it's important to keep these positions in mental categories because otherwise I would go crazy. Should be: FALSE |________| |_Hr_____| |_rx__x__| |_D______| |_e______| |__x__x__| |________| |_______R| 1. The enemy pieces are on adjacent sides of the trap = FALSE (they share the same row) 2. The frozen dominator is at the corner = TRUE You're absolutely right. The frozen dominator has to be at the corner where it's next to both enemy pieces. Just being at a corner is not enough; it has to be at THAT corner. By the way, I don't know if you want to share all your cases? I've been thinking of building my own bot and it would be great if I didn't have to reinvent the wheel. :) And thanks for the mental workout. Again. |
||||||
|
Title: Re: Capturing Moves Post by Hippo on Jun 26th, 2013, 3:16am Is blocked piece considered frozen in the analysis? Otherwise there would be other false false protections with blockade preventing the captures... |
||||||
|
Title: Re: Capturing Moves Post by JimmSlimm on Jun 26th, 2013, 4:04am Quote:
While sleeping tonight, the PC have been running tests on all board positions since 2012, if a capture is available, and my current static capture detection thinks its not, the board have been saved. And vice versa for false positives. Should be at least 500 saved boards, alot of duplicates though. I'll upload them later today. Quote:
Yea with blocked pieces, there's a whole new world of problem cases. "Can this dominator push this enemy? Oh it doesn't have empty square around it, can we make space for it? Yea, we can move our own unit away from it, oh its frozen, can we get someone to unfreeze it? Yea, oh the unfreezer was blocked/frozen", etc. :P I've been thinking about automating the decision tree construction, but I suspect that the resulting static function from that would be slower than a manually constructed function edit: Here's over 1500 test cases, probably containing some cases that are duplicates regarding capture tactics: http://www.speedyshare.com/Rey9U/download/testcapture.zip |
||||||
|
Title: Re: Capturing Moves Post by harvestsnow on Jun 26th, 2013, 9:12am Quote:
I don't think so. eg. Cat capture in F6:
Would these tables help ? I think they catch all the cases of false protection with one frozen and one unfrozen attackers. My apologies if I missed something. The trap is always the central square. The ennemy trap defenders are noted a and b; the unfrozen dominator of a is noted U, the frozen dominator of b is noted F. The diagrams don't include the ennemy freezing pieces nor the friendly trap defenders (nor any piece that will be at the same place after the move). Any two subcases that differ by a horizontal flip, vertical flip or quarter rotation are considered identical (practically, you would need to either generate all the symmetrical cases or reduce the position to a normal state before checking it). The rotation isn't a problem, since the friendly rabbits won't move.
Each diagram allows one or several moves. Each move needs two particular free squares, and captures either a or b. The fact that F can be frozen by a leads to tricky cases. For instance, 1.1 allows 6 possible moves where U unfreezes F by contact. In short notation (http://arimaa.com/arimaa/learn/shortNotation.html): Ua< Fb< b* aU> Fb< b* Uav Fbv a* Uav Fb> a* Uav bF^ a* Uav bF> a* But two others are possible if F is only dominated by a: aU< Fb< b* aU^ Fb< b* with different required free squares. I can't think of a nice condition set that would summarize all these cases. They could be the basis of a decision tree: use the position of the defenders to choose the root case, then search the unfrozen dominator, and check the existence of the frozen one and the free squares. |
||||||
|
Title: Re: Capturing Moves Post by JimmSlimm on Jun 26th, 2013, 9:46am Interesting post, harvestsnow! Your minimalistic approach of representing the cases leads me to think that a lookup-table could be feasible for all possible scenarios with 2 defenders. A index/hash key as identifier would be needed for the lookup-table. Maybe it would require more time to make the key at runtime than using a decision tree though :P |
||||||
|
Title: Re: Capturing Moves Post by JimmSlimm on Jun 28th, 2013, 11:45am Update: I gave up on the 4step decision tree after working on it for over a week, it just took to much energy away from me :P Hopefully it will serve as a warning for others thinking about doing the same thing manually, it takes ALOT of time, probably more than most think. There are just SO many cases :) I made 2step+3step decision trees instead, doable in less than a day. So now, I generate all possible first steps, including push and pulls. And then check the decision tree after that, it has a huge impact on performance, I can only imagine what a full decision tree would do :) |
||||||
|
Title: Re: Capturing Moves Post by JimmSlimm on Oct 8th, 2013, 6:07am I have a 4-step capture decision tree now, it can certainly be improved in speed, and probably has some bugs, but it's good enough. To take it one step further, since fast decision trees/static capture evaluation is so important, has anyone made a 2-ply capture tree? That is, for example: "Can I capture a piece while at the same time NOT allowing opponent to capture any of my pieces?" or even better if you include what piece(s) to get captured: "What is the best material score I can get within 2 plies from this board state?" |
||||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |