I just came across this article which digs through the actual code of the original NES version of Tetris and then creates an AI to play it.
Speaking of game AI…two Pac-Man-related links are making the blog rounds these days – one of them is new.
The new one is Chad Birch’s “Understanding Pac-Man Ghost Behavior”. It is clear and well illustrated.
As Chad points out, he was inspired by and used Jamey Pittman’s “Pac-Man Dossier”. This is a nice resource.
It also seems that I haven’t previously blogged Don Hodges’ fix to a bug in the behavior of two of the ghosts. (The bug-fixing of classic videogames is a topic we will return to in the future.)
Of course, the ghosts need a Pac-Man to chase. I have previously linked to a Ms. Pac-Man computer player competition. Of specific interest is this paper on evolving rules to play Ms. Pac-Man (seems that I have not directly linked it before).
(Post title is of course a play on the “magnets…” meme.)
The folks at the PokerStars online poker service actively police their games to make sure that bots are not being used to gain advantage.
Here’s a recent post from their Game Security staff demonstrating that they paid a visit to one player in order to witness the playing and playstyle in person.
It ends with the following wonderful quote:
We are pleased to report, however, that ‘rs03rs03’ is human.
It has been ten years to the day since John E. Laird and Michael van Lent published their paper “Human-level AI’s Killer Application: Interactive Computer Games”. In ten years, what has and hasn’t changed?
I am often asked to describe the rule engines that Microsoft ships. (The first question being: “Microsoft has rule engines?”) This question frequently comes from folks who know rules, but don’t know .NET. This post is specifically written to answer the question. Should the offerings change in the future, I will update this post as needed.
As always, this is not an official Microsoft statement. Questions about the future directions for these products should be directed to Microsoft.
As of this writing, Microsoft is currently shipping two rule engines. They are aimed at somewhat different audiences as described below.
The first rule engine is called the Microsoft Business Rule Engine (sometimes called “MS BRE” or “BRE”) and it has shipped as part of BizTalk Server since early 2004. BRE has shipped in BizTalk Server 2004, BizTalk Server 2006, BizTalk Server 2006 R2, BizTalk Server 2009 and I’m sure it will be included in the upcoming BizTalk Server 2009 R2.
The second rule engine is part of Windows Workflow Foundation in .NET, it is the Windows Workflow Foundation Rules Engine (sometimes called “Workflow Rules” or “WF Rules”). The WF rule engine originally shipped in late 2006 as part of .NET 3.0. It was also included in .NET 3.5 and .NET 4.0. If you are running Windows 7, Windows Server 2008 R2, Windows Server 2008, or Windows Vista or have installed .NET 3.0 or higher – you already have the WF rule engine on your computer. Update: I have an additional post specifically about rules in WF4.
Comparing MS BRE & WF Rules
Here are some comparisons of these engines written by other folks. Charles Young has written extensively on this topic.
- Charles Young – Comparing WF rules and the Microsoft Business Rule Engine
- Charles Young – BizTalk Server or WF for rules and tracking?
- Charles Young – WF Rules and MS BRE – Comparing Performance
- Stephen Kaufman’s comparison that was presented to the Twin Cities BizTalk User Group. (In my opinion, the agenda terminology in this presentation could be a little more crisp. In addition, the “Types vs Instances” section should mention the fact that the single-rooted structure can also be used in BRE.)
A Short Summary Of Differences For Those Who Know Rules
If you asked me to summarize differences for a rules specialist, my comments would be along the following lines:
- MS BRE is part of a BizTalk Server, which is a business-oriented server package, while WF Rules is part of the free .NET Framework which is more developer-oriented. (MS BRE may be used standalone outside of BizTalk, but is only licensed with BizTalk.) Both engines provide forward chaining execution. WF Rules also provides the option for sequential execution.
- MS BRE rules are typically authored in the Rules Composer, while WF Rules are typically authored in Visual Studio. There are partners that provide a more BRMS-like authoring environment. MS BRE has features such as vocabularies and a respository, and is therefore closer to what Gartner defines as a BRMS.
- MS BRE implements the Rete algorithm, while WF Rules does not. MS BRE uses eager evaluation, while WF Rules uses lazy evaluation. The performance profiles are accordingly different – WF “first hit” execution being faster, for example.
- WF does not have assert/retract keywords or a Working Memory, while MS BRE does – so WF Rules requires all objects to be reachable from a common root object (this). (In WF Rules, support for multiple instances is achieved through forward chaining.) WF Rules supports “Else”, while MS BRE does not. MS BRE has some known restrictions around negation-as-failure. MS BRE has special handling for XML and DB fact types.
I would be remiss if I did not mention some Microsoft offerings that apply to related areas:
- Microsoft Solver Foundation – a constraint-solving framework
- Microsoft StreamInsight – a Complex Event Processing engine
- Reactive Framework (Rx) – adds operators such as ForkJoin to .NET
Lastly, I should also point out that the Mono Project is reimplementing Windows Workflow Foundation – including WF Rules.
Cheers to James Owen for his stewardship of the October Rules Fest for 2008 and 2009. I was only able to attend a small portion of the 2009 conference, but those portions were quite good. The sign of a healthy conference is one where attendees return as presenters and this year had a few such presentations (Andrew! David!). It was great to see everyone again, but I missed a few folks who were unable to return.
I think my previously posted comments from last year are largely still applicable:
Since James is now returning to working for a vendor, October Rules Fest will now be organized by Jason Morris. The conference is in good hands – Jason is an excellent choice. Make your wishes for ORF 2010 known now.
Every so often I hear about a “friend of a friend” who has implemented a backward chaining project with one of the Microsoft rule engines (WF Rules, BizTalk MS BRE). However, the details usually fail to materialize. If you have worked on such a system, or know someone who has – please contact me using the contact form on this blog. I’m interested in understanding more about your project and how successfully the backward chaining implementation went.
(As always – this is mainly personal interest, and does not reflect on any future directions of my employer’s products.)
One of the recurring topics in the rules world is forward chaining vs. backward chaining – how they compare, when to use one or the other, and which implementations even offer back chaining. I suspect that a lot of the confusion around backward chaining is simply due to the fact that most folks haven’t implemented production-quality systems that make use of it.
Backward chaining systems are more limited than forward chaining systems.
Dietrich points out that the article was located on the old Rulespower site and disappeared with the purchase by Fair Isaac.
I’m posting here simply to point out that the Wayback Machine has them.
Charles Forgy on Forward and Backward Chaining
I have linked directly to the latest archived version of each article segment. You can find all the RulesPower content that they have here.
For further reading on the topic, the discussions at the following links are interesting (in no particular order):
- Paul Haley on backward chaining using rete
- Paul Vincent on goal-directed event processing – in which he points out that backward chaining was dropped from PRR due to lack of vendor interest
- James Owen on the problems with performing full opportunistic backward chaining on a forward chaining engine
I found a quote that James Owen used on the JESS mailing list and I’m interested in learning where it comes from. More specifically, is it in a paper or article somewhere and I’m just overlooking it? My suspicion is that James is quoting Dr. Charles Forgy and that it isn’t published in any articles.
I’ll email James to check the source – but I wanted to highlight the quote here since it was only used on the JESS list and could use a little more exposure.
“Any forward chaining engine can be made to do backward chaining and any backward chaining engine must eventually forward chain to deliver results.”
Updated on January 13, 2010:
James has confirmed (via email) that he was paraphrasing Dr. Charles Forgy here. The comment apparently was made during OPSJ training classes.