Author |
Topic: Evaluation MindMap (Read 3987 times) |
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender: 
Posts: 1413
|
 |
Evaluation MindMap
« on: Apr 6th, 2006, 12:43am » |
 Quote  Modify
|
This is my first attempt at mapping out my thoughts about Arimaa evaluation: http://members.westnet.com.au/doctorhudson/ArimaaEval.pdf
What do you think? Anything more you think should be included. Should it be organized differently?
|
| « Last Edit: Apr 6th, 2006, 12:43am by 99of9 » |
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Evaluation MindMap
« Reply #1 on: Apr 6th, 2006, 7:43pm » |
Quote Modify
|
I'm afraid I'm not familiar with the concept of a mind map. Would you care to explain, or is it one of those things where, if you have to explain, I'm not going to get it?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Evaluation MindMap
« Reply #2 on: Apr 6th, 2006, 9:39pm » |
Quote Modify
|
Wikipedia says it better than I could:
http://en.wikipedia.org/wiki/Mind_map
To use this type of graph for evaluation of a board position, I would need to eventually put formulas on every node. Leaf nodes should have very simple formulas that can be obtained directly from the board (e.g. "enemy density in the 8 squares around my most advanced rabbit"). All other nodes would combine the values of their successors with a formula that could be as simple as adding them up, but in most cases is likely to be a non-linear equation describing how the interacting components contribute to the overall feature.
The overall idea is to go beyond just adding up millions of different terms, and e.g. include the fact that it doesn't matter whether or not you kill a camel if your opponent is creating an amazing goal attack on the other side of the board.
(The numbers on some of the nodes just represent the priority I would put on some of those terms.)
I recommend a freeware program called Freemind which can produce this type of map. If people are interested in this, I can post the source file for this map, and we can try to improve it collaboratively. An accurate and complete map with formulas would help design a very powerful evaluation function.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Evaluation MindMap
« Reply #3 on: Apr 6th, 2006, 11:08pm » |
Quote Modify
|
Ok, I'll give a try at how I evaluate a position in arimaa.
Top priority is goal threats. What do I have and what does my opponent have?
Second priority is material balance. Are there some tactics happening? This includes piece capture, hostage taking and piece framing.
If there are no tactics or goal threats, then I look for rabbit pulling possibilities. Also how the pieces are distributed around the board. Are my home traps protected?
In the end, I think, most of arimaa strategy revolves around trap control. If you look at games in general, the player who controls the important traps is usually winning the game.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Evaluation MindMap
« Reply #4 on: Apr 7th, 2006, 12:16am » |
Quote Modify
|
on Apr 6th, 2006, 11:08pm, jdb wrote:| Top priority is goal threats. |
|
I'm hesitant to put them in totally separate strata like this. I would not be willing to give up a camel to get a 1%-probability-of-getting-through goal threat.
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Evaluation MindMap
« Reply #5 on: Apr 7th, 2006, 1:16am » |
Quote Modify
|
After playing around with botV last year, I was wondering whether imitating our thoughts could help to prune off more branches.
So a graph with the same set of nodes you suggest but with a different edge set might be useful for a very selective search.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Evaluation MindMap
« Reply #6 on: Apr 7th, 2006, 3:18am » |
Quote Modify
|
I've got an inkling of what you mean, but can you explain in a bit more detail how that might work?
|
| « Last Edit: Apr 7th, 2006, 3:19am by 99of9 » |
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Evaluation MindMap
« Reply #7 on: Apr 7th, 2006, 3:28pm » |
Quote Modify
|
botV mainly generates classes of moves:
- For example if an opponent's piece is close a trap that is at most "secured" by this piece itself, then botV checks all its stronger pieces to see whether they can attack this pieces and push/pull it into the trap.
- attacking moves: pieces are allowed to move next to a weaker piece of the opponent.
- If there is an own frozen piece, then it creates moves of pieces nearby that unfreeze this piece.
- ...
All those moves are generated as a sequence of up to four steps. So while Loc for example would consider Ea2s if this is possible, botV would never do this in a single step unless there is a piece of the opponent on b1 (or an own frozen piece, ...).
Still, there are many moves that are "unreasonable" (and on the other hand there are also classes of moves missing).
To get rid of those unreasonable moves I would like to draw a graph like yours and focus on important things in a certain position, very similar to what also Jeff said above.
If we see a rabbit close to goaling, then we focus first on moves in that area I suppose. It is not very interesting to generate an attacking move towards the trap diagonally accross the board.
If the opponent gets hold of my camel next to his own trap, then I guess I mainly check whether I can get something for this, or whether I can send two minor pieces at the same time to secure this trap temporarily (which might not be a good move) or whether my elephant needs to run.
I would like to exclude all other moves that (most probably) have no use because of the major threat, that the opponent is going to kill my camel in the next turn.
Maybe this is more like a structogram, but I didn't know about mind maps until you brought it to our attention. So I was wondering whether mind maps can also model this behavior rather than keeping on generating all moves and then evaluating so many positions. But I'm sure a mind map would significantly improve the evaluation function.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Evaluation MindMap
« Reply #8 on: Apr 9th, 2006, 7:55am » |
Quote Modify
|
Interesting map Toby.
I've always felt that humans use a top-down constructive approach to coming up with a move as opposed to a bottom-up selective approach used by computers. The evaluation suggested by your map seems to be going in this direction.
Lately I've started to think that a combination of an AI expert system (http://en.wikipedia.org/wiki/Expert_system) combined with a conventional shallow depth (maybe 2 ply) tree search might produce a strong program. The tree search helps to avoid blunders and tactics while the expert system focuses on longer term strategic goals.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Evaluation MindMap
« Reply #9 on: Apr 11th, 2006, 3:52pm » |
Quote Modify
|
on Apr 7th, 2006, 3:28pm, BlackKnight wrote:botV mainly generates classes of moves:
- For example if an opponent's piece is close a trap that is at most "secured" by this piece itself, then botV checks all its stronger pieces to see whether they can attack this pieces and push/pull it into the trap.
- attacking moves: pieces are allowed to move next to a weaker piece of the opponent.
- If there is an own frozen piece, then it creates moves of pieces nearby that unfreeze this piece.
- ...
|
|
This is extremely interesting. I'm thrilled someone is developing such a bot. But let me check that I understand what is going on.
You are drastically pruning the search tree by generating a list of "reaonsable" moves.
You are not saying anything about the evaluation function when you list the kinds of moves bot_V will consider.
Is this correct?
Quote:| I would like to exclude all other moves that (most probably) have no use because of the major threat, that the opponent is going to kill my camel in the next turn. |
|
OK, so this is a method to speed up (i.e. deepen) search? This is very intriguiging because it is more similar to what humans do than brute-force searching.
However, I think you would have difficulty forming a concrete hierarchy of priorities. Yes, goals are strictly more valuable than captures, but as 99of9 pointed out, how do you rate goal threats? If the opponent has a threat to kill your camel in four steps and a threat to make goal in six steps, do you strictly forbid your program from looking at moves to defend one in favor of moves that defend the other? I don't know how you can decide in advance which threat ranks higher.
In chat with JDB, I tried to develop some some notion of urgency as distinct from value. In the above example, the goal threat is more valuable than a camel capture, but it is less urgent becuase it is six steps away while the camel capture is four steps away. In the current postal tournament, I have also noticed this dynamic in the opening phase. One player will make a smaller, quicker threat, while the other players makes a larger, slower threat. It's often a difficult judgement for the player with the smaller threat to know whether it's quick enough to take, and then defend later, or whether the small threat has to be abandoned immediately to defend the large threat.
Also I think there has to be a way to incorporate that playing in a certain area can have a different value to the two players. Maybe I have a rabbit hostage, and if I can play there, I will capture the rabbit for a value of +1 to me, but if you can play there you will get a forced goal, for a value of infinity to you. What is the value of this rabbit?
The answer depends on the population of other threats that exist, on their urgency, and on their value. If this is the only hotspot on the board, then I will kill the rabbit right away, and the value of your goal threat turns out to be nothing. But if you are also threatening to take my camel, I still have to take your rabbit to prevent goal, in which case the goal threat wins you a camel for a rabbit.
So I guess what I am saying (if I am saying anything at all) is that my attempts to create hierarchy have been frustated by the value/urgency dichotomy. It seems any breakthrough in evaluation will have to distinguish the two.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Evaluation MindMap
« Reply #10 on: Apr 11th, 2006, 9:19pm » |
Quote Modify
|
on Apr 11th, 2006, 3:52pm, Fritzlein wrote:Also I think there has to be a way to incorporate that playing in a certain area can have a different value to the two players. Maybe I have a rabbit hostage, and if I can play there, I will capture the rabbit for a value of +1 to me, but if you can play there you will get a forced goal, for a value of infinity to you. What is the value of this rabbit?
The answer depends on the population of other threats that exist, on their urgency, and on their value. If this is the only hotspot on the board, then I will kill the rabbit right away, and the value of your goal threat turns out to be nothing. But if you are also threatening to take my camel, I still have to take your rabbit to prevent goal, in which case the goal threat wins you a camel for a rabbit. |
|
I suppose I view this one the other way around:
A camel threat is worth almost an entire camel when the defending elephant is "busy".
Maybe I should extend the concept of busy to include "busy for X steps" and "busy defending/attacking material value Y". Both would have different implications for how to play.
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Evaluation MindMap
« Reply #11 on: Apr 12th, 2006, 6:49pm » |
Quote Modify
|
on Apr 11th, 2006, 3:52pm, Fritzlein wrote:
You are drastically pruning the search tree by generating a list of "reaonsable" moves.
|
|
Yes, but there are still moves missing.
For example I did not implement goal attack nor goal defense. Goal attack seems relatively straight forward actually, but how about goal defense. How can I "explain" all those sidesteps and blockading and squeezing to botV. And if, will I really cover all possibilities? Maybe the brute force approach will still work better here. And I think humans also do a kind of brute force when they are trying to find out whether a rabbit can reach the goal.
on Apr 11th, 2006, 3:52pm, Fritzlein wrote:| You are not saying anything about the evaluation function when you list the kinds of moves bot_V will consider. |
|
Exactly. First I thought let's try a very simple one, only considering material advantage and some few other things. Like Jonathan proposed. But then the bot really needs to look ahead A LOT!
botV only reaches maybe 16 steps on average (without null moves, search extensions, ...).
So that's still only 4 ply, 2 moves for each player. That's by far not enough. So I used Loc's eval, with a few changes! 
on Apr 11th, 2006, 3:52pm, Fritzlein wrote:OK, so this is a method to speed up (i.e. deepen) search? This is very intriguiging because it is more similar to what humans do than brute-force searching.
|
|
Yes, compared to Loc it's much faster. botV often reaches 12 steps within 15sec.
I really would like to copy even more of the human way of thinking, but I need a way to further choose a subset of the moves I'm generating. This is why I thought Toby's mind map could not only be very useful for evaluation but also for move generation in the first place.
But as you said in your posting: it's VERY difficult to find the right balance between long/short term strong/weak threats. I don't even know how I decide in my own games, so how can I tell my bot how to think.
My main ideas was actually to draw a flow diagram:
Can I goal? {Y: {Do it.} N: {Can I capture a piece? Y: {Can the opponent goal after this move? ...}N: {Do I have the camel hostage? Y:{Attack with my camel. ...}...}...}...}.
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Evaluation MindMap
« Reply #12 on: Apr 12th, 2006, 7:44pm » |
Quote Modify
|
One of the approaches I am working on with my bot uses an ANN to produce a "saliency map" of the board.
One of the things that humans do best when analyzing anything from strategic games is use shallow processing to learn what to ignore. Entire sections of visual cortex are committed to building a queue of "interesting" locations in the visual sphere, based on movement, contrast, etc. Your eye saccades to these regions sequentially.
In a game like Chess or Arimaa, a human only considers ~2 moves per second. But the tree is trimmed drastically by only considering moves that are salient/interesting; if a region has no incoming threats, is well defended, and no reasonable chance of producing an outgoing threat, we don't waste much time considering moves from that location.
I am trying to reproduce that function via an ANN in my bot; hopefully to narrow down the branch factor by an order of magnitude or more.
A saliency map is nearly impossible in chess, but I think it's quite doable in Arimaa because of the basic differences in mechanics.
(I am also trying to train an ANN as a static evaluator, but I think this is much less likely to prove fruitful; it will be too slow on commodity hardware.)
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Evaluation MindMap
« Reply #13 on: Apr 12th, 2006, 8:30pm » |
Quote Modify
|
I think saliency maps deserve a thread of their own. (Omar if you happen to be reading this and have the time on your hands, could you split this thread?)
I agree this could be very significant to arimaa. I certainly think it is possible to identify the salient areas of the board.
My question is, exactly what do you do with them after that?
* If you totally ignore the "boring" areas, you will not make the small improvements to those areas that may later cause them to become great hotspots for you.
* I suppose the answer is to search them to a lower depth. In my experience it is hard to know how to compare one move searched to a lower depth to another searched deeper (for example if the low depth scored higher). But then I'm not really a programmer.
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Evaluation MindMap
« Reply #14 on: Apr 12th, 2006, 9:01pm » |
Quote Modify
|
Mentally, it seems what I do as a human player is search the salient areas of the board for an important move. If that move happens to consume only 2 or 3 steps, then I search the non-salient areas of the board for strategic adjustments that can be done in 1-2 steps, like reinforcing a trap or making it easier to rotate pieces later.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print