Author |
Topic: attempt for a positional evaluator for MC method (Read 3562 times) |
|
pago
Forum Guru
Arimaa player #5439
Gender: 
Posts: 69
|
 |
attempt for a positional evaluator for MC method
« on: Oct 17th, 2013, 11:39am » |
 Quote  Modify
|
This is an attempt for a positional evaluator that could be used with a Monte-Carlo search without overestimating rabbit advance.
The general idea is to calculate for each piece a kind of “distance” to trap threat and goal threat. It assumes to calculate it that the opponent is free to play all the move. The evaluation of one side nearness to victory is the addition of all these “distance”. This positional evaluator doesn’t need a complementary material evaluation.
Detailed description :
1) Let GOLD side play consecutively ALL THE MOVES without letting silver play.
1.a) Calculate the Rabbit distance to goals
goal distance(Gold) = minimal number of step necessary for the closest Gold Rabbit to reach the eighth rank.
For example, for Gold rabbit in F2, G2, H3 with no other piece around : Goal distance (Gold) = 5
1.b) Calculate for each silver piece the distance to trapping:
Trap distance[ silver piece] = minimal number of step necessary to trap the silver piece
For example, for a Gold Elephant in B2 and a silver camel in A2, it would require 6 steps for gold side to trap the camel (assuming that there are no other piece nearby the C3 trap).
Trap distance( camel ) = 6.
Nota 1: For a piece already trapped, Trap distance[ silver piece] = 0
Nota2 : Trap distance[elephant] = infinite
1.c) Calculate for each silver piece, the distance of threat:
Threat distance (silver piece) = Min [Trap distance[ silver piece] ; goal distance (Gold)]
With the previous examples : Threat distance(camel) = Min[6 ; 5] = 5
1.d) Calculate the global Gold victory nearness:
Victory nearness(Gold) = Sigma[Threat distance(silver piece)]
2) Repeat the same process for SILVER side by letting it playing ALL THE MOVES.
goal distance(silver) = minimal number of step necessary for one of silver Rabbit to reach the first rank.
Trap distance[ Gold piece] = minimal number of step necessary to trap the Gold piece
Threat distance (Gold piece) = Min [Trap distance[ Gold piece] ; goal distance (silver)]
Victory nearness(silver) = Sigma[Threat distance(Gold piece)]
3) Calculate the evaluator
Positional Evaluator = [Victory nearness(silver) – Victory nearness(Gold)]/ [Victory nearness(silver) + Victory nearness(Gold)]
Additional considerations:
Evaluator = +1 => Gold victory
Evaluator = -1 => silver victory
Goal distance and trap distance is not easy to calculate by traditional tree search. However, one can let gold and silver alternatively play a random game from the initial position to evaluate. By this way, goal distance and trap distance estimation would be improved at each game (the overestimation would gradually decrease).
|
|
 IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #1 on: Oct 17th, 2013, 12:47pm » |
