Author |
Topic: Evaluation beyond material (Read 1274 times) |
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
 |
Evaluation beyond material
« on: Jun 14th, 2008, 2:33pm » |
 Quote  Modify
|
Like most board games where it is applicable, the most dominant heuristic consideration in Arimaa is material, but what comes after that? By comparison, in chess apparently it's static piece location (as captured by piece-square tables).
So as a question to you bot owners, in what order would you place the heuristic considerations you've augmented the evaluation function of your bot with in terms of the additional playing strength they were responsible for? Or is the evaluation function too holistic for you to answer that in a satisfactory way?
|
|
 IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Evaluation beyond material
« Reply #1 on: Nov 25th, 2011, 7:11pm » |
Quote Modify
|
I'm also interested in this question. I guess that a lot of bot developers do what's easiest first rather than what's best? (or that's what I'd be tempted to do!)
I suppose there are a lot of candidates to be the next best priority after material eval. And this is aside from the search-related stuff like pruning and static goal recognition and qsearch right? Are we assuming that all of that is already been done?
edit: typos, and apologies for bringing up an old post.
|
| « Last Edit: Nov 25th, 2011, 7:43pm by Swynndla » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender: 
Posts: 605
|
|
Re: Evaluation beyond material
« Reply #2 on: Nov 26th, 2011, 5:30am » |
Quote Modify
|
Right now I think the best way to go about it is to see why your bot usually loses games with its current eval, and try to add evaluation terms to fix it (when playing against reasonably equal opponents of course, as playing much better opponents will likely not give you so much useful information).
YMMV, but if you start with a material-only evaluation, you'll probably find:
- that the bot moves its pieces randomly much of the time (so it's good to have something to encourage good development at least for the strongest pieces)
- that it lets the opponent harass its pieces too much, resulting in captures beyond the search horizon (and perhaps hostages and frames)
- that it doesn't care about medium/long-term goal attacks (as you know from our conversations in the chat my bot is at this stage)
It would be interesting to know if other bot developers use this philosophy or if they have another approach to figuring out what evaluation they need to add. If others do use this philosophy, did you have different observations as to what was causing your bot to lose games?
|
| « Last Edit: Nov 26th, 2011, 5:31am by rbarreira » |
IP Logged |
|
|
|
ingwa
Forum Full Member
Arimaa player #573
Gender:
Posts: 13
|
|
Re: Evaluation beyond material
« Reply #3 on: Nov 27th, 2011, 5:31am » |
Quote Modify
|
Here is a small note I wrote to myself before I started the work to improve badger earlier this fall. It was written while I was still thinking of this in pretty abstract terms and wasn't up to my neck in conflicting parameter values and battering complex details of implementation. Take it for what it's worth, and I'd be very interested in comments.
----------------------------------------------------
Hierarchy of Goals
------------------
The primary goal of the game is to win by advancing a rabbit to the end row. This must be the primary objective of all evaluation functions; if it is not, the evaluation function will not lead the search to final victory.
It is true that there are other ways to win, e.g. through immobilisation of the opponent. However, that goal is much more difficult to reach. We will therefore disregard those winning ways and concentrate on the rabbit goal runs.
Unfortunately for us, the initial setup provides a much too heavy force of resistance for our poor rabbits to be able to break through. So there must be secondary goals that we have to fulfill first, before trying to advance the rabbit toward the end row.
The most important secondary goal is to trap the opponent pieces. This is the easiest way to thin out the opponent force and thereby let our rabbits move past it. A more difficult way to create a path is to concentrate the opponent pieces to one side and let the rabbit through on the more thinly populated side. If we can combine both -- trap pieces to make them fewer, and then force them aside -- we have prepared the way well for our rabbits to reach the goal.
However, the opponent will not let us trap his pieces without putting up a fight. His normal pieces will not be easy to drag to our home traps and his rabbits will be protected behind them. Furthermore, he will try to do the same to our pieces, and we will have to defend them. So we will have to create a position where it is likely that we will be able to trap the opponent's pieces while it is unlikely that he will be able to trap our own.
To create such a position, we must weaken his defences. If we can create a stalemate on one side of the board and at the same time free up one of our strong pieces to dominate the rest of the board, we have a very favourable situation. Such a stalemate can be created by one of several different tactics: a hostage, a blockade of his elephant (difficult unless he makes a grave mistake) or by isolating one or more weaker pieces while at the same time blocking the traps from the opponents strong pieces.
It is also important to dominate as many traps as possible to make it likely that if we manage to isolate a piece as above, that we can lead it to a trap and finally capture it.
But how do we manage to set up a position like above? It is unlikely that the opponent will let us take over his home traps or isolate one of his pieces without a fight. What we must do is to recognize such strategic factors that are important in creating tactical situations like above. Such factors could be mobility, especially of the elephant and camel, centralization, domination of sectors of the board, etc. The opening theory is not mature here, so we may be able to find factors that are so far unnoticed by others.
So to summarize:
1. Primary goal: Force a rabbit through to the end row.
This can be done by using strong pieces as path breakers through
areas of enemy weak pieces or making the opponent force so thin
that the rabbit can go there on its own.
2. Secondary goal: Thin out the opponent force.
This is done by trapping the opponent pieces and possibly
concentrate them to one side. This will prepare the ground for the
rabbit to fulfill the primary goal.
3. Tertiary goal: Create a position that makes it likely that we will
be able to capture his pieces.
This is done by paralyzing his strong piece(s), e.g. through
tactical means like hostages, frames, blockades, etc in one side of
the board, and then dominate the rest of the board by our other
strong free pieces. It is therefore important that the tactical
situations above are created with as light pieces as possible (but
no lighter!) so that we can free as powerful pieces as possible for
the other parts of the board.
We must also create a combination of threats such that he cannot
defend against them all at the same time. The most powerful tool we
have here is ownership of the traps, especially if we manage to
dominate each trap just a little: the elephant against the camel,
the camel against the horses, etc. Over-domination of one trap or
other feature will lead to submission somewhere else.
There are also tactical tools here, like the fork.
4. Quarternary goal: Find strategic values that let us eventually
fulfill the tertiary goal.
This is a vague goal. Such values could be centralization of strong
pieces, mobility, patterns around traps, etc. This is an area
where creativity and fantasy will help us.
I also believe that it is important to recognize different types of
threats as early as possible. If we can create a combination of two
threats, e.g. a threat to create a fork and at the same time a
threat to a hostage, we may be able to actually fulfill one of the
threats. A good treatment of combinations of threats is likely a
way to very high playing strength.
Evaluation Function as a Guide for the Search
---------------------------------------------
The evaluation function must recognize all the factors and features above and reward them with a suitable score. It is important that once one subgoal of the position has been reached, that there is a smooth transition into the next level of goals.
An example of the contrary can be seen in the current evaluation function. It rewards freezing or taking hostage of enemy pieces, but doesn't make any further use of this by trying to drag it closer to a trap and dispose of it. What is missing is a term that makes the freeze more valuable nearer to a trap. Another such mistake is that it is just as happy to frame a horse with a camel as with another horse. So the tactical advantage of a frame (to almost trap a piece) is recognized, but not the strategic value (to tie down a strong opponent piece and let our own strong pieces roam the board). A third example is that it rewards rabbit advancement, but once a rabbit has a
forward position, it doesn't try to get stronger pieces nearby to help it make a goal.
So, each feature must be evaluated in a way that leads the search into naturally trying to move to the next level of goals. This means that the feature must have a gradual evaluation, making it higher valuated the closer it is to reaching the next goal. Some examples:
- Freezing a piece is better near a trap than far away from it. The
closer the better.
- A rabbit in a forward position is better if the opposition in front
of it is slim or if we have a strong piece nearby to help it. In
that case, the value of slim opposition must be higher than the
value of the strong piece. This will make the strong piece
naturally try to reduce the opposition by trapping it.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print