Welcome, Guest. Please Login or Register.
Dec 4th, 2024, 9:29am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « attempt for a positional evaluator for MC method »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   attempt for a positional evaluator for MC method
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: attempt for a positional evaluator for MC method  (Read 3565 times)
pago
Forum Guru
*****



Arimaa player #5439

   
Email

Gender: male
Posts: 69
attempt for a positional evaluator for MC method
« on: Oct 17th, 2013, 11:39am »
Quote Quote Modify 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: male
Posts: 86
Re: attempt for a positional evaluator for MC meth
« Reply #1 on: Oct 17th, 2013, 12:47pm »
Quote Quote Modify 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 Smiley
IP Logged
pago
Forum Guru
*****



Arimaa player #5439

   
Email

Gender: male
Posts: 69
Re: attempt for a positional evaluator for MC meth
« Reply #2 on: Oct 17th, 2013, 2:12pm »
Quote Quote Modify 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: male
Posts: 86
Re: attempt for a positional evaluator for MC meth
« Reply #3 on: Oct 17th, 2013, 5:06pm »
Quote Quote Modify 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 Smiley
IP Logged
crazyharry
Forum Senior Member
****




Arimaa player #7323

   


Gender: male
Posts: 38
Re: attempt for a positional evaluator for MC meth
« Reply #4 on: Oct 17th, 2013, 6:11pm »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 69
Re: attempt for a positional evaluator for MC meth
« Reply #5 on: Oct 18th, 2013, 2:07pm »
Quote Quote Modify 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  Tongue
IP Logged
Hippo
Forum Guru
*****




Arimaa player #4450

   


Gender: male
Posts: 883
Re: attempt for a positional evaluator for MC meth
« Reply #6 on: Oct 18th, 2013, 3:26pm »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 69
Re: attempt for a positional evaluator for MC meth
« Reply #7 on: Oct 19th, 2013, 12:33am »
Quote Quote Modify 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  Huh
IP Logged
JimmSlimm
Forum Guru
*****




Arimaa player #6348

   


Gender: male
Posts: 86
Re: attempt for a positional evaluator for MC meth
« Reply #8 on: Oct 20th, 2013, 1:32pm »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 69
Re: attempt for a positional evaluator for MC meth
« Reply #9 on: Oct 21st, 2013, 1:17pm »
Quote Quote Modify 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: male
Posts: 86
Re: attempt for a positional evaluator for MC meth
« Reply #10 on: Oct 21st, 2013, 1:48pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.