Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 10:06am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Capturing Moves »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Capturing Moves
« Previous topic | Next topic »
Pages: 1 2 3 4  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Capturing Moves  (Read 12042 times)
aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 768
Re: Capturing Moves
« Reply #30 on: May 28th, 2009, 6:14pm »
Quote Quote Modify Modify

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.
IP Logged
doublep
Forum Guru
*****



Badger author

   


Gender: male
Posts: 82
Re: Capturing Moves
« Reply #31 on: Oct 2nd, 2009, 1:17pm »
Quote Quote Modify Modify

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.
IP Logged
aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 768
Re: Capturing Moves
« Reply #32 on: Oct 3rd, 2009, 2:48am »
Quote Quote Modify Modify

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.
IP Logged
doublep
Forum Guru
*****



Badger author

   


Gender: male
Posts: 82
Re: Capturing Moves
« Reply #33 on: Oct 3rd, 2009, 6:02am »
Quote Quote Modify Modify

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.
IP Logged
lightvector
Forum Guru
*****



Arimaa player #2543

   


Gender: male
Posts: 197
Re: Capturing Moves
« Reply #34 on: Mar 28th, 2010, 8:50am »
Quote Quote Modify Modify

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.
 
« Last Edit: Mar 28th, 2010, 8:53am by lightvector » IP Logged
doublep
Forum Guru
*****



Badger author

   


Gender: male
Posts: 82
Re: Capturing Moves
« Reply #35 on: Mar 30th, 2010, 10:35am »
Quote Quote Modify Modify

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.
IP Logged
JimmSlimm
Forum Guru
*****




Arimaa player #6348

   


Gender: male
Posts: 86
Re: Capturing Moves
« Reply #36 on: Jun 24th, 2013, 5:35am »
Quote Quote Modify Modify

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 Smiley
 
I got a problem with these two different situations:
 
Code:

Should be: FALSE
|________|
|_Hr_____|
|_rx__x__|
|_D______|
|_e______|
|__x__x__|
|________|
|_______R|

Code:

should be: TRUE
|________|
|________|
|__x_rx__|
|____Dr__|
|____eE__|
|__x__x__|
|________|
|_______R|

 
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)
« Last Edit: Jun 24th, 2013, 5:41am by JimmSlimm » IP Logged
mattj256
Forum Guru
*****



Arimaa player #8519

   


Gender: male
Posts: 138
Re: Capturing Moves
« Reply #37 on: Jun 25th, 2013, 3:21am »
Quote Quote Modify Modify

Wow that's a hard one!  Thanks for the mental workout! Smiley
 
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
IP Logged
JimmSlimm
Forum Guru
*****




Arimaa player #6348

   


Gender: male
Posts: 86
Re: Capturing Moves
« Reply #38 on: Jun 25th, 2013, 4:09am »
Quote Quote Modify Modify

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:
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

I didn't think about that, it's a great idea, it would(should) speed up move generating as well as static capture detection
IP Logged
JimmSlimm
Forum Guru
*****




Arimaa player #6348

   


Gender: male
Posts: 86
Re: Capturing Moves
« Reply #39 on: Jun 25th, 2013, 4:51am »
Quote Quote Modify Modify

It doesnt work Sad
your second example:
Code:

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|

 
E can PULL to D, making it unfrozen, and D can push to capture
 
edit: Also, my first example:
Code:

Should be: FALSE  
|________|  
|_Hr_____|  
|_rx__x__|  
|_D______|  
|_e______|  
|__x__x__|  
|________|  
|_______R|  
1. The enemy pieces are on adjacent sides of the trap = TRUE (they don't share row OR column)
2. The frozen dominator is at the corner = TRUE

 
both conditions are true, but a capture is still impossible, did I misunderstand the conditions?
« Last Edit: Jun 25th, 2013, 4:58am by JimmSlimm » IP Logged
mattj256
Forum Guru
*****



Arimaa player #8519

   


Gender: male
Posts: 138
Re: Capturing Moves
« Reply #40 on: Jun 25th, 2013, 11:26pm »
Quote Quote Modify Modify

on Jun 25th, 2013, 4:09am, JimmSlimm wrote:
Wow, that's a excellent answer, I am impressed! And thanks for the examples you provided.

 
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. Smiley
 
And thanks for the mental workout.  Again.
IP Logged
Hippo
Forum Guru
*****




Arimaa player #4450

   


Gender: male
Posts: 883
Re: Capturing Moves
« Reply #41 on: Jun 26th, 2013, 3:16am »
Quote Quote Modify Modify

Is blocked piece considered frozen in the analysis? Otherwise there would be other false false protections with blockade preventing the captures...
IP Logged

JimmSlimm
Forum Guru
*****




Arimaa player #6348

   


Gender: male
Posts: 86
Re: Capturing Moves
« Reply #42 on: Jun 26th, 2013, 4:04am »
Quote Quote Modify Modify

Quote:
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

 
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:
Is blocked piece considered frozen in the analysis? Otherwise there would be other false false protections with blockade preventing the captures...

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. Tongue
 
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
« Last Edit: Jun 26th, 2013, 4:15am by JimmSlimm » IP Logged
harvestsnow
Forum Guru
*****





   


Gender: male
Posts: 88
Re: Capturing Moves
« Reply #43 on: Jun 26th, 2013, 9:12am »
Quote Quote Modify Modify

Quote:
The frozen dominator has to be at the corner where it's next to both enemy pieces.

I don't think so.
eg. Cat capture in F6:
 
|r.......|  
|.....c..|  
|..x.CEd.|  
|......H.|  
|......e.|  
|..x..x..|  
|........|  
|.......R|

 
 
 
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.
 
1. Defenders on adjacent sides:
.....
..a..
..xb.
.....
.....
 
1.1__   1.2__   1.3__   1.4__   1.5__
..U..   .....   .....   .....   .....
..aF.   .UaF.   ..aU.   ..aF.   ..a..
..xb.   ..xb.   ..xbF   ..Ub.   ..Ub.
.....   .....   .....   .....   ...F.
.....   .....   .....   .....   .....
 
2. Defenders on opposite sides:
 
.....
..a..
..x..
..b..
.....
 
2.1__   2.2__
.....   .....
.Ua..   ..a..
..x..   ..U..
.Fb..   .Fb..
.....   .....
 
 
3. Defenders on adjacent sides, ennemy piece (c) on the trap:
 
.....
..a..
..cb.
.....
.....
 
3.1__   3.2__   3.3__
..U..   .....   .....
..aF.   .UaF.   ..aU.
..cb.   ..cb.   ..cbF
.....   .....   .....
.....   .....   .....
 
 
4. Defenders on opposite sides, ennemy piece on the trap:
 
.....
..a..
..c..
..b..
.....
 
4.1__  
.....
.Ua..
..c..
.Fb..
.....

 
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:
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.
 
« Last Edit: Jun 26th, 2013, 11:33pm by harvestsnow » IP Logged
JimmSlimm
Forum Guru
*****




Arimaa player #6348

   


Gender: male
Posts: 86
Re: Capturing Moves
« Reply #44 on: Jun 26th, 2013, 9:46am »
Quote Quote Modify Modify

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 Tongue
IP Logged
Pages: 1 2 3 4  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.