|
||||||
|
Title: Evaluation MindMap Post by 99of9 on Apr 6th, 2006, 12:43am 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? |
||||||
|
Title: Re: Evaluation MindMap Post by Fritzlein on Apr 6th, 2006, 7:43pm 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? |
||||||
|
Title: Re: Evaluation MindMap Post by 99of9 on Apr 6th, 2006, 9:39pm 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. |
||||||
|
Title: Re: Evaluation MindMap Post by jdb on Apr 6th, 2006, 11:08pm 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. |
||||||
|
Title: Re: Evaluation MindMap Post by 99of9 on Apr 7th, 2006, 12:16am on 04/06/06 at 23:08:47, jdb wrote:
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. |
||||||
|
Title: Re: Evaluation MindMap Post by BlackKnight on Apr 7th, 2006, 1:16am 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. |
||||||
|
Title: Re: Evaluation MindMap Post by 99of9 on Apr 7th, 2006, 3:18am I've got an inkling of what you mean, but can you explain in a bit more detail how that might work? |
||||||
|
Title: Re: Evaluation MindMap Post by BlackKnight on Apr 7th, 2006, 3:28pm botV mainly generates classes of moves:
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. |
||||||
|
Title: Re: Evaluation MindMap Post by omar on Apr 9th, 2006, 7:55am 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. |
||||||
|
Title: Re: Evaluation MindMap Post by Fritzlein on Apr 11th, 2006, 3:52pm on 04/07/06 at 15:28:19, BlackKnight wrote:
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:
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. |
||||||
|
Title: Re: Evaluation MindMap Post by 99of9 on Apr 11th, 2006, 9:19pm on 04/11/06 at 15:52:45, Fritzlein wrote:
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. |
||||||
|
Title: Re: Evaluation MindMap Post by BlackKnight on Apr 12th, 2006, 6:49pm on 04/11/06 at 15:52:45, Fritzlein wrote:
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 04/11/06 at 15:52:45, Fritzlein wrote:
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 04/11/06 at 15:52:45, Fritzlein wrote:
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. ...}...}...}...}. |
||||||
|
Title: Re: Evaluation MindMap Post by IdahoEv on Apr 12th, 2006, 7:44pm 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.) |
||||||
|
Title: Re: Evaluation MindMap Post by 99of9 on Apr 12th, 2006, 8:30pm 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. |
||||||
|
Title: Re: Evaluation MindMap Post by IdahoEv on Apr 12th, 2006, 9:01pm 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. |
||||||
|
Title: Re: Evaluation MindMap Post by ntroncos on Apr 13th, 2006, 10:44am Some of the aspect discussed in this thread could be achieved in a way by a double evaluation. First do a shallow search to look for the possible moves, then line them up in a priority cue. Then a second in more depth evaluation for the higher priority moves. |
||||||
|
Title: Re: Evaluation MindMap Post by 99of9 on Jul 20th, 2006, 10:13pm Just an update on Gnobot's evaluation overhaul: I've written about 15 functions out of about 50 that are now on my map. (*) means some subfunctions are missing, but the formula for combining the subfunctions is written. * game stage * board balance * key positions held * pieces organized * board structure* * DAPE - depreciated arimaa piece evaluator * DAPE derivatives * Path weights to centre * E access to centre * M_E separation * initiative* * general advance * long term win probability* * short term win probability* * overall evaluation* So far these fragments take 1100 lines of code, and I probably subconsciously chose the easiest ones first. Another problem is that as I think more, I add more components to my To Do list. So there's a long way to go. But at least I think I'm doing each component "properly", and I hope I can get the whole thing ready before this year's CC. The downside of focussing so much energy on Eval is that I'm unlikely to change the search routines at all - so Gnobby will be a 10 -11ply bot once again. |
||||||
|
Title: Re: Evaluation MindMap Post by Fritzlein on Jul 21st, 2006, 10:41am I'm thrilled to see Gnobot get an evaluation overhaul. It was already more strategically aware than the other bots, so this could potentially vault Gnobot into contention for the Computer Championship. My understanding is that for computer chess, most of the progress came by improving search rather than by improving eval, but I don't see why that would necessarily apply to Arimaa. My hunch is that bots can do much better with static eval than they do at present. |
||||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |