Author |
Topic: Detecting Forks (Read 3500 times) |
|
leon_messerschmidt
Forum Senior Member
Arimaa player #6344
Gender: 
Posts: 26
|
 |
Detecting Forks
« on: Aug 7th, 2014, 6:22am » |
 Quote  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:
Posts: 86
|
|
Re: Detecting Forks
« Reply #1 on: Aug 7th, 2014, 7:21am » |
Quote 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:
Posts: 682
|
|
Re: Detecting Forks
« Reply #2 on: Aug 7th, 2014, 8:40am » |
Quote 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:
Posts: 26
|
|
Re: Detecting Forks
« Reply #3 on: Aug 16th, 2014, 6:18am » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Detecting Forks
« Reply #4 on: Aug 20th, 2014, 8:58am » |
Quote 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:
Posts: 26
|
|
Re: Detecting Forks
« Reply #5 on: Aug 20th, 2014, 4:09pm » |
Quote 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:
Posts: 1016
|
|
Re: Detecting Forks
« Reply #6 on: Aug 20th, 2014, 6:02pm » |
Quote 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 |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print