Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> attempt for a positional evaluator for MC method
        
(Message started by: pago on Oct 17^th, 2013, 11:39am)

Title: attempt for a positional evaluator for MC method
Post by pago on Oct 17^th, 2013, 11:39am

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

Title: Re: attempt for a positional evaluator for MC meth
Post by JimmSlimm on Oct 17^th, 2013, 12:47pm

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 :)

Title: Re: attempt for a positional evaluator for MC meth
Post by pago on Oct 17^th, 2013, 2:12pm

I haven't tried it: I have not the programming skills to do a bot.

Title: Re: attempt for a positional evaluator for MC meth
Post by JimmSlimm on Oct 17^th, 2013, 5:06pm

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 :)

Title: Re: attempt for a positional evaluator for MC meth
Post by crazyharry on Oct 17^th, 2013, 6:11pm

on 10/17/13 at 14:12:36, 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?

Title: Re: attempt for a positional evaluator for MC meth
Post by pago on Oct 18^th, 2013, 2:07pm

on 10/17/13 at 18:11:25, 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 :P

Title: Re: attempt for a positional evaluator for MC meth
Post by Hippo on Oct 18^th, 2013, 3:26pm

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

Title: Re: attempt for a positional evaluator for MC meth
Post by pago on Oct 19^th, 2013, 12:33am

[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 ???

Title: Re: attempt for a positional evaluator for MC meth
Post by JimmSlimm on Oct 20^th, 2013, 1:32pm

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

Title: Re: attempt for a positional evaluator for MC meth
Post by pago on Oct 21^st, 2013, 1:17pm

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.

Title: Re: attempt for a positional evaluator for MC meth
Post by JimmSlimm on Oct 21^st, 2013, 1:48pm

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