Other (abandonned) projects II

(first part here: http://roguesurvivor.blogspot.com/2010/06/other-abandonned-projects.html)
Warning : bunch of AI mumbo-jumbo ahead, you should know a bit about searching and planning. I'm too lazy right know to properly explain the algorithms and terms.

* BadBowl - an attempt at "serious" AI
For the life of me I can't get this thing running again, so no ingame screenshots, just code.
I like screens because they show I actually did work and its not vaporware :)

Idea : Solo Blood Bowl - Human vs AI.
Environement : Java, Eclipse.
Status : Abandonned.

Designing an AI for a BloodBowl clone sounded fun, so I did it. I developped the game engine and the AI at the same pace. For instance I did not implement passing yet but there was an AI you could play already against with moving, blocking, scoring, special abilities etc...
Actually there was THREE different AIs engine. 

1. SimpleAI
Engine: Selective tree search with static pruning.

Why "Simple"? Well doing a search engine with pruning sounded simple enough as I was sure I could do it since  I already did chess engines for instance. I knew it would be probably bad and slow, but at least I knew I could do it. Just curious about the results.

I knew the search space would be insanely large so I did pruning at each level of the tree. In other words selective search with static pruning. As usual with these kind of approach, the idea being that "good" moves should get more attention than "bad" moves. It sounds much less risky than in chess for instance, because you are searching only your own moves, not the opponent, so less tactical blunders caused by ignoring some move lines.

I don't remember the details (how did I handle turnovers in the search, risk taking with probabilities etc..).
Here's the actual main search method code in Eclipse, arranged into one messy large picture:

As you can see its just a standard search with hashing and prunning.
The resulting AI was mediocre at best and the AI thinking was way too slow.
As usual with tree searches, it was hard to determine what was the weak point causing bad choices : the evaluation function? the search/pruning?...
So I did number 2...

2. BeamAI
Engine : Beam search of plans.

Instead of searching a tree, this AI maintains a list of plans and try to improve them. I read about it in some AI papers, mostly about a Diplomacy AI engine by a French guy, and it sounded great.
In this context, a Plan is a list of successive AI moves. Improving a plan means adding a move that makes the terminal position better. The plans are initially seeded with all or a selection of legal moves.
Sounded great, easy enough to do and easily debuggable since I could for instance print all the plans at all times to monitor the AI decision process.
I had the brilliant idea to write the algorithm in the comments of the code, much better than random code screens, so here it is with a bit of code :

It worked quite well, producing occasional flash of semi-brilliance and actual planning, but was very bad at handling risk taking (either too safe or too insane) and tended to gravitate around a main line (with only superficial changes like one square move difference), ignoring alternatives (poor space exploration, exploitation vs exploration dilemna as usual).
As usual, how to balance the search vs the evaluation... Annoying. Nice actual AI but annoying. Really.
I was fed up with search methods and the lack of control, so I did number 3...

3. RulesAI
Engine : Rules from a Rule Book.

Rules. They are simple, easily controllable.. but predictible and about as un-AI as you can get. But what the heck, it actually works.

1. Each pawn is an Agent. An Agent has a Rule Book. A Rule Book is a set of ordered Rules, from the most urgent/interesting one to the least important.
2. When the AI wants to play, it ask all its Agents what they want to do and the winner (the Agent firing the highest rated rule) does its action.
3. When asked to, the Agent checks its rule book, line by line, until a rule gets fired, and return the resulting action.

Very simple and you can tune a lot of things (for instance a "strategic focus" to arbitrary reward some agent or some kind of rule). If you order and design the rules correctly it produce surprisingly decent AI for a quite low CPU cost when compared to search methods.
Example  of a Rule Book with actual rules :

Individual Agent actions made sense, problem was coordinating the different agents... For instance when attacking I could easily outflank it like you would do against a novice player (move the ball to the center, fix the opponent there, then escape/pass to the wings).
So decent tactics (it did tackling and support very well) but mediocre strategy, which is kinda a classic for strategic games AIs...

