Designing an AI for Cricket

Just not cricket: AI in commercial cricket sims

Over the years I've played several cricket video games (Brian Lara Cricket, EA Sports' series, ICC 2010, Don Bradman Cricket), and one thing that stood out in all of them is the sub-optimal quality of the AI. While the latest update to DBC produced a reasonably competitive AI, it still suffers from the same fundamental problem present in all the cricket games - the inability of the AI to dynamically adapt its strategies during the game, taking into account the match situation and knowledge about the opponents strengths/weaknesses.

As a user, you often experience highly irrational AI behavior, e.g.

• AI batsman defends the last ball when a boundary is needed to win
• AI bats overly aggressive when the asking run rate is low
• AI repeats bowlers who have gone for many runs earlier in the match 

Moreover, the AI is extremely predictable, e.g, the AI bowling and batting orders are typically unchanged in all the games irrespective of the match situation.

Finally, there is rarely (if ever) a display of smart human-like AI behavior, e.g., decide to bat more cautiously against a good bowler with the knowledge that a weaker bowler's overs are still left to be bowled later in the game.

My best guess for the AI techniques used in these commercial games is that they are based on behavior trees and/or finite state machines, with the likely use of hand-coded rules for special situations.

It seemed to me that an approach based on Monte Carlo Tree Search (MCTS) is a much better fit for the problem (in particular you don't need an evaluation function, but instead need to simulate the game mechanics accurately), and so I decided to write an AI engine using it.

Turns out that the AI plays pretty sensibly using this approach and seems to address the problems mentioned above.

Think before you act: An MCTS-based Cricket AI

The basic idea is fairly intuitive: for each decision the AI has to make (e.g. which bowler to bowl next), simulate the effects of all the choices possible for that decision (in this case, the choices are all the available bowlers) starting with the current match state all the way to the end. Then, score the choices based on the payout at the end (i.e. whether it resulted in a win or not) and choose the choice with the highest payout.

For this to work, we need to:

1. Determine the core AI decisions 
2. For each decision, come up with a reasonably finite set of choice points to evaluate
3. Simulate the game as accurately as possible taking both game rules and players attributes/skills into account 
4. Use heuristics to reduce the search space of decisions/moves 

Designing the AI Engine 

The full source code is on github.

Here I'm going to summarize the key design decisions of the model w.r.t the 4 steps mentioned above

For 1, I chose for the AI engine to make the following four decisions:

• Select next bowler 
• Select next delivery type, which involves setting three parameters - pitch zone, speed, movement
• Select next shot aggression, with two additional parameters: 
• latitude - how much to vary aggression based on ball quality (high latitude means drop aggression if ball quality is excellent, zero latitude means go with desired aggression no matter what)
• change-strike - boolean flag indicating a desire to give the non-striker the strike)
• Select next batsman

(Note that this excludes decisions related to field placement and shot selection; this is for future work)

For 2, I used the standard approach of binning the continuous parameters (pitch zone, speed, movement, aggression, latitude)

For 3, I first constructed two teams (India and Australia) and specified batsman and bowler attributes that were consistent with their real world counterparts. I then ran 10K simulated games between the two teams and tuned parameters in the AIEngine class such that the final batsman and bowler statistics aggregated over 10K games was in keeping with their attributes. This is a crucial point - the model needs to be faithful to the players attributes otherwise the MCTS sampling results won't be reliable.

For 4, the key idea was to devise strategies which determined which decision parameters to vary and which to keep constant for all the intermediate decisions made during an MC simulation. For example, an highly efficient strategy (in terms of reducing the search space and improving the result quality) was to keep the aggression and latitude fixed throughout the simulation when deciding the next shot.

How does it play

I simulated several T20 AI (India) vs AI (Australia) cricket matches and noticed much more realistic behavior than I've seen in existing commercial sims.

When Bowling:

• Bowlers who had done well earlier in the match (i.e. given few runs and/or taken some wickets) were given more chances later (and vice versa)
• Bowlers selected their intended ball delivery considering the batsmans strengths and weaknesses and their own abilities
• Good bowlers were called upon to clean up the tail and finish the match (instead of having them come at the end as is typically pre-meditated)

