*by
Sudharshana
*

Growing up in India, the only game that has excited me the most is Cricket. I got to know that DP was being used to resolve conflicts due to shortening of game time while reading about DP in Wikipedia. While searching I found this article “Dynamic Programming in One-Day Cricket – Optimal scoring rates” by Stephen Clarke.

THE GAME:

It is a bat-ball game between two teams with 11 players each. Each team gets a set amount of time, 50 or 20 overs each (6 balls bowled make an over). They have to get an optimal score (run) at the end of play, which is either using up all overs or losing 10 batsmen (wickets). A coin toss decides which team bats first (first innings) and then the second team tries to beat the score set by the previous team (second innings) within the stipulated time. Other constraints include field placings.

THE PROBLEM:

While the objective of Team 1 is to score as many runs as possible, the second team only has to score at least as many as Team 1. At each stage the batsman has to decide how fast to score. To increase the rate of scoring, he/she takes greater risks, which increases chance of losing wickets. If wickets are lost soon, then the innings will end prematurely with a low total score.

RUN RATE:

For each ball, the batsman can either lose his wicket or score a run between 0-6.

If p_d is the probability of dismissal

p_x is the probability of scoring ‘x’ runs

then,

Run-rate per ball = Expected value of the number of runs scored per ball = SUM(x*(p_x))

In most calculations we look at statistics for an over (6 balls), so the run rate would then be R = 6*run-rate per ball

MYOPIC POLICY:

There are several strategies followed in Cricket, the most common one being “Bat slowly in the early overs of the innings, keeping wickets in hand. In the end, the confidence of having wickets in hand helps to make risky game play decisions and typically brings a last-minute orgy of runs”.

FORMULATION:

STAGE: The number of balls (n) to go.

STATE: The wickets (i) in hand.

Value functions V_n(i) = MAX { (p_d*V_n-1(i-1)) + SUM{p_x*(x+V_n-1(i))} } ; maximize over R

=MAX{ (p_d*V_n-1(i-1)) + R/6 + ((1-p_d)*V_n-1(i)) } ; maximize over R

Each ball

- a batsman loses wicket, the team has one less wicket in hand and one less ball to go (or)

- scores x runs, the team has one less ball to go with same number of wickets

Boundary Conditions:

Innings finishes when

- No more players are left i.e. V_0(i)=0 for i = 0-10

-No more balls to be bowled (assuming 50 over match) i.e. V_n(0)=0 for n = 0-300

Note: The paper discusses separate formulations for second and first innings because the second team knows the required score to play for.

A new parameter (the number of runs to go, ‘s’) is included into the state.

Each ball

- a batsman loses wicket, the team has ‘s’ runs to score with one less wicket in hand and one less ball to go (or)

- scores x runs, the team has to score s-x runs with one less ball to go but same number of wickets

Results:

They have computational results for both innings, which can be found in the paper.

There are more complexities that can be added to the game, such as what if the strategies of the teams are reversed, or the game-play is interrupted due to un-warranted situations, etc. More on this, to come.

Hope you enjoyed the post, and will catch a game of Cricket some day!

## Comments

Another application of DP to cricket is the Duckworth-Lewis method for setting targets in one-day matches which are interrupted by weather and bad light. There is an entry on Wikipedia which describes Duckworth and Lewis as statisticians. However Frank Duckworth is, Tony Lewis is an O.R. person and the key paper on the method is in the Journal of the OR Society (Duckworth, FC & Lewis, AJ “A fair method of resetting the target in interrupted one-day cricket matches” Journal of the Operational Research Society, (Mar 1998) Volume 49, No. 3 pp 220–227 JSTOR 3010471).

There are several other applications of DP to sports John Norman wrote a paper on this in 1995) and board games. Google scholar will turn up some of these.

I think it is great that dynamic programming can be used in arenas other than the typical type problems that we learn in class. Based on the approach, it also sounds like sequential game-theory as well. Especially with plays depending on who bats first, and how the second team responds. It makes me wonder if there is more research regarding Cricket within the use of other methodologies, such as game theory.

Yes, there is a significant literature about aspects of O.R. and cricket. If you have access to IAOR (International Abstracts in OR) the keyword “cricket” turns up 31 abstracts. As you might guess, many of these have appeared in journals published in the U.K.

David, Thanks for mentioning the article.I was going to talk about the application of DP to the Duckworth-Lewis method in my next blog, and your resource was very helpful.

Becky, I think it is interesting to see that there are several methods adopted to solve a problem and that the choice of the method to adopt depends on the situation and the decision-maker.

Similarly to Becky, I wonder how the DP analysis of cricket you wandered upon, Suds, differs from (or resembles?) game theory? In particular, this:

“While the objective of Team 1 is to score as many runs as possible, the second team only has to score at least as many as Team 1.”

Seems to suggest the need for distinct value functions for the two teams involved? Or, at least, value functions that vary depending on which role a team has taken?

Did the article you investigated ever talk about simultaneous optimizing, Suds — like, both teams optimizing, holding the other team’s strategy fixed?