Author |
Topic: Lemmings (Read 2292 times) |
|
Hippo
Forum Guru
Arimaa player #4450
Gender: 
Posts: 883
|
For a long time I didn't want to implement special lemming prevention.
Now I have decided to try some.
I have started with the most trivial case ... when only one player piece moves.
There is a complication that sometimes losing the piece improves the player position.
It happened for example at
http://arimaa.com/arimaa/gameroom/opengamewin.cgi?client=1&gameid=14 5655&role=v&side=w
when rabbit at c5 was obstacle to captures at c6 so it's move to b4 was improvement even when it could be captured there (as it was on c5).
Other obstacles could happen during goal prevention ... delaying goal by piece sacrifice could create path for permanent solution.
Another obstacle could happen in goal attacking ... the sacrified piece could blocked friendly rabbit from goaling.
So without understanding obstacles avoiding lemmings could worsen play (in rare cases).
|
|
 IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
 |
Re: Lemmings
« Reply #1 on: Jul 24th, 2013, 8:18am » |
 Quote  Modify
|
Good example. In my bot I have some unsafe prunning (although not lemmings yet), for a while I've been thinking about turning it into reductions instead, perhaps a reduction of 1 or 2 plies. So those moves would still be detected as good, they would just take more depth to be found.
The reduction could be different depending on how safe the pruning is. Moves that are very unlikely to be good might have a bigger reduction.
|
| « Last Edit: Jul 24th, 2013, 8:23am by rbarreira » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Lemmings
« Reply #2 on: Jul 24th, 2013, 3:41pm » |
Quote Modify
|
on Jul 24th, 2013, 8:18am, rbarreira wrote:Good example. In my bot I have some unsafe prunning (although not lemmings yet), for a while I've been thinking about turning it into reductions instead, perhaps a reduction of 1 or 2 plies. So those moves would still be detected as good, they would just take more depth to be found.
The reduction could be different depending on how safe the pruning is. Moves that are very unlikely to be good might have a bigger reduction. |
|
Oh not meaning the move is searched to lower depth, just that the move is considered only when remaining depth is bigger that some treshold. That makes sense (otherwise the lemming is even more encouraged).
This could be helpfull especially in goal situations, when the search could go deeper.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Lemmings
« Reply #3 on: Jul 25th, 2013, 6:14am » |
Quote Modify
|
on Jul 24th, 2013, 3:41pm, Hippo wrote:
Oh not meaning the move is searched to lower depth, just that the move is considered only when remaining depth is bigger that some treshold. That makes sense (otherwise the lemming is even more encouraged).
This could be helpfull especially in goal situations, when the search could go deeper. |
|
If you look at LMR (late move reductions) in chess, they do a reduced depth search just to see if the move might be worth it, and if it returns a high score (for the player doing the lemming move) then the move is checked with full depth.
You're right that the lemmings case is a bit special, it's exactly the kind of move which might often look good with a reduced depth search... So there are several things to test and experiment here.
The method you proposed would avoid that problem, although it could still cause mistakes, for example a loss score could be returned even though the lemming move has not been tried yet (because the depth is not high enough). In this case the depth will never increase as a loss score can be treated as absolute truth, in the normal way of thinking about a minimax search. Then again, this can be treated as a special case (if the current score is a loss then all moves are tried).
|
| « Last Edit: Jul 25th, 2013, 6:19am by rbarreira » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Lemmings
« Reply #4 on: Jul 25th, 2013, 9:54am » |
Quote Modify
|
More general definition of lemming could be ... the small sacrifice which delayes bigger capture. Searching deep enough would find its better to let the bigger piece go saving us all the small sacrifices.
The lemming move just puts the high capture move above the horizon.
In this case lowering depth of search for the lemming move would encourage lemming even when otherwise the search would be deep enough. Of course full depth research would cure that, but it would be run almost always so the depth reduced search would be just loss of time.
The lemming prevention would try to increase the depth to see above the original horizon, but spending even more time on move we expect is bad ...
---
I agree that lemming cut should be avoided when alpha declares forced loss. But I still think detecting "the piece was an obstacle" would be better method to prevent lemming cut.
(Maybe searching the position without the piece to the full depth before allowing the lemming move in normal search? Of course the same obstacle should be tested just once ... not for each possible lemming it could make)
|
|
IP Logged |
|
|
|
Boo
Forum Guru
Arimaa player #6466
Gender:
Posts: 118
|
|
Re: Lemmings
« Reply #5 on: Jul 25th, 2013, 12:43pm » |
Quote Modify
|
I think that usually lemmings defense occures as a result of a poorly implemented "strongest free piece" concept in the evaluation function.
Luckily for humans "strongest free piece" is hard to programm  E.g. 21g looks terrible positional mistake, allowing M as SFP in
http://arimaa.com/arimaa/games/jsShowGame.cgi?gid=269594&s=b
Bot is happy to capture the cat, but gets the elephant pinned and eventually is forced to use the lemmings.
I think bot would improve much more if it had SFP implemented (and possibly played another 21g e.g. Hg4n cf4e hf5s Ee5e) if compared to recognising lemmings. E.g. it could try to sacrifice the Mh6 in move ~40 moving E towards c3, which would only result in a different losing line.
|
| « Last Edit: Jul 25th, 2013, 12:47pm by Boo » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print