Author |
Topic: Naive goal-seeking strategy (Read 2124 times) |
|
leo
Forum Guru
Gender: 
Posts: 278
|
 |
Naive goal-seeking strategy
« on: Apr 21st, 2006, 12:42pm » |
 Quote  Modify
|
Hello botmakers,
I've been two long years away from game AI and I'm curious about the possible changes in perspective Arimaa might have thrusted you into.
Back then I was considering starting with the naive beginner approach of seeking simple goals, that is for instance:
Instead of scanning the pieces and their moves and evaluate what comes out, start with something like that: Where are the traps? Are there opponent pieces nearby? How may I push or drag them into the trap?
This approach would be refined and complexified to handle conflicting priorities and board-wide strategy, but always avoiding doing mechanical scan - at the risk of missing a genial stroke but preventing the pruning clippers from getting red hot.
|
|
 IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Naive goal-seeking strategy
« Reply #1 on: Apr 22nd, 2006, 7:19pm » |
Quote Modify
|
I'm browsing my old notes and code, and here are some thoughts for those interested:
As I understand it the human mind spends more time imagining the application of known good actions than pruning off a host of bad ones.
New kinds of move are tested only once in a while, and their evaluation will depend on the actual consequences of them. This is long term abstract pruning, as opposed to immediate real-time pruning.
Experience stores a lot of visual configurations that are immediately recognized, for instance how the pieces are disposed around a trap square, or an open channel for a rabbit to advance through.
The visual patterns are mostly orientation-independent, so the alarm bell quickly rings when a dangerous disposition in spotted around a trap; or the attack bell when there's a possibility of trapping down an opponent piece.
Densely populated zones of the board require special attention, as they are likely to generate blockades and tricky attacks and stealthy rabbit jumps.
Mutual protection and split attacks have a flip side of getting each part involved in a counter split attack that highly increases the complexity of the analysis. Don't make forking and covering a long-term plan, re-evaluate them at each turn. Bonus if a piece can be substituted on the fly if necessary. But don't complexify the analysis too much scanning a zillion cases of perturbation.
The notes were for a plan and goal based AI that stores a "mind state" across moves.
|
| « Last Edit: Apr 23rd, 2006, 9:07pm by leo » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Naive goal-seeking strategy
« Reply #2 on: Apr 22nd, 2006, 10:06pm » |
Quote Modify
|
Thanks for sharing your observations. I'll have to reflect on them, but it looks like there are a few gems there.
|
|
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Naive goal-seeking strategy
« Reply #3 on: Apr 23rd, 2006, 9:04pm » |
Quote Modify
|
I've taken up coding and am aiming at the kind of AI that is used in "realistic" strategy games (as opposed to abstract boardgames), where the army units and managers only have a few microseconds per second to think. Here are some directions I've begun to code:
Each piece is assigned by the general manager one or several missions of the kind:
-Advance in general direction D.
-Protect piece P.
-Block piece P from advancing in direction D.
-Put away or trap piece P.
-Clear the way for piece P in direction D.
Each mission is tagged with a priority value.
Opponent pieces too are tagged with missions, but ones that are supposed by the general manager about what the opponent is trying to achieve.
Each piece is capable of a limited perception (4 steps away, or 4 cells in manhattan distance, may be changed in the future) and communication with the other pieces the same color. They maintain an internal state of distress, aggressivity, and can perceive the state and missions of the nearby pieces (of either color).
On local decision taking, a piece may decide to go help a piece in danger balancing it with its already assigned missions. Unresolvable conflicts of priority ring a bell to the general game manager that employs different techniques (still unclear) to take a final decision on goal and mission changes for each piece.
Step and move selection are the last operation performed, but each branch of the limited tree is checked against an evaluation of the resulting situation. This evaluation is of the same type as the one performed to assign the missions at the beginning.
The code is still a mess but I thought I may say a few things about it in case it rings a bell for some botmakers and we may come up with interesting things.
One important point: I'm not trying at this stage to create a strong AI opponent, only an opponent that looks more human than the current bots.
|
| « Last Edit: Apr 23rd, 2006, 9:09pm by leo » |
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Naive goal-seeking strategy
« Reply #4 on: Apr 23rd, 2006, 10:42pm » |
Quote Modify
|
on Apr 23rd, 2006, 9:04pm, leo wrote:| One important point: I'm not trying at this stage to create a strong AI opponent, only an opponent that looks more human than the current bots. |
|
I don't think that having each piece "decide" what to do will result in a more human bot. I agree that it will make for a very different bot.
|
|
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Naive goal-seeking strategy
« Reply #5 on: Apr 24th, 2006, 9:08am » |
Quote Modify
|
on Apr 23rd, 2006, 10:42pm, nbarriga wrote:
I don't think that having each piece "decide" what to do will result in a more human bot. I agree that it will make for a very different bot.
|
|
I see what you mean. We humans keep an eye on everything on the board, and don't move a piece without considering all the consequences. But before that there is a moment when we do local scan and plans of a simple sort, such as "threatened rabbit here! horse nearby! come help!". An advanced player may be mostly unconscious of the first stages of his reflection and be only aware of the elaborate solutions he might respond with. But I remember my state of mind when I was a total beginner in Arimaa: It was as if I had a part of my mind for each piece, selfishly trying to draw the attention for help or attack, and my perception of the global strategy was rather primitive. The ability to put together the needs of each piece or local group of pieces in order to produce a sensible move came very progressively. It is this kind of thinking that I'm trying to reproduce.
My post misleadingly let think I wanted to make the pieces autonomous agents, but the autonomous agents are actually the cognitive modules, and the higher reflection is produced by other cognitive modules that work globally, but are still rather dumb individually. I base this bot on the -maybe false- theory of the mind that intelligence is the well-tuned collaboration of specialized little units that are good at one thing but generally idiot.
I really want to make the bot look like a human beginner. It will make the typical errors a human makes, such as overlooking a threat and panic for a benign intimidation. But it won't make errors a human doesn't, such as merrily sacrificing pieces for no reason as some bots do. At least that's what I'm trying to do 
|
| « Last Edit: Apr 24th, 2006, 9:12am by leo » |
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Naive goal-seeking strategy
« Reply #6 on: Apr 24th, 2006, 11:19am » |
Quote Modify
|
Great ! I bet nobody never tried anything like this (at least conceptually) !!! 
Now it depends on how you concretely implement it, but if you do it without emphasing too much the agent part, you might get back to more usual stuff : each piece has sorts of weakness, activity, ... values with respect to the global position, some moves could improve some values, and then you want to make a soup with all this and decide which combination is worth more ...
But maybe your different point of view will lead to something really different ... 
With a different aim, I seems to me that the only way to get a bot play really well is through deep calculation ... considering only avery tiny part of the possible moves at each node ... I don't see how bots could compete with humans in the future otherwise. (but this has nothing to do with what you're doing)
Have fun and good luck with your programming !
Jean
|
|
IP Logged |
|
|
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender:
Posts: 882
|
|
Re: Naive goal-seeking strategy
« Reply #7 on: Apr 24th, 2006, 12:13pm » |
Quote Modify
|
leo's bot will be very interesting to watch play and develop. One aspect of the piece-oriented approach that may be a problem is that the pieces can't all move simultaneously. Distributed C2 works if the nodes can function with some independence. Movement in arimaa is constrained with the effect that good moves for individual pieces must be prioritized and selectively applied. The result is that the "general game manager" does all the real work.
I would expect the individual piece processes effectively contribute to the evaluation function and the general game manager interprets the components. The approach may shed some light on our understanding of evaluation functions.
The part of loe's approach I like the best is the goal-oriented selection of candidate moves. This is similar to what I wanted to try in a bot (aardvark) "when I get some time." I was thinking about defining threat and opportunity objects, generating moves that address/further them, and evaluating candidates according to the relative priority of the opportunity objects. The hard part would be to recognize new opportunities, correctly ranking them, and determining to what degree each piece participates. This was how I wanted to address the strategy problem. It seems like leo has a similar approach.
I'm hoping for some cool behavior. Good luck!
|
|
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Naive goal-seeking strategy
« Reply #8 on: Apr 24th, 2006, 4:47pm » |
Quote Modify
|
on Apr 24th, 2006, 11:19am, chessandgo wrote:| Now it depends on how you concretely implement it, but if you do it without emphasing too much the agent part, you might get back to more usual stuff (...) |
|
Too right... I just had a look at Haizhi Zhong's thesis and I realize his bot is full of specialized parts that ressemble agents or groups of agents. And I suspect other bots use similar techniques.
So the only originality of my approach would be that there is no systematic branch exploration, but instead local goal driven explorations at particular spots of the board.
Quote:| With a different aim, I seems to me that the only way to get a bot play really well is through deep calculation ... considering only avery tiny part of the possible moves at each node ... I don't see how bots could compete with humans in the future otherwise. (but this has nothing to do with what you're doing) |
|
This is the point where my project started. I believe that we humans haven't assimilated the whole space of possibilities of the game, and never will. Some mental predispositions and the force of habits tend to create for each game a particular style, a sub-game, that is typically human. Look for instance at how one player with a new idea changed the style of playing of the whole Havannah community: http://www.mindsports.net/Arena/Havannah/TwilightZone.html
I imagine that after this revolution the playing style stabilized again.
Brute-force bots can and will make us discover new styles, because they act as the obsessive genius that goes where nobody has gone before, but I think that most humans will always privilege their own way of playing. A human-like AI will be less likely to produce surprise, but its eventual victory will feel less controversial. This is just a theory of mine, of course...
|
|
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Naive goal-seeking strategy
« Reply #9 on: Apr 24th, 2006, 5:21pm » |
Quote Modify
|
on Apr 24th, 2006, 12:13pm, RonWeasley wrote:| (...) Distributed C2 works if the nodes can function with some independence. Movement in arimaa is constrained with the effect that good moves for individual pieces must be prioritized and selectively applied. The result is that the "general game manager" does all the real work. |
|
Yes... The turn-based situation requires much tweaking to the RTS habits. But I want to avoid the need for a "general commander" with his maps and twenty-line radio. There must be a way to confront the levels of priority of each task and emergency without spending expensive seconds of board-wide analysis and projection. Competition for the steps inside one move might be similar to the competition for draining limited resources on the RTS field. This means that the local agents should have a sense of the importance of their actions and are not as dumb as ant-agents.
Quote:| I would expect the individual piece processes effectively contribute to the evaluation function and the general game manager interprets the components. The approach may shed some light on our understanding of evaluation functions. |
|
I hope so...
Quote:| The part of loe's approach I like the best is the goal-oriented selection of candidate moves. This is similar to what I wanted to try in a bot (aardvark) "when I get some time." I was thinking about defining threat and opportunity objects, generating moves that address/further them, and evaluating candidates according to the relative priority of the opportunity objects. The hard part would be to recognize new opportunities, correctly ranking them, and determining to what degree each piece participates. This was how I wanted to address the strategy problem. It seems like leo has a similar approach. |
|
It does look similar. Since the agents are a bit more sophisticated than ant-agents and can explore local alternatives to fulfil their missions (but always with the final check of the evaluation), and can dialog with nearby agents to cooperate (for instance not to be three to rush for attack when a single piece is enough), they are likely to do good part of the job of prioritizing.
I imagine there will be intensive talk with the manager though, at the time of evaluating the result of the actions, because the evaluation will often say that it's a bad solution, and the agents will have to reconsider their alternatives. Duh, that's still more coding...
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Naive goal-seeking strategy
« Reply #10 on: Jun 17th, 2006, 1:15am » |
Quote Modify
|
the more I think about what Leo said, the more I like it I'm trying to do somehting along these lines ... a problem is to makes the controller understand that several subgoals are in fact the same.
For instance one friendly piece is sharing trap control, it shouts : hey guys, come help me ! an enemy piece also controlling this trap will say : "please, push me away, I occupy a good position here controlling this trap !" and the friendly phant being within reach of this trap will say "please, let me go there to try to control it". Now how to make the controller understand that these 3 subgoals are the same ? as i'm currently doing here he will generate several request to all friendly pieces to try to fullfill each separately ... and maybe will select another better valued move while a phant move would have fullfiled 3 goals at the same time ?
Ok, these are just random thoughts, but hopefully someone will see a way to deal with this kind of approach
|
|
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Naive goal-seeking strategy
« Reply #11 on: Jun 29th, 2006, 3:41am » |
Quote Modify
|
Interesting. I'm not so advanced in the development (well, hm, I'm even in a pause), but I guess the evaluation of the different states after simulated actions should take care of 'realizing' that kind of things.
As the bot aquires more experience (crystalized cause-and-effect memory) less simulation and evaluation should be needed (I'm talking here of the goal-and-memory bot I'm developing, not just the goal-bot).
I'll think about it more and post if I find out something worth of it. Thanks for sharing your thoughts, Chessandgo
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Naive goal-seeking strategy
« Reply #12 on: Jun 29th, 2006, 10:48am » |
Quote Modify
|
in fact the main problem seems to be that, to achieve a goal, not only a simple action like pushing a piece or advancing a piece is need ; but rather a logical combination of many "elementary actions" : like push this piece and push no other enemy piece nearby this trap or advance a stonger piece here or there and not move this one or ... and each piece trying to solve the goal might add other restrictions (like the presence of a piece to unfreeze it, no piece coming in the middle of it's way ...), so it will yield huge boolean formulas ... and this doesn't even take temporal phenomena (like a piece can pass, and then another can get on its path without problem but not the contrary ...) ...
|
|
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Naive goal-seeking strategy
« Reply #13 on: Jun 30th, 2006, 6:53am » |
Quote Modify
|
It is indeed a complex system in spite of the seemingly simple 'naive strategy'. What is naive in it is the approach, as opposed to elaborated alpha-beta and related sophisticated techniques.
A weak goal-bot might play at the level of a very young child, but a more evolved bot will host a population of little conflicting modules whose processing time might well soar far above the time of the traditional bots. Our brains work in parallel but in a way radically opposed to the current AI players.
What I wish to build is a system that can handle all the problems you mention without maintaining complicated tables of possibilities. The comparisons and simulations and conflict resolutions should be taken care by the 'natural', naive functioning of the system. The complexity should lie in the (ideally partly self-)organisation of the whole, not the detailed mechanisms of the parts.
I'm not claiming I have the solution -- otherwise the bot would be already up and kicking. I hope that experimenting with the simple version, which is incapable of complex moves, I'll get insights to go a bit further and so on...
I realize all I'm saying is awfully abstract and looks like a cloud masking my ignorance rather than a brilliant intuitive description 
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print