Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Detecting Forks
        
(Message started by: leon_messerschmidt on Aug 7^th, 2014, 6:22am)

Title: Detecting Forks
Post by leon_messerschmidt on Aug 7^th, 2014, 6:22am

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?

Title: Re: Detecting Forks
Post by JimmSlimm on Aug 7^th, 2014, 7:21am

You can give a huge penalty if capture is possible in 2 traps at the same time

Title: Re: Detecting Forks
Post by jdb on Aug 7^th, 2014, 8:40am

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.

Title: Re: Detecting Forks
Post by leon_messerschmidt on Aug 16^th, 2014, 6:18am

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.

Title: Re: Detecting Forks
Post by Fritzlein on Aug 20^th, 2014, 8:58am

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."

Title: Re: Detecting Forks
Post by leon_messerschmidt on Aug 20^th, 2014, 4:09pm

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".

Title: Re: Detecting Forks
Post by Janzert on Aug 20^th, 2014, 6:02pm

on 08/20/14 at 08:58:14, 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