When Batting:

• The batsman's aggression would dynamically change depend on the match situation considering factors such as required run rate, number of wickets fallen, quality of batsman left to come, quality of bowlers left to bowl and the current bowler. E.g., if the required rate was not too high, less risks would be taken against top quality bowlers or against bowlers who had done well earlier in the game
• Tail enders would try to give strike to a more capable partner (unless they themselves had scored some runs or the match situation demanded extreme aggression)
• Batting order changed dynamically depending on the match situation - e.g. a power hitter being sent up the order when the asking run rate was high and the current batsmen were not power hitters

Sample Games

Here are results of 3 sample games to demonstrate the AI's play.

Each game is a T20 match played between India and Australia.

The Indian players with the highest attributes are V. Kohli, R. Sharma (highest batsman execution), M. Dhoni, Y. Singh (highest batsman power) and A. Nehra (highest bowler execution). The weakest bowlers are R. Jadeja and S. Raina. You can see these settings in TestAIEngine.createIndianTeam()

The Australian players with the highest attributes are S. Smith, M. Clarke (highest batsman execution), D. Warner, G. Bailey (highest batsman power) and M. Starc (highest bowler execution). The weakest bowlers are X. Doherty and S. Smith. You can see these settings in TestAIEngine.createAustralianTeam()

You can run games yourself by launching TestAIEngine.java and tweaking the match configuration in the method playMatches(..)

Game 1: Key points demonstrated

• Ability of AI to recover after losing early wickets. This happened in both the innings. 
• India batted first and lost wickets early (being 60/4 in 5.5 overs at one stage) but managed to recover very well with a couple of partnerships (first between Kohli and Y. Singh, and later between Y. Singh and R. Jadeja) and posted a competitive score of 177
• Ability of AI top batsman to manage strike when batting with the tail to prolong innings
• Even though Australia were continuously losing wickets during the run chase, S. Marsh managed to keep most of the strike when batting with the tail and remained not-out  ("*" next to player's name) on 61 at the end. 
• Dynamic Batting Order
• Even though G. Bailey comes after S. Marsh in the regular lineup, he was promoted up the order as the asking rate was increasing alarmingly after the loss of early wickets. The plan didn't work as he got out early.

Game 2: Key points demonstrated

• Ability of AI to plan a big run chase
• Australia batted first and put up a big score of 179 in 20 overs, yet India managed to chase it down in 19.3 overs while regularly losing wickets (at one point being 35/4). Note how the blue worm (India) dips below the green worm (Australia) around ball 83 but steadily accelerates at the end, timing the chase well
• Dynamic Bowling Changes
• In both innings, the AI switched between the two worst bowlers by attributes (Raina/Jadeja for India; Doherty/Smith for Australia) based on their match performance.

Histogram showing runs scored per over for both Innings.
Dark Blue bars indicate >8 runs scored in the over.

Game 3: Key point

• Ability of AI to chase a low target sensibly
• India chased down a total of 119 (less than 6 r.p.o) without being overly aggressive. Note how the blue worm (India) stays below the green worm (Australia) throughout, with the knowledge that lasting longer should achieve the target.

Wrapup

My goal was to develop a proof of concept to test whether an MCTS-based AI engine can play the game of cricket realistically (or at least better than existing sims out there). On an admittedly small sample of simulations (I tested around 50 AI vs AI games), it seems to be working as intended (dynamic decisions that mirror rational human behavior).

Feel free to try out the code and let me know what you think.

The beauty of this approach is that it did not require specifying any rules manually. The model figured out the optimal strategy by evaluating each of the choices in the context of when the decision was made.

Obviously, the game model itself is incomplete (e.g. no field placements). Also, the AI decisions can use more information (e.g. bowler ball placement can consider batsman's history in the match). I'll work on adding these enhancements.

Now if only I had a graphics engine to integrate this AI into :)