Welcome, Guest. Please Login or Register.
Mar 19th, 2024, 5:44am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Include mobility in an evaluation function ? »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Include mobility in an evaluation function ?
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Include mobility in an evaluation function ?  (Read 2698 times)
Stanley
Forum Junior Member
**



Arimaa player #2048

   


Gender: female
Posts: 9
Include mobility in an evaluation function ?
« on: Nov 19th, 2006, 7:40am »
Quote Quote Modify Modify

I have just read the analysis at http://arimaa.janzert.com/bf_study/  Congratulations, Janzert, your study is of great importance for dimensioning the "Arimaa problem".
 
What seems very interesting to me, and perhaps there are some additional graphs that may be easy to obtain is: The strong correlation between winning chances and mobility (defined as number of possible moves). (see the graph "bysidegoal.png" near the center of the page). May be, evaluation functions should have that "in mind".
 
I suggest extending the analysis in two directions:
 
1. Taking 3 or 4 snapshots at specific turns, (E.g. after move 20, 30, 40 and 50) and developing for that moment the complete distribution of mobility for the winning/loosing ratio. I explain: From the graph, at move 60 one can conclude that the winner has (approx) three times more mobility than the looser. What I would like to know is: How is that ratio distributed? Is the winner (almost) always ahead in mobility? A graph representing (winner mobility)/(looser mobility) distribution after move 30, 40, etc. would answer these questions. That would answer the question of how relevant is being ahead in mobility.
 
2. Something else, I think, may be useful for an evaluation function is a decomposition of mobility by pieces. I mean, repeating the graph ("bysidegoal.png") in five separate graphs for each type of piece: elephant mobility, camel mobility, etc. The 4 steps of a move should be attributed to pieces of the color in turn. The piece moving or the piece pushing or pulling and opponent's piece.
 
Of course, mobility-evaluation will necessarily have to be considered together with some other evaluation (maximizing mobility by itself is pointless) and it is also significantly slower than something like FAME. Exchanging speed (and therefore evaluating less nodes) for a "broader vision", . . may be, or may be not Wink
 
 
IP Logged
Janzert
Forum Guru
*****



Arimaa player #247

   


Gender: male
Posts: 1016
Re: Include mobility in an evaluation function ?
« Reply #1 on: Nov 19th, 2006, 8:28pm »
Quote Quote Modify Modify

Thanks, I'm glad to hear you found it of interest.
 
Suggestion 1 would be something interesting to know and shouldn't be too hard to do.
 
Unfortunately, while number 2 would be quite interesting it would also take quite a bit more to set up and would be infeasible for me to run over the whole set of games played. Looking at just HvH or even some subset of that would probably still be interesting though.
 
Also since once again the trend of doubling the number of Arimaa games played each year seems to continue1. It would be interesting to compare graphs from this year to the previous years.
 
Janzert
 
1 From the time the game record starts in 2002 through the end of 2005 there were 23022 total games and 1447 HvH games. Year to date 2006 there have been 19817 games and 1256 HvH games. Although there are a few duplicate games that still need to get weeded out of those numbers, extending them to the year end puts it at 22394 games and 1419 HvH games.
IP Logged
Stanley
Forum Junior Member
**



Arimaa player #2048

   


Gender: female
Posts: 9
Re: Include mobility in an evaluation function ?
« Reply #2 on: Nov 22nd, 2006, 12:09pm »
Quote Quote Modify Modify

Hi
 
I think the first part would be enough for the moment, since it may show if this is a promising idea or not. If there are really few cases in which superior mobility leads to a loss, then it seems a good idea.  Further in-depth study may go in that (dividing by pieces) direction or in new directions someone else may suggest. I am just getting a picture of how complicated it is and what kind of development tools can be used. In the beginning of next year, I expect to have more time and I could also help if you want. That, of course, if nobody wins the price this year Wink
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Include mobility in an evaluation function ?
« Reply #3 on: Nov 23rd, 2006, 10:24am »
Quote Quote Modify Modify

I was excited by Janzert's mobility analysis at the time, but when I looked through some results for specific games, I conluded quickly (too quickly?) that the total number of moves available isn't much help for evaluation.
 
The trouble is that most of the total move count comes from moving four pieces one step each.  Therefore, there is a strong correlation between total moves available and one-step moves available.  You can increase your total mobility substantially by moving a cat from the second rank to the third rank, if the advanced cat has four one-step options compared to two one-step options for the cat on the second rank.  But advancing the cat is wrong in most situations.
 
With mobility, as with other empirically-derived evaluators, there is a great difficulty distinguishing between cause and effect.  Yes, gaining a winning position might be a partial cause of increased mobility.  This might create a strong correlation between superior mobility and winning in recorded games.  Yet increasing your mobility for its own sake may not cause a better position at all, and indeed may cause a worse position.
 
The only mobility term that seems plausible to me is the number of different four-step moves the elephant can make on its own.  But even that is problematic.  In a camel-hostage situation, the hostage-holding elephant will usually have fewer options than the elephant defending the trap, yet practically speaking, the defending elephant has little mobility, because moving away will lose a camel.
 
All this is not to discourage you, Stanley, but apart from purely material evaluation, it seems very hard to get a decent machine evaluation of a position.  
IP Logged

Stanley
Forum Junior Member
**



Arimaa player #2048

   


Gender: female
Posts: 9
Re: Include mobility in an evaluation function ?
« Reply #4 on: Dec 3rd, 2006, 12:02pm »
Quote Quote Modify Modify

Thank you, Fritzlein.
 
I was not considering mobility by itself, just to decide differences assuming equal material evaluation, but you have (almost) convinced me. You know the game much better, and have explored this possibility before. I am not after another evaluation function for global minimax search. I don't know if Arimaa is hard for all computer methods, but it is certainly hard for chess-like global minimax search. I would like to try something more goal-oriented, where the maximum goal is rabbit in the last line, but captures are interesting goals as well. In that sense, Arimaa has a small set of interesting goals (8 target cells + 4 traps x 16 pieces = 72 goals for each player). Of course, when a goal is feasible the right line of play is clear, but when it is not, some evaluation function could help "navigating in the fog".  
 
IP Logged
pago
Forum Guru
*****



Arimaa player #5439

   
Email

Gender: male
Posts: 69
Re: Include mobility in an evaluation function ?
« Reply #5 on: Oct 12th, 2010, 10:57am »
Quote Quote Modify Modify


 
Sorry from exhuming very old topics...
 
One other explaination of the correlation between the mobility and the winning chances could be linked to the space advantage factor.
 
The side that has a space advantage has a positional advantage and a consequence of this space advantage is a better mobility as measured by Janzert.
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.