GNOME Bugzilla – Bug 419159
Improve gnibbles AI search algorithm
Last modified: 2008-06-16 19:41:10 UTC
The bug has been opened on https://launchpad.net/bugs/90907 "Binary package hint: gnome-games To really show the bug: Change nibbles to level 15. (Can the up/down arrows only go in twos?) Add the max number of AI players. watch the ai players die, games last around 2-3 seconds. ProblemType: Bug Architecture: i386 Date: Fri Mar 9 13:28:29 2007 DistroRelease: Ubuntu 7.04 ... It doesn't crash the game. It is a logic bug. The AI can't navigate through level 15. The purple worm (bottom of the screen), Gets spawned and 9/10 times runs directly into a wall. AI needs to be a bit smarter. Importance: Very very low."
Yes, this is a limitation of the current AI algorithm. It uses a "greedy" algorithm, which doesn't detect that it will die in the corners of level 15. This could be improved by: - implementing A* search of the AI worms. - making the worms move in a random direction when returning from the dead, which will prevent the worm from repeatedly dieing in level 15, because the worm will default to going downwards, and thus die every time quickly. - implement a special case check for the condition which occurs in level 15.
Created attachment 108364 [details] [review] AI with search algorithm - Working but not refined The attached patch file implements a search algorithm for the AI. (And uses it for half the AI worms for test purposes.) Note that it still isn't perfect and I'm not intending that this should be included as is. I'm more interested in hearing if the maintainers are interested in having more work done in this area. (I was having some fun doing it anyway)
Hello Simon, Excellent work on improving the nibbles AI, this would be a very good improvement to gnibbles. Once you are satisfied enough with the results, then I can help with adding your changes to gnome-games. Which search algorithm have you implemented? From looking at your patch, it seems that you are using some greedy algorithm. - Andreas
It's a greedy algorithm, but I'm afraid I don't know a name, it fills the entire search space with the distance from a bonus (and it's not very efficient at doing that either) and moves into the cell with the lowest score. Part of my hesitation is that it may be too hard for a human player to reach the bonuses, so playability could potentially suffer.
>Part of my hesitation is that it may be too hard for a human player to >reach the bonuses, so playability could potentially suffer. I agree that this greedy algorithm will make it quite difficult for human players to reach bonuses. How about using this search algorithm for having difficulty settings for the AI? Eg. redefine the speed preference in gnibbles to modify the game difficulty instead. For example: -Nibbles newbie" has the slowest movement speed, and old search algorithm. -Finger-twitching good has fastest movement speed, and new search algorithm.
Created attachment 111892 [details] [review] Alternative AI patch This patch is an alternative solution to the Level 15 problem. This patch doesn't improve the AI search algorithm for bonuses much (although it allows search for bonuses to wrap across the edges of the screen); instead, it makes the AI worms much better at surviving. (It could therefore be implemented additionally to the other patch given, to make the worms better at searching and at surviving.) With this patch, the AI worms turn away from dead ends and other similar traps, making them harder to kill, and will not die due to being stuck in a 45-degree corner. It also protects the AI worms from some of the most common techniques that humans use to kill them, and so improves the AI in that way as well. I'm not sure whether to submit this here or create a separate bug for it; let me know if I'm doing this wrong!
Now we have two competing patches... How can we compare the the AI approaches? Simon McNeilly, what do you think of the latest patch from ais523?
It sounds pretty good. This approach probably makes for a more playable game than my patch. I suspect that it could even make my previous patch (with is_move_safe) redundant. I agree that it could be done in conjunction with a search like mine and would add value to such a search because it would aid in avoiding traps by opponent worms.
> I agree that it could be done in conjunction with a search like mine and would > add value to such a search because it would aid in avoiding traps by opponent > worms. Perhaps we could get a patch with this combined solution, if this would be the best solution for players of gnibbles?
(In reply to comment #9) > > I agree that it could be done in conjunction with a search like mine and would > > add value to such a search because it would aid in avoiding traps by opponent > > worms. > > Perhaps we could get a patch with this combined solution, if this would be the > best solution for players of gnibbles? > I'd recommend only doing that if an AI-strength setting is added to the preferences, because it would make the computer worms very difficult to beat for non-experienced players. The greedy-algorithm search means that computers will alwasy get the boni unless they are created near a human; the survivability means that they won't go for a bonus if it leads the AI into a trap. However, the combined approach would lead to the computers 'swarming' towards the boni; a smart human player would aim in the opposite direction and likely get a bonus that way due to having a large head start under several circumstances. The AI could be made still stronger if worms only aimed for the boni if they were nearest; that would lead to the human getting about 1/6 of the boni with 6 worms, if they had average skill, and to the computers being very efficient at completing levels. As for what's best for players, I'm not entirely sure. Some players (from my very small sample) like playing for points, others like killing enemy worms. One potentially difficult solution would be to combine both patches in a user-configurable manner, and also add a third AI which makes the computers agressive towards other players (trying to kill each other and human players); there isn't code for this and it would take a while, but do people here think it would be worth me working on it? That would lead to a situation where there would be multiple AI personalities (greedy, agressive, defensive, standard, inept, etc.), so the user could choose what sort of opponents to play against, according to what sort of game they enjoyed. (Maybe even to change the personality per-worm.) This would be a reasonably major change, but if people think it's worth it I may have a go. Anyway, repeatedly suiciding on level 15 is a pretty clear logic bug that detracts from the product; I'd be in favour of increasing the severity to minor, because it's obvious that the AI is just being stupid, and also trivial to win on that level, without either patch applied. I can probably quite easily come up with an AI patch which avoids the level 15 suicide problem and the worm-getting-caught-in-a-spiral problem, without making the worms notably better in other regards; that would leave the game playing similarly to how it does now, with no obvious increase in the AI's strength, but without the obvious traces of AI stupidity.
Ok, I'll commit the AI from ais523@bham.ac.uk. This problem has been fixed in the development version. The fix will be available in the next major software release. Thank you for your bug report. http://svn.gnome.org/viewvc/gnome-games?view=revision&revision=7694