Author |
Topic: Position Metric (Read 4725 times) |
|
The_Jeh
Forum Guru
Arimaa player #634
Gender: 
Posts: 460
|
 |
Re: Position Metric
« Reply #15 on: Mar 7th, 2011, 5:16pm » |
 Quote  Modify
|
on Mar 7th, 2011, 4:44pm, 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.
|
| « Last Edit: Mar 7th, 2011, 5:23pm by The_Jeh » |
 IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Position Metric
« Reply #16 on: Mar 7th, 2011, 5:48pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Position Metric
« Reply #17 on: Mar 7th, 2011, 6:06pm » |
Quote Modify
|
on Mar 7th, 2011, 5:48pm, 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. 
|
| « Last Edit: Mar 7th, 2011, 6:09pm by Fritzlein » |
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #18 on: Mar 8th, 2011, 3:15am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Position Metric
« Reply #19 on: Mar 8th, 2011, 9:37am » |
Quote Modify
|
on Mar 8th, 2011, 3:15am, chessandgo wrote: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. |
|
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.
|
| « Last Edit: Mar 8th, 2011, 9:40am by The_Jeh » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Position Metric
« Reply #20 on: Mar 8th, 2011, 9:52am » |
Quote Modify
|
on Mar 8th, 2011, 3:15am, 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!
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #21 on: Mar 8th, 2011, 10:32am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #22 on: Mar 8th, 2011, 10:35am » |
Quote Modify
|
on Mar 8th, 2011, 9:37am, 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.
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Position Metric.
« Reply #23 on: Mar 10th, 2011, 10:42pm » |
Quote Modify
|
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;
}
|
| « Last Edit: Mar 10th, 2011, 10:56pm by BlackKnight » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Position Metric
« Reply #24 on: Apr 1st, 2011, 4:21pm » |
Quote Modify
|
on Mar 5th, 2011, 12:40am, 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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print