Tuesday, July 6, 2010

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.

3 comments:

  1. nice entry and a interesting read, also suggestion for a skill, Eagle Eye increase your sight radius by a square per level, the first 2 levels adds +1 to sight range at day, and the 3rd level adds +1 to sight range at night (so fully leveled you have +2 sight day +1 sight night) i dont know if it this would be making things too easy but at least you can take more advantage of those long range weapons and having a better chance of spotting "those guys" before they kill you

    ReplyDelete
  2. I'm not too keen on a skill permanently increasing the player FoV and "outfoving" other humans.
    I prefer the temporary increase you get with using Flashlights, and using the GPS item to locate those guys.

    ReplyDelete
  3. Ya, I survive two weeks in my safe house only to get shot twice by those guys and die instantly.

    ReplyDelete