Author |
Topic: Position Metric (Read 4727 times) |
|
The_Jeh
Forum Guru
Arimaa player #634
Gender: 
Posts: 460
|
 |
Position Metric
« on: Mar 5th, 2011, 12:40am » |
 Quote  Modify
|
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.
|
| « Last Edit: Mar 5th, 2011, 12:55am by The_Jeh » |
 IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #1 on: Mar 5th, 2011, 5:49am » |
Quote Modify
|
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?
|
| « Last Edit: Mar 5th, 2011, 5:52am by chessandgo » |
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Position Metric
« Reply #2 on: Mar 5th, 2011, 8:01am » |
Quote Modify
|
on Mar 5th, 2011, 5:49am, 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.
|
| « Last Edit: Mar 5th, 2011, 8:02am by The_Jeh » |
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #3 on: Mar 5th, 2011, 9:02am » |
Quote Modify
|
on Mar 5th, 2011, 8:01am, The_Jeh wrote:
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 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.
|
| « Last Edit: Mar 5th, 2011, 12:35pm by chessandgo » |
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Position Metric
« Reply #4 on: Mar 5th, 2011, 10:26am » |
Quote Modify
|
on Mar 5th, 2011, 9:02am, 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.
|
| « Last Edit: Mar 5th, 2011, 10:35am by The_Jeh » |
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #5 on: Mar 5th, 2011, 12:36pm » |
Quote Modify
|
sorry, I meant if you're winnng. I hope it makes more sense now 
|
| « Last Edit: Mar 5th, 2011, 12:36pm by chessandgo » |
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #7 on: Mar 7th, 2011, 4:38am » |
Quote Modify
|
I got a "Sorry, we are unable to retrieve the document for viewing or you don't have permission to view the document."
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #9 on: Mar 7th, 2011, 11:59am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Position Metric
« Reply #10 on: Mar 7th, 2011, 1:15pm » |
Quote Modify
|
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.
|
| « Last Edit: Mar 7th, 2011, 1:16pm by The_Jeh » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Position Metric
« Reply #11 on: Mar 7th, 2011, 1:59pm » |
Quote Modify
|
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. 
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?
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Position Metric
« Reply #12 on: Mar 7th, 2011, 2:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Position Metric
« Reply #13 on: Mar 7th, 2011, 2:35pm » |
Quote Modify
|
on Mar 7th, 2011, 1:59pm, 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.
|
| « Last Edit: Mar 7th, 2011, 2:38pm by The_Jeh » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Position Metric
« Reply #14 on: Mar 7th, 2011, 4:44pm » |
Quote Modify
|
on Mar 7th, 2011, 2:35pm, 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. |
|
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.)
Quote:| 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.
|
| « Last Edit: Mar 7th, 2011, 4:58pm by Fritzlein » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print