Author |
Topic: Material evaluation question (Read 3337 times) |
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
 |
Material evaluation question
« on: Apr 9th, 2007, 8:31pm » |
 Quote  Modify
|
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"?
|
| « Last Edit: Apr 9th, 2007, 10:58pm by aaaa » |
 IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender: 
Posts: 460
|
|
Re: Material evaluation question
« Reply #1 on: Apr 9th, 2007, 11:59pm » |
Quote Modify
|
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.
|
| « Last Edit: Apr 10th, 2007, 12:00am by The_Jeh » |
IP Logged |
|
|
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender:
Posts: 882
|
|
Re: Material evaluation question
« Reply #2 on: Apr 10th, 2007, 7:27am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Material evaluation question
« Reply #3 on: Apr 10th, 2007, 8:09am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Material evaluation question
« Reply #4 on: Apr 10th, 2007, 11:21am » |
Quote Modify
|
on Apr 9th, 2007, 11:59pm, 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 Apr 10th, 2007, 8:09am, 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.
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Material evaluation question
« Reply #5 on: Apr 10th, 2007, 11:50am » |
Quote Modify
|
You're right. My upper bound doesn't take into account symmetrical positions. I've been having trouble lately thinking before I post. Sorry.
|
| « Last Edit: Apr 10th, 2007, 11:55am by The_Jeh » |
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Material evaluation question
« Reply #6 on: Apr 10th, 2007, 2:14pm » |
Quote Modify
|
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, 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.
|
|
IP Logged |
|
|
|
woh
Forum Guru
Arimaa player #2128
Gender:
Posts: 254
|
|
Re: Material evaluation question
« Reply #7 on: Apr 10th, 2007, 3:43pm » |
Quote Modify
|
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.
|
| « Last Edit: Apr 10th, 2007, 3:44pm by woh » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Material evaluation question
« Reply #8 on: Apr 10th, 2007, 4:05pm » |
Quote Modify
|
The starting position is 112228-112228.
111128-110028
110228-110028
011228-011028
I think these are also all equivalent.
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Material evaluation question
« Reply #9 on: Apr 10th, 2007, 8:06pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
woh
Forum Guru
Arimaa player #2128
Gender:
Posts: 254
|
|
Re: Material evaluation question
« Reply #10 on: Apr 10th, 2007, 8:35pm » |
Quote Modify
|
on Apr 10th, 2007, 4:05pm, 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 Apr 10th, 2007, 8:06pm, 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.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Material evaluation question
« Reply #11 on: Apr 10th, 2007, 9:47pm » |
Quote Modify
|
on Apr 10th, 2007, 11:21am, 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.
|
|
IP Logged |
|
|
|
NIC1138
Forum Guru
Arimaa player #65536
Gender:
Posts: 149
|
|
Re: Material evaluation question
« Reply #12 on: Apr 10th, 2007, 10:01pm » |
Quote Modify
|
on Apr 10th, 2007, 8:35pm, 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!... 
|
|
IP Logged |
|
|
|
woh
Forum Guru
Arimaa player #2128
Gender:
Posts: 254
|
|
Re: Material evaluation question
« Reply #13 on: Apr 10th, 2007, 10:05pm » |
Quote Modify
|
on Apr 10th, 2007, 8:06pm, 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)
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Material evaluation question
« Reply #14 on: Apr 10th, 2007, 11:04pm » |
Quote Modify
|
on Apr 10th, 2007, 8:35pm, 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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print