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

        Arimaa >> General Discussion >> Material evaluation question
        
(Message started by: aaaa on Apr 9th, 2007, 8:31pm)
Title: Material evaluation question
Post by aaaa on Apr 9th, 2007, 8:31pm
Materially speaking, if we restrict ourselves to simply considering whether one side is better off than the other and not by how much, can one simply evaluate a position by considering the two sides separately such that there is in fact a ranking imaginable of the sets of pieces one side can have? Or can someone give an example of sets such that they exhibit a cyclic relationship in the sense of preferring to have one combination with the opponent having the other, e.g. "I'd rather have pieces A versus B and B versus C, but not A versus C"?
Title: Re: Material evaluation question
Post by The_Jeh on Apr 9th, 2007, 11:59pm
If you had 16 different Arimaa pieces and put any number >0 of them on the board, you would have 65,535 combinations to choose from.  Because several Arimaa pieces are copies of each other, the true number of material combinations is somewhat lower, but still relatively high.  It would be imaginable to rank all the combinations, but not practical.
Title: Re: Material evaluation question
Post by RonWeasley on Apr 10th, 2007, 7:27am
Most players agree that material sets, not considering position, are transitive in value.  There are threads discussing ways to quantify this.  One system is called FAME (Fritzlein's Asomething Material Evaluator).  It attempts a general algorithmic comparison of asymmetric material sets independent of position.  99of9 has a system too.  I haven't looked for where these threads are, but try looking in the bot developers' forum.

In reality, the value of asymmetric material sets depend heavily on position, so the transitivity question has not been explored.  Because the piece relationships are transitive, I expect piece sets to also be transitive.  I can't even think of how a rabbit's goal ability would break transitivity.
Title: Re: Material evaluation question
Post by 99of9 on Apr 10th, 2007, 8:09am
I'd rather have (5R) than (ER).

I'd rather have (ER) than (EMHH).

I'd rather have (EMHH) than (5R).

DAPE agrees (but not always for the right reasons).
Nice challenge aaaa.
Title: Re: Material evaluation question
Post by aaaa on Apr 10th, 2007, 11:21am

on 04/09/07 at 23:59:39, The_Jeh wrote:
If you had 16 different Arimaa pieces and put any number >0 of them on the board, you would have 65,535 combinations to choose from.  Because several Arimaa pieces are copies of each other, the true number of material combinations is somewhat lower, but still relatively high.  It would be imaginable to rank all the combinations, but not practical.

You're being way too loose in calculating an upper bound there. For each piece type, one can have from 0 to the maximum of that type, i.e. given a piece type, the number of possibilities for it is one more than the starting number. That means that there are merely (and exactly) 2*2*3*3*3*9=972 different combinations of pieces (including the empty set).


on 04/10/07 at 08:09:30, 99of9 wrote:
I'd rather have (5R) than (ER).

I'd rather have (ER) than (EMHH).

I'd rather have (EMHH) than (5R).

DAPE agrees (but not always for the right reasons).
Nice challenge aaaa.

Can you also think of more realistic examples where the elephant is present in every situation? I can never imagine deliberately losing it except when there is a forced goal.

I understand of course that even if piece sets are transitive, one would still like to assign a number to one's advantage over the other side in order to assess whether a trade is favorable because the estimated advantage is higher with the resulting opposing piece sets. Then the question becomes whether one can estimate this advantage adequately simply by giving a number to each piece set separately and calculating the difference.
Title: Re: Material evaluation question
Post by The_Jeh on Apr 10th, 2007, 11:50am
You're right.  My upper bound doesn't take into account symmetrical positions. I've been having trouble lately thinking before I post.  Sorry.
Title: Re: Material evaluation question
Post by IdahoEv on Apr 10th, 2007, 2:14pm
Last summer in a thread about material analysis I proposed a notation system that correctly collapses equivalent material states, for example it recognizes that EMRerr is the functionally the same as EHRerr and ECRerr.  The first proposal for this system can be found in this thread (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;num=1146199776), though I later refined it a bit so that states collapse "downward" instead of "upward" because that came up with more sane values in the material eval functions I was designing.

Basically you represent the material state as a series of numbers representing the functional level of the piece in terms of how many pieces remaining on the board are effectively "smaller" or "larger" than them.  The starting position is 112228-112228, with the left six numbers representing gold's pieces.   If gold's two cats are captured, this reduces to 112208-112228.  But if silver's two cats are captured, this reduces to 011228-011228:  effectively dogs become cats (they are now the smallest piece that can capture rabbits), horses become dogs, and so forth.

Someone who is better at combinatorics than I could use this system to compute the actual number of functionally equivalent combinations that can exist.   It's not super trivial, since the collapse function depends on which pieces actually are present on *both sides*.   Maybe I'll write a program to count the states one of these days, it wouldn't be too hard since i've already implemented the collapse function.
Title: Re: Material evaluation question
Post by woh on Apr 10th, 2007, 3:43pm
I allways like to do some numbers. So here we go.

Considering just one player, of the 972 combinations as mentioned by aaaa, 279 are unique taking IdahoEv's collapsing equivalent combinations into account. (Including the combination where the player has no pieces left.)

For the combinations with 2 players there are more than 279*279 possibilities because one can only collapse when both players are missing some kind of piece. Eg 112027 and 110227 are considered equivalent for one player. In combination with an opponent who has 112217, 112027-112217 and 110227-112217 are not equivalent. The total number adds up to 545049 unique states including those where either player or both players have no pieces left and 544492 without those.

If anyone is interested how I got those numbers, let me now and I'll post the calculations.
Title: Re: Material evaluation question
Post by jdb on Apr 10th, 2007, 4:05pm
The starting position is 112228-112228.

111128-110028
110228-110028
011228-011028

I think these are also all equivalent.
Title: Re: Material evaluation question
Post by IdahoEv on Apr 10th, 2007, 8:06pm
JDB's three positions are indeed equivalent.  Or, rather, the first two positions do not exist in Arimaa because they are not fully collapsed; only the third position is a legitimate position.

Woh, I am definitely interested in how you did the math.   I'm skeptical of computing the total by figuring the number of positions for one player and then squaring it to get the total, because positions including zeros in mid-string are only legal when they are matched against a position that does not have a zero in the same place.   So positions with zeros must be counted, but they can't be considered against all opposing combinations, only some.

Note that positions with two sequential zeros mid-string are never legal because they always cause a level collapse in the opposing player's string.
Title: Re: Material evaluation question
Post by woh on Apr 10th, 2007, 8:35pm

on 04/10/07 at 16:05:22, jdb wrote:
The starting position is 112228-112228.

111128-110028
110228-110028
011228-011028

I think these are also all equivalent.


Good point, jdb!
In my calculations the 2nd and 3th combination were equivalent but the first wasn't.



on 04/10/07 at 20:06:48, IdahoEv wrote:
Note that positions with two sequential zeros mid-string are never legal because they always cause a level collapse in the opposing player's string.


This is exactly what I had missed. I didn't find a way to take that into account, so I let the computer count the number of unique combinations. The result was 447040.


I suppose that 011228-011028 and 011028-011228 are also equivalent. In that case we're down to 223659 combinations.
Title: Re: Material evaluation question
Post by 99of9 on Apr 10th, 2007, 9:47pm

on 04/10/07 at 11:21:21, aaaa wrote:
Can you also think of more realistic examples where the elephant is present in every situation? I can never imagine deliberately losing it except when there is a forced goal.

Heh, sorry, I'm a theorist, realism often doesn't come into my criteria.

I can't immediately think of a normal non-transitive position.  I think they are quite rare (as Ron suggested), and I had to construct that other one quite carefully.
Title: Re: Material evaluation question
Post by NIC1138 on Apr 10th, 2007, 10:01pm

on 04/10/07 at 20:35:48, woh wrote:
I suppose that 011228-011028 and 011028-011228 are also equivalent. In that case we're down to 223659 combinations.

I was going to say that! ;) But is it true?... In a purely "materialistic" player program, if we consider the fact that it´s our turn, and take different values for symmetrical states, would this be already a non-materialistic variable? And does it matter? Interesting problem!...  8)
Title: Re: Material evaluation question
Post by woh on Apr 10th, 2007, 10:05pm