Quote Modify
|
Have you tried this in practice? it looks like an interesting idea, in fact it's similiar to an idea I've had for a evaluator that I never tried 
|
|
IP Logged |
|
|
|
pago
Forum Guru
Arimaa player #5439
Gender:
Posts: 69
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #2 on: Oct 17th, 2013, 2:12pm » |
Quote Modify
|
I haven't tried it: I have not the programming skills to do a bot.
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #3 on: Oct 17th, 2013, 5:06pm » |
Quote Modify
|
My thoughts on how this could be implemented:
1. Generate all possible moves at the root, the number of unique moves is = M
2. Take note on how much time left we have to think = T
3. For each move, evaluate/run monte carlo for this long:
T / M
pago, would this be a good way to use it? It would be a interesting P1 bot
|
|
IP Logged |
|
|
|
crazyharry
Forum Senior Member
Arimaa player #7323
Gender:
Posts: 38
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #4 on: Oct 17th, 2013, 6:11pm » |
Quote Modify
|
on Oct 17th, 2013, 2:12pm, pago wrote:| I haven't tried it: I have not the programming skills to do a bot. |
|
If you have the time for it, I think maybe you should learn some code; you certainly seem to have a head for programming. Sounds like an interesting idea to me, who better to implement it than you?
|
|
IP Logged |
|
|
|
pago
Forum Guru
Arimaa player #5439
Gender:
Posts: 69
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #5 on: Oct 18th, 2013, 2:07pm » |
Quote Modify
|
on Oct 17th, 2013, 6:11pm, crazyharry wrote:
If you have the time for it, I think maybe you should learn some code; you certainly seem to have a head for programming. Sounds like an interesting idea to me, who better to implement it than you? |
|
I would like to learn SW development.
However with two young children I have not the time for that. In addition i would not know how to begin (C ? C++ ? python ?)
So i apply in advance 99of9's proposal for a collaborative development, assumin that this idea interests a developper 
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #6 on: Oct 18th, 2013, 3:26pm » |
Quote Modify
|
It's not too hard to generate ideas, but it's a lot of work not only with it's codding, but as well with testing how much which idea improves the resulting bot.
I don't expect this evaluator would help that much
(if Sigma means sum, the main problem I see with the evaluator is that losing pieces increases computed "probability of win", that somehow contradicts my experiences).
Of course one could generate changes ...
|
|
IP Logged |
|
|
|
pago
Forum Guru
Arimaa player #5439
Gender:
Posts: 69
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #7 on: Oct 19th, 2013, 12:33am » |
Quote Modify
|
[quote author=Hippo link=board=devTalk;num=1382027972;start=0#6 date=10/18/13 at 15:26:04
(if Sigma means sum, the main problem I see with the evaluator is that losing pieces increases computed "probability of win", that somehow contradicts my experiences). [/quote]
I don't understand this part of the comment: in the evaluator losing piece decreases (not increases) the probabiliry of win...
As far as I understand the post, idea sharing does'nt seem to be a good idea 
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #8 on: Oct 20th, 2013, 1:32pm » |
Quote Modify
|
Code:
........
........
..xcEM..
........
........
..x..x..
........
........
|
|
pago, how should the evaluator deal with this case? The cat can be captured in 2 steps, but that means the camel also dies.
edit: Alternative way of representing the problem:
Code:
........
.....md.
..xcEMcd
.....eh.
........
..x..x..
........
........
|
|
In other words, when the capture threat requires collateral damage, the evaluator needs to take the collateral damage into account somehow
|
| « Last Edit: Oct 20th, 2013, 1:43pm by JimmSlimm » |
IP Logged |
|
|
|
pago
Forum Guru
Arimaa player #5439
Gender:
Posts: 69
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #9 on: Oct 21st, 2013, 1:17pm » |
Quote Modify
|
JimmSlimm,
Your remark points out one of the defects of the evaluator.
Maybe would it be better to change the definition of trap distance as folloWing:
Trap distance[ silver piece] = minimal number of step necessary to trap the silver piece "without losing a gold piece"
in your 1st example, trap distance(c) would be 3 instead of 2 (one additional step for M to evacuate the trap.
In the 2nd example, assuming a Horse in H5, the trap distance would be 6 (2 steps to pull d+ 2 steps for M to push c + 2 steps for E to trap c.
Of course in this 2nd example M would remain threatened by e but the evaluator shall not be a systematic tree search but remain a global estimation of threats.
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: attempt for a positional evaluator for MC meth
« Reply #10 on: Oct 21st, 2013, 1:48pm » |
Quote Modify
|
Yeah that's an acceptable solution. I was trying to come up with another scenario where the gold camel became a cat and the silver cat became a camel(some situation where it would be worth sacrificing for a fast capture), but after thinking about it for a while, I think your solution would probably be acceptable as well.
The best way to test this idea, is of course by implementing in a bot. I agree with crazyharry, you should really learn to code and put all of your ideas to the test! I've heard people saying it's about as difficult as learning a new language(like english, spanish, french etc.).
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print