Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Position Metric
        
(Message started by: The_Jeh on Mar 5^th, 2011, 12:40am)

Title: Position Metric
Post by The_Jeh on Mar 5^th, 2011, 12:40am

I had this (probably unoriginal) idea the other day. Let's say that we have a metric d on the space of all Arimaa positions X, where d is a measure of the dissimilarity between two positions. Let p be the current game position that a bot is considering. Let R be the set of all positions that the bot can reach by moving. Let B be the set of all positions in a database (where positions are considered distinct if they occur in different games or on different moves in the same game). Then a bot can choose a move via the following method:

1. Let m = min{d(p,b) | b is in B}
2. Let S = {s in B | d(p,s)=m}
3. Let s be a position in S where the rating of the player to move is largest.
4. Let t be the position moved to from s (in the game in which s occurs).
5. Let n = min{d(r,t) | r is in R}
6. Choose a position from the set {r in R | d(r,t) = n}, and make the move that reaches that position.

The grand question is how to define d. Symmetric positions should be considered equal.

Almost certainly, this method would produce a lousy bot, simply because positions are extremely sensitive to what may appear to be subtle differences. However, I wonder if creating such a metric could be useful in some subordinate way. Perhaps it could help with pruning?

I also wonder whether such a metric could give serious help to a bot's strategic play. When a bot is choosing among tactically reasonable moves, if it chooses to move to a position that is as close as possible to one that already exists in a top player database, even if the two positions are fairly dissimilar, choosing this closest one may result in a better strategic placement of pieces.

The general idea is of the bot learning as a child learns from its parent - by imitation, but not exact replication.

Title: Re: Position Metric
Post by chessandgo on Mar 5^th, 2011, 5:49am

I have the feeling that S is going to be a singleton almost always, no matter how (practically) large the database is (as soon as the measure is sufficiently discriminating to be of use).

Also, if I understand correctly, the move finally chosen is not necessarily related to the move it's trying to mimic, but just to the position after the move. So if the closest position in the database comes from a game where the friendly player is losing (because of a piece hanging or hostaged) then it's likely that the move selected will actually give up that piece hostage or hang that piece in order to make the position more similar?

So maybe you would choose only among games where the friendly players wins in the end, or something like that?

Title: Re: Position Metric
Post by The_Jeh on Mar 5^th, 2011, 8:01am

on 03/05/11 at 05:49:37, chessandgo wrote:

Also, if I understand correctly, the move finally chosen is not necessarily related to the move it's trying to mimic, but just to the position after the move. So if the closest position in the database comes from a game where the friendly player is losing (because of a piece hanging or hostaged) then it's likely that the move selected will actually give up that piece hostage or hang that piece in order to make the position more similar?

So maybe you would choose only among games where the friendly players wins in the end, or something like that?

The bot finds the position s in the database that is closest to the current board position p. It then looks at the move made from s in the database and the position t in the database reached by this move. Then it chooses the move that takes the current board position p closest to t. It would be a problem if the move made from s were a blunder, so maybe you're right that the database would need to be limited to friendly player wins. On the other hand, you'd be cutting out a lot of data. Among strong players, the player who eventually loses can be expected to make decent moves most of the time.

But like I said, I have more faith in the metric as a portion of a bot's evaluation rather than the whole thing, though in that case I expect it may slow the search down too much.

Title: Re: Position Metric
Post by chessandgo on Mar 5^th, 2011, 9:02am

on 03/05/11 at 08:01:28, The_Jeh wrote:

But the move you eventually select is not a move close to the database move, it's a move making the position closer to the database position. So if you're (EDIT) WINNING and the database position is tied (which it should be most of the time in relevant games), you can expect to lose your advantage by making the position more similar.

Title: Re: Position Metric
Post by The_Jeh on Mar 5^th, 2011, 10:26am

on 03/05/11 at 09:02:48, chessandgo wrote:

But the move you eventually select is not a move close to the database move, it's a move making the position closer to the database position. So if you're losing and the database position is tied (which it should be most of the time in relevant games), you can expect to lose your advantage by making the position more similar.

What do you mean? If I'm losing, what advantage do I lose by making the position more even? But if I'm losing, I would expect the closest database position to be losing, too. That does not mean the the database move is bad, and hence the resultant database position t should be not much worse than s. So a bot should not go wrong by bringing the position closer to t.