on 04/10/07 at 20:06:48, IdahoEv wrote:
Woh, I am definitely interested in how you did the math.   I'm skeptical of computing the total by figuring the number of positions for one player and then squaring it to get the total, because positions including zeros in mid-string are only legal when they are matched against a position that does not have a zero in the same place.   So positions with zeros must be counted, but they can't be considered against all opposing combinations, only some.


This is how I got my first result.

First I calculated the number of combinations where L1...L5 are all occupied. At L1 and L2 each player can have either 0 or 1 piece. But at least one player must have 1 piece, so 3 combinations. At L3, L4 and L5 8 of the 9 combinations are valid. LR gives 81. Total = 3*3*8*8*8*81 = 373248.
Then for one level collapsed: 3*8*8*8*81 = 124416.
Two levels collapsed: 8*8*8*81 = 41472
3 -> 8*8*81 = 5184
4 -> 8*81 = 648
5 (only rabbits) -> 81
Grand total: 373248+124416+41472+5184+612+81=545049 (or 272664 when states like 011228-011028 and 011028-011228 are equivalent)

For the 2nd result I subtracted the combinations where either player or both players have no pieces left.
With L1...L5 all occupied only 1 player can have 0 pieces left. The other player must have at least 1 pieces at least level except for the rabbits. So I get 373248 - 2*(1*1*2*2*2*9) = 373104
Then for one level collapsed: 124416 - 2*(1*2*2*2*9) = 124272.
Two levels collapsed: 41472 - 2*(2*2*2*9) = 41328
3 -> 5184 - 2*(2*2*9)= 5112
4 -> 648 - 2*(2*9) = 612
5 (only rabbits) -> 64
Grand total: 373104+124272+41328+5112+648+64=544492 (or 272385 when states like 011228-011028 and 011028-011228 are equivalent)
Title: Re: Material evaluation question
Post by aaaa on Apr 10th, 2007, 11:04pm

