Tuesday, September 9, 2014

What one can learn from Game AI development

Below is an excerpt from STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving, R. E. Fikes and N. J. Nilsson, Artificial Intelligence 2 (3--4), 1971. (pdf):
STRIPS belongs to the class of problem solvers that search a space of “world models” to find one in which a given goal is achieved. For any world model, we assume there exists a set of applicable operators each of which transforms the world model to some other world model. The task of the problem solver is to find some composition of operators that transforms a given initial world model into one that satisfies some particular goal condition.
The basic idea is that a world model is modified by operators, which have a set of preconditions and side effects. STRIPS planner is used to find out how to apply these operators to achieve the goal given some state. (But don't confuse this approach with a Prolog programming language that operates with formal logic on top of knowledge base without any side effects.) The original algorithm without any optimizations is simple: find which operator achieves the goal, then if operator's prerequisites are not satisfied your new goal is to satisfy those, in the end choose the easiest plan. STRIPS was featured in F.E.A.R. and a number of other games, that was (and to some degree still is) a cutting edge in game AI development.

The main thing one can learn from this is a clear segregation between WHAT and HOW. WHAT is your goal defined in terms of conditions applied to the state (defines a subset of all possible states). HOW is a set of operators that do the job. Everything else does planner that doesn't depend on the domain and can be easily reused from project to project.

An example
Imagine you are about to implement private cloud solution. You can implement a set of operators like bring interface up, make a bridge, obtain address via DHCP, mount volume, create container with lxc, etc. Each of these operators have prerequisites like to obtain address via DHCP an interface must be up and running. Define states in terms of MIBs and use SNMPv3 to get/set state. Then you can easily define goals like provision a vm and planner will do it for you using defined operators. The good news is that if something happens in the middle of vm provisioning (state changed from A to A') planner can deal with this by providing a new plan. If you need to integrate someones solution just add a few new operators and planner will benefit from them immediately. Compare and contrast this approach to OpenStack solution that is obsessed by (micro-)SOA ideas not in the best way.
Can this be applied to the web development? Consider you have a bunch of operators with arguments, prerequisites and side effects defined. In case one does not handle these operators as black boxes and with the bit of introspection understands prerequisites and side effects planner can build workflows by connecting operators together and it can also build an interface to input arguments for operators in the plan and react to unexpected (what if Paypal payment failed, planner can suggest you to pay in another way). The only thing left is to present current state in a nice way to the user.

Final thoughts
One day devs used macro assembler, then C, nowadays OOP and FP hit the fan, but we need to go further and program in terms of business rules and goals. Even AngularJS and Backbone are too low level.

Wednesday, September 3, 2014

Glue together git, feature branches, Jenkins and Redmine

Feature branches or topic branches are useful thing to keep master stable and to introduce atomicity and isolation to what you are doing. But when you commit your work and set task to Resolved state it doesn't mean that this fix is ready to be tested by QA team. There is a time lag between the moment you resolve an issue in issue tracker and it is rolled out on test environment: your lead needs to review your changes, QA lead needs to make a build that will grab your change and put it to the testing env.
There is a simple solution to this issue though. First of all a custom field has been added to the tracker (issue/bug/feature/ticket) in Redmine namely Issue fixed build number (ok, it must have been called Issue fixed commit), when someone resolves a ticket it fills in the last commit in corresponding feature branch. If one sees this commit in some branch he can say with confidence that this branch contains changes for this feature (after you merge feature branch to the master you'll see there the same commit hash, it doesn't hold for rebase).
Secondly you'll need the proprietary JenkinsRedmine plugin, see Building a plugin. The plugin actually does two simple steps:
  1. Gets all commits in fetched by Jenkins brunch issuing git log command
  2. Gets all issues in Resolved state for given project from Redmine (see Redmine REST API for Issues), checks which Issue fixed build numbers are in git log
Then it just draws a table like below. It omits issues that are not found in git log. Thus QAs get the list of issues to check on test environment.