The problem I see is if the bot's current position is even, but the closest database position according to the metric is losing. Then bringing the position closer to t would be bad.

Maybe what you're hinting at, and what I now suspect, is that there is no need to find t. Just bring the position closer to one held by a human who won. No need to bother with what move the human made at all.

Title: Re: Position Metric
Post by chessandgo on Mar 5^th, 2011, 12:36pm

sorry, I meant if you're winnng. I hope it makes more sense now :)

Title: Re: Position Metric
Post by The_Jeh on Mar 6^th, 2011, 7:52pm

Here's an example of a possible metric on Arimaa positions:

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwaMXEarBaG9MDYwMTJiOTEtYjc5Ny00Nzk4LWFhMGUtNTgwMTAwYzZjOTY0&hl=en

(I haven't formally proven that it's a metric.)

Title: Re: Position Metric
Post by chessandgo on Mar 7^th, 2011, 4:38am

I got a "Sorry, we are unable to retrieve the document for viewing or you don't have permission to view the document."

Title: Re: Position Metric
Post by The_Jeh on Mar 7^th, 2011, 10:49am

Sorry, here is the correct link: https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwaMXEarBaG9ZTkxYzlhYTktOTA5NC00MWM2LTk2NDQtNzBlNmM0NDEwMGRl&hl=en&authkey=CJOSheED

Title: Re: Position Metric
Post by chessandgo on Mar 7^th, 2011, 11:59am

Ok. If the "presence" was more distinct (with a base coefficient of 2^rank instead of just rank for example, or maybe something yet bigger actually) I'd agree it's probably a metric. As it stands I'm kind of worried that you might "emulate" the presence of a strong piece with several smaller pieces (well, emulating just one doesn't seem to work, but maybe emulating several strong pieces with even more numerous small pieces).

Title: Re: Position Metric
Post by The_Jeh on Mar 7^th, 2011, 1:15pm

I do understand what you are saying. The reason I left it as just the rank was so that the difference between a camel and an elephant would be the same as between a horse and a camel, or a dog and a horse, etc., since the relationship between these pieces and other pieces is sort of the same. I wonder if it is possible for distinct positions to have distance 0 under this system. My intuition says probably not, especially just among legal positions, but how to prove that, or if it were changed to 2^rank, I don't know off the top of my head.

Title: Re: Position Metric
Post by Fritzlein on Mar 7^th, 2011, 1:59pm

The difference between a rabbit and a non-rabbit seems pretty fundamental to me. I can imagine an AI advancing a cat to the seventh rank in order to be similar to a database game where a rabbit was advanced to the seventh rank. ;D

More precisely, suppose the closest match to {Ra3, Ed3, Ch3} found in the database was {Ca3, Ed3, Rh3}. The database move was Rh3->h7. Therefore (I believe) the move which minimizes the proposed distance between positions is Ch3->h7.

Have you hooked up the metric calculator with a move generator so that you can find the move which minimizes distance as required?

Title: Re: Position Metric
Post by chessandgo on Mar 7^th, 2011, 2:24pm

Well, if you make it big enough so that the biggest piece has a presence (on its square) which offsets the sum of all possible presences of all smaller pieces together, then obviously two positions would need to have the strongest piece(s) on the same square(s), and so on recursively. So maybe you'd need a cat to have a presence of like 8 times more than a rabbit, dog at least 8*rabbit + 2*cat etc, to have a simple proof.

Title: Re: Position Metric
Post by The_Jeh on Mar 7^th, 2011, 2:35pm

on 03/07/11 at 13:59:00, Fritzlein wrote:

More precisely, suppose the closest match to {Ra3, Ed3, Ch3} found in the database was {Ca3, Ed3, Rh3}. The database move was Rh3->h7. Therefore (I believe) the move which minimizes the proposed distance between positions is Ch3->h7.

Have you hooked up the metric calculator with a move generator so that you can find the move which minimizes distance as required?

Assuming the silver pieces are equally placed:

d({Ra3, Ed3, Ch7},{Ca3, Ed3, Rh7})=9.87
d({Ra7, Ed3, Ch3},{Ca3, Ed3, Rh7})=12.77

So, you're right about the cat move being considered closer than the rabbit move. However,

d({Ra6, Ee3, Ch3},{Ca3, Ed3, Rh7})=3.21

This metric is much more sensitive to the relative position of the elephant (treated as a dog), which could be a problem. In general, it is more concerned with the exact position of heavier pieces. Had the position of the cat and rabbit been of equal importance to the position of the elephant, the move Ra3->a7 might have been chosen due to symmetry. This is just a first attempt, anyway - an example, if you will.

I have not hooked it up to a move generator. I can only calculate for different positions.

Title: Re: Position Metric
Post by Fritzlein on Mar 7^th, 2011, 4:44pm

on 03/07/11 at 14:35:18, The_Jeh wrote:

Had the position of the cat and rabbit been of equal importance to the position of the elephant, the move Ra3->a7 might have been chosen due to symmetry.

This is just a first attempt, anyway - an example, if you will.

Understood. I hope my comment was the type of feedback you were hoping to get by posting both a general project and a specific metric. If you were hoping for a different sort of discussion, I apologize, and will accept guidance on how to respond in the future.

Title: Re: Position Metric
Post by The_Jeh on Mar 7^th, 2011, 5:16pm

on 03/07/11 at 16:44:17, Fritzlein wrote:

But if the opposing pieces are not symmetrically arranged, that would nix making a "symmetrical move" anyway, wouldn't it? For example, add {ec4, rd4} to the above position. Then even weighting the elephants less prevents Gold from moving on the wing where Silver has pieces instead of on the wing where Silver doesn't have pieces. Or does the metric allow you to flip wings for one player and not the other? (Sorry; I didn't entirely parse the formula.)

Understood. I hope my comment was the type of feedback you were hoping to get by posting both a general project and a specific metric. If you were hoping for a different sort of discussion, I apologize, and will accept guidance on how to respond in the future.

No, you've got to flip both players or neither. If you flip just one player, you're examining a different position. So, you are right. Maybe chessandgo's suggestion would correct the problem, because then the difference between a rabbit and nothing is less than the difference between a cat and a rabbit, and so putting the cat there would take the position farther away. On the other hand, this tendency would carry over to the other pieces as well, which is not necessarily good. Maybe rabbit=1, cat=3, dog=4, horse=5, etc.? Or am I not thinking hard enough? A greater cat presence would increase differences here and lessen them there... Maybe the rabbits could be propagated separately as well, so the metric would be added in 4 parts.

And no, you didn't respond in an unwelcome way. This is something I'd like to develop. I only meant that I expected success to come from some new metric using a different idea, rather than by refining this crude one.

Title: Re: Position Metric
Post by The_Jeh on Mar 7^th, 2011, 5:48pm

Actually, the problem extends beyond rabbits. If you charge, it does make a difference whether you do so with an elephant or a camel, or a camel vs. horse. My original idea was that a position is defined entirely by the relationships between the pieces on the board. For example, draw an arrow from a friendly piece to all enemy pieces stronger, then all friendly pieces stronger, then even, then weaker, etc. But I was at a loss as to how to define distance between two arrow diagrams, so I went with this simpler idea.

If I had just wanted any old metric example, though, how about d(p,q) = 1 if p<>q. :) Not very useful in a bot.

Title: Re: Position Metric
Post by Fritzlein on Mar 7^th, 2011, 6:06pm

on 03/07/11 at 17:48:11, The_Jeh wrote:

If I had just wanted any old metric example, though, how about d(p,q) = 1 if p<>q. :) Not very useful in a bot.

At least in topology metrics are interesting for the small distances rather than the large ones. If there is any parallel, one should start creating small distances for small positional differences and work up from there. But I guess there will be a minimum positive distance, and thus no connected sets. :-/

Title: Re: Position Metric
Post by chessandgo on Mar 8^th, 2011, 3:15am

Ok, but even if you have a perfect metric, expressing exactly what we would intuitively call the "distance" between two positions, I still don't see why my earlier comment is not a problem.

The bot is way ahead, the closest position in the database is tied, and the algorithms selects a move which makes the position closer to the target position (after the move), thus probably weakening the advantage. For example, if the bot is up a cat and the closest database position is the same without the cat, the bot will likely sacrifice his cat.

Title: Re: Position Metric
Post by The_Jeh on Mar 8^th, 2011, 9:37am

on 03/08/11 at 03:15:01, chessandgo wrote:

I guess you are right in a sense. If the "perfect" metric were to match a position only to one of a similar evaluation, then it would be an evaluation, not a metric. I admit wholeheartedly that the algorithm given would produce garbage. However, suppose that the bot evaluates a position in the usual way and produces a set of candidate moves, all within a certain evaluation of each other. If the bot selects the move from these pre-screened choices that the metric says is closest to a database position, isn't that move more likely to bring the position closer to that of a human strategically than the other moves? In other words, the intent of the metric is to offer the bot a new sort of strategic evaluation.

Title: Re: Position Metric
Post by Fritzlein on Mar 8^th, 2011, 9:52am

on 03/08/11 at 03:15:01, chessandgo wrote:

The bot is way ahead, the closest position in the database is tied, and the algorithms selects a move which makes the position closer to the target position (after the move), thus probably weakening the advantage. For example, if the bot is up a cat and the closest database position is the same without the cat, the bot will likely sacrifice his cat.

Heh, yes, or say the position is {Ca3, Ed3, Rh4}, where R->h8 wins, but the closest position in the database is {Ca3, Ed3, Rh2}, where R->h6 was played, so by imitation we play R->h6, making the positions identical!

Title: Re: Position Metric
Post by chessandgo on Mar 8^th, 2011, 10:32am

I dunno, I suppose I meant you might need to tweak a bit the approach. For instance you might define a metric on the set of moves just as you did for positions, and then select the closest database "starting" position, see what has been played, and select the legal move which is closest to the database move played.

Title: Re: Position Metric
Post by chessandgo on Mar 8^th, 2011, 10:35am

on 03/08/11 at 09:37:50, The_Jeh wrote:

I guess you are right in a sense. If the "perfect" metric were to match a position only to one of a similar evaluation, then it would be an evaluation, not a metric.

Well, actually maybe your metric could be partially derived from an eval function, putting much emphasis on the material count and the proximity of a rabbit to goal, etc, and then my objection wouldn't hold.

Title: Re: Position Metric.
Post by BlackKnight on Mar 10^th, 2011, 10:42pm

I wrote something related some time in 2007 if I recall correctly, but "Loc" would even sacrifice pieces to get closer to a position that was in the database.
I also submitted it for the WCC in 2008 with a huge database of landscapes. I'm not sure whether or not Loc2008CC still has access to this database.

I tried to calculate a landscape with hills and valleys to be able to compare two positions:

int* landscape(position *p) {
// transform the position into a "high-land"
int static highland[64];
int MAXDIST = 5;
for (int i=0; i<64; i++) {
// measure the distance to a different color:
u64 square= bit_on( i );
u64 cur = square;
int dist = 0;
for (dist=1; dist<MAXDIST; dist++) {
cur = cur | neighbors_of(cur );
if ((cur & p->bd[0][0]) && (cur & p->bd[1][0])) {
break;
}
}
u64 neighbors = neighbors_of(square );
// now calculate the weighted average:
double avg = 0;
for (int c=0; c<2; c++) {
for (int type=1; type<7; type++) {
if (square & p->bd[c][type]) {
avg += (10 - dist) * landvalues[type-1]* 10* pow(-1, c);
}
avg += dist * landvalues[type-1]* 10* bit_count(neighbors
& p->bd[c][type]) * pow(-1, c);
}
}
double denominator = 10 - dist + 4 * dist;
if (square & (A_FILE | H_FILE))
denominator -= dist;
if (square & (RANK_1 | RANK_8 ))
denominator -= dist;
avg /= denominator;
highland[i] = (int) avg;
}
return highland;
}

int comppos(int target[64], int curpos[64], int lowerbound) {
int value = 0;
// compare the two positions:
for (int s=0; s<64; s++) {
value -= abs(target[s] - curpos[s]);
if (value < lowerbound) {
return -INF;
}
}
return value;
}

Title: Re: Position Metric
Post by omar on Apr 1^st, 2011, 4:21pm

on 03/05/11 at 00:40:44, The_Jeh wrote:

The grand question is how to define d. Symmetric positions should be considered equal.

How about using a classification approach similar to what David Wu has done with bot_sharp. Given a position, identify a vast number of features in the position and use these features to define the similarities between positions.
It would certainly not be sensitive to symmetry.