Welcome, Guest. Please Login or Register.
Jun 24th, 2019, 11:31pm

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum Detecting Forks


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Detecting Forks
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Detecting Forks  (Read 2589 times)
leon_messerschmidt
Forum Senior Member
****



Arimaa player #6344

   


Gender: male
Posts: 26
Detecting Forks
« on: Aug 7th, 2014, 6:22am »
Quote Quote Modify Modify

Ignoring for a moment that my bot (playing silver in the example below) makes some strategic errors in pushing a dog forward too early, I seem to have a problem with recognising complex up forks.
 
My evaluation function determines that the dog at e3 is relatively safe because the friendly elephant can move to the f3 trap while the c3 trap is guarded by the friendly camel.  The bot also thinks the camel at b3 is relatively safe because the friendly elephant can come to the rescue.
 
Basically each one of the c3 and f3 traps look safe in isolation and only too late does my bot find itself in the position where its elephant can't be at two places at once and loses a dog.
 
Code:

 +-----------------+
8|_r_r_r_r_____r_r_|
7|_r___d_c_c_r___h_|
6|_____X_____X_h___|
5|___________e_____|
4|_______C_________|
3|___m_X_E_d_X_M___|
2|_H_H_D___C_D___R_|
1|_R_R_R___R_R_R_R_|
 +-----------------+
   a b c d e f g h
 
PNG =  Ra1 Rb1 Rc1 Re1 Rf1 Rg1 Rh1 Ha2 Hb2 Dc2 Ce2 Df2 Rh2 Ed3 Mg3 Cd4  mb3 de3 ef5 hg6 ra7 dc7 cd7 ce7 rf7 hh7 ra8 rb8 rc8 rd8 rg8 rh8

 
 
This is not a simple textbook fork and I'm not sure how to protected against it.  The most obvious solution is to do deeper searches, but Arimaa is no good for that.  I could increase the weight for straight forward capture threats (aiming at the camel threat at c3) but that may make the bot too sensitive to trivial threats.
 
I've played around with a factor to punish weaker pieces being to close to the enemy elephant but then the bot moves pieces away from the elephant rather than defending traps with 2 or 3 pieces.
 
Anyone care to share any ideas on how not to land yourself in this situation?
IP Logged
JimmSlimm
Forum Guru
*****




Arimaa player #6348

   


Gender: male
Posts: 86
Re: Detecting Forks
« Reply #1 on: Aug 7th, 2014, 7:21am »
Quote Quote Modify Modify

You can give a huge penalty if capture is possible in 2 traps at the same time
IP Logged
jdb
Forum Guru
*****



Arimaa player #214

   


Gender: male
Posts: 682
Re: Detecting Forks
« Reply #2 on: Aug 7th, 2014, 8:40am »
Quote Quote Modify Modify

To detect forks, keep track of what pieces can be captured into each trap. If a piece can be captured into two traps, it is forked.
 
Most tactics in arimaa involve overloading a piece. In the given position the silver elephant is overloaded. To detect overloaded pieces, keep track of what pieces have a job to do. In the above position, the silver elephant has a job around both the c3 and f3 trap, so it is overloaded.
IP Logged
leon_messerschmidt
Forum Senior Member
****



Arimaa player #6344

   


Gender: male
Posts: 26
Re: Detecting Forks
« Reply #3 on: Aug 16th, 2014, 6:18am »
Quote Quote Modify Modify

After some experimentation I think for the given position it actually works better to punish pieces that are frozen next to an unprotected trap (the dog at e3 in this case) than to try and to detect the fork directly.  It is cheaper to compute and I suspect less prone to being taken advantage of by human opponents.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Detecting Forks
« Reply #4 on: Aug 20th, 2014, 8:58am »
Quote Quote Modify Modify

Is your evaluation symmetrical?  I ask because imposing a penalty big enough to prevent it from being exploited by humans in a certain way might then cause the reverse situation when the bot thinks it is beating up on a human when it isn't really.  In this particular case, the bot might be thrilled to freeze a piece next to a trap in a case when the human isn't actually threatened by it.
 
I bring this up because of the elephant blockade experience.  Developers worked really hard to prevent their bots from falling into elephant blockades, but sometimes they penalized it so much that the bots would go crazy on the other side of the coin, trying to create elephant blockades of their own that weren't worth anything, or at least not worth as much as they were willing to sacrifice to get the blockade.
 
Indeed, I wonder how many developers solved the blockade problem without resorting to asymmetry, e.g. "If my elephant gets blockaded it is -3.5, but if I blockade your elephant is it only +0.5."
IP Logged

leon_messerschmidt
Forum Senior Member
****



Arimaa player #6344

   


Gender: male
Posts: 26
Re: Detecting Forks
« Reply #5 on: Aug 20th, 2014, 4:09pm »
Quote Quote Modify Modify

My evaluation function is completely symmetrical so I could easily get into these kinds of issues.  I didn't have to add a huge weight to pieces frozen next to an unprotected trap to solve this particular situation, so I should be fine.
 
However, since I added this weight my bot seems much more likely to get its camel taken hostage.  Thinking out loud, it may make sense to adjust weights so that "my camel taken hostages is -3.5 but taking the opponents camel hostage is +0.5".
IP Logged
Janzert
Forum Guru
*****



Arimaa player #247

   


Gender: male
Posts: 1014
Re: Detecting Forks
« Reply #6 on: Aug 20th, 2014, 6:02pm »
Quote Quote Modify Modify

on Aug 20th, 2014, 8:58am, Fritzlein wrote:
Indeed, I wonder how many developers solved the blockade problem without resorting to asymmetry, e.g. "If my elephant gets blockaded it is -3.5, but if I blockade your elephant is it only +0.5."

 
I'd be surprised to hear that a bot didn't have a symmetric* evaluation. But given that you'd apparently be somewhat surprised if it wasn't common I'm really curious to know if, and how commonly, bots are doing this.
 
Janzert
 
 
* i.e. treating a position differently depending on which side it was playing
IP Logged
Pages: 1  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.