on 04/10/07 at 20:35:48, woh wrote:
This is exactly what I had missed. I didn't find a way to take that into account, so I let the computer count the number of unique combinations. The result was 447040.

This is with both sides having at least some pieces. Otherwise the count is 447201.


Quote:
I suppose that 011228-011028 and 011028-011228 are also equivalent. In that case we're down to 223659 combinations.

Same story. 223740 if including empty sides.
Title: Re: Material evaluation question
Post by woh on Apr 11th, 2007, 6:02am

on 04/10/07 at 23:04:01, aaaa wrote:
This is with both sides having at least some pieces.


Yes, I only considered combinations with both players having at least one piece in those counts.
Title: Re: Material evaluation question
Post by aaaa on Apr 12th, 2007, 12:38am
I've managed to come up with a collapse function that outputs a canonical combination that's in the same form as the input.
Title: Re: Material evaluation question
Post by pago on Sep 16th, 2010, 10:50am



Quote:
can someone give an example of sets such that they exhibit a cyclic relationship in the sense of preferring to have one combination with the opponent having the other, e.g. "I'd rather have pieces A versus B and B versus C, but not A versus C"?


The most plausible cycle I have found at this time with the third version of my evaluator in development is:
EMHC8R > EHDD8R > EDDCC8R > EMHC8R

EDDCC8R > EMHC8R is the most controversial inequality although in that case M worth only H
Title: Re: Material evaluation question
Post by 99of9 on Sep 16th, 2010, 8:47pm

on 09/16/10 at 10:50:25, pago wrote:
EDDCC8R > EMHC8R is the most controversial inequality although in that case M worth only H

You're right, that's highly controversial.  I definitely disagree with this, and would prefer to play with the MH=HH than the DDC.
Title: Re: Material evaluation question
Post by pago on Sep 17th, 2010, 2:31am

Quote:
You're right, that's highly controversial.  I definitely disagree with this, and would prefer to play with the MH=HH than the DDC.  


The controversial effect is a consequence of the relative value given to the pieces by my evaluator.

I can propose the following cycles that use relative values closer to the current consensus :

EMC8R>EHCC8R>EDDC8R>EMC8R
Or
EMDC8R>EHDCC8R > EDDCC8R > EMDC8R

They use the following relative values between pieces :
M>HC>DD > H
M>HC>DC > H

Nota : If one thinks that the relative value of M differs, it should not be difficult to build an other cycle...
Title: Re: Material evaluation question
Post by aaaa on Sep 18th, 2010, 11:35am
Here is what several evaluators consider a cycle, even without any rabbit ever being off: EMC8R>EHH8R>EDCC8R>EMC8R
Title: Re: Material evaluation question
Post by rbarreira on Sep 18th, 2010, 11:56am

on 09/18/10 at 11:35:40, aaaa wrote:
Here is what several evaluators consider a cycle, even without any rabbit ever being off: EMC8R>EHH8R>EDCC8R>EMC8R


Wow, that one is a good find, especially since the differences between the successive comparisons are not very small either. If you sum them up you would think that EMC8R is quite a lot better than EMC8R.
Title: Re: Material evaluation question
Post by pago on Sep 19th, 2010, 6:28am

Quote:
Here is what several evaluators consider a cycle, even without any rabbit ever being off: EMC8R>EHH8R>EDCC8R>EMC8R


I also like this one.

I wonder whether someone could exhibit a cycle with rabbits that would not be controversial
Title: Re: Material evaluation question
Post by pago on Sep 28th, 2010, 9:17am

I propose the following cycle with one additional step (4 setups) :

EMDC8R > EHHC8R > EHDD8R > EDDCC8R > EMDC8R

I have not found a cycle of 5 steps with 8 rabbits. I assume that they could be possible with an unbalanced number of rabbits but they would be more controversial because of the difficulty to evaluate the relative value of rabbits.
Title: Re: Material evaluation question
Post by pago on Sep 30th, 2010, 5:13am

Hereafter are two plausible cycles with unbalanced number of rabbits.
They are almost confirmed by the test performed by jdb with clueless (more precisely there is no obvious contradiction with jdb's results).

They are not as trivial as cycles with equal number of rabbit. So I would be curious to know if someone could explain how they work (assuming that they do exist !) and if "old" players would agree or disagree with them.


1) EDD7R > EDDCC4R > ECC8R > EDD7R

jdb’s results :
EDD7R / EDDCC4R : +3 / -2
EDDCC4R / ECC8R : +3 / -1
ECC8R / EDD7R : +2 / -2


2) ED8R > EDD6R > EDDCC3R > ED8R

jdb’s results :
ED8R / EDD6R : +2 / -2
EDD6R / EDDCC3R : +4 / -1
EDDCC3R / ED8R : +3 / -1


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