* Ok but uh what about Rogue Survivor?
Rogue Survivor AI = KISS : Keep It Simple Stupid.
Its similar to RulesAI presented here, but with much more stuff "hardcoded" and no real engine behind it.
It kinda works because agents are not supposed to cooperate a lot and just do their own stuff.
I did a post about it.

Since you were brave enough to read all this crap, here's a super secret RS screenshot for you :

(that part of 4.0 is not completed yet)

End of post.

Alpha 3.2 Progress

Urgent bug fixes, balancing and CivilianAI improvements.

AI vs CPU : Fight!
I have to keep the AI code as simple as possible. Better AI often eats more CPU. The game will crawl if I do decent pathfinding and proper planning for all the actors. I want the game playable on low end CPUs such as mine ;)
I can do simple improvements that eat little CPU time, but you shouldn't expect "good" AI from 100+ actors.
I will reserve better AI for unique NPCs and player followers.

Simple AI  improvements
One of the AI improvement in 3.2.
Civilians will try to secure the room they will sleep in, as demonstrated in these screenshots.

Release?
Soon. Bug fixes are urgent, I can't have the game crashing left and right.

End of post.

AI

Some words on the AIs in Rogue Survivor. 

Constraints
A strong design choice was to have a lot of NPCs (non-player character) running around. I wanted chaos and interaction. 100+ NPCs on maps is the norm in RS. A lot of NPCs are updated almost each turn. Roguelikes are fast paced games and it is not acceptable to wait 1 second between turns because the 100 fancy AIs use A*, reinforcement learning and whatnot. I also wanted zombies to behave like zombies, and citizens to behave like citizens.
To sum up:

• Fast processing.
• Recognizable and typical behaviors.

Past Experiences with implementing AIs in games
In other game projects I tried to used fancy stuff like Genetic Algorithms, Neural Networks, Planning etc..
Problem is they don't really work or are overkill and you have little control on the decision process. I read a bunch of game AI papers. Most of the time AI researchers are using complex techniques to evolve or design simple pacman-level AIs. So much effort for -excuse me- so ridiculous results.
I had much better results with very simple rule-based AIs and it is faster too. Interesting AI doesn't necessary need complex AI. Note I did say interesting not good. It's a game, you want interesting and amusing NPCs, not competitive NPCs.
Lesson learned. KISS : Keep It Simple Stupid.

Basic algorithm

Straightforward rule-based stuff, not even a FSM and not even an AI engine.

1. Sense the environement with Sensors.
2. Scan a list of rules (trigger -> Behavior) until a behavior propose a valid action.
3. Execute the proposed Action.

That's it. The "intelligence" resides in :

• the use of the Sensors  : they interpret the environement into useful percepts.
• the relative complexity of the Behaviors : they might check for additional conditions or call other Behaviors.
• the ordering of the rules : do this (eg: flee the zombie) instead of that (eg: try to get the item next to the zombie) and the NPC will appear to be clever.

Example AI : CivilianAI (actual code screenshots)
AI used by the hopeless citizens roaming the streets.
They try to survive just like you and they currently have 16 rules to do so.

From the most important one:

...To the least important one:

Some rules are more complex, using percepts computed by the sensor and apply filter on them to get only revelant data.
For instance:

BehaviorGrabItem is more complex too, it checks additional stuff on item, in particular if the NPC really want this item:

Conclusion
So as you can see it's not rocket science. Behaviors and rules aren't even objects, there is no rule engine etc...
But it gets the job done quickly both for me and the player. Those AIs are going to die anyway, and probably out of the player sight, so do you really need fancy stuff? I think not.
Would I do the same for my next game? Yes sir! The only change I would consider is encapsulating behaviors and rules into objects, and better algorithms (A*  pathfinding...) if I can allocate more CPU time.

End of post.