notes/phrases score at different level. Therefore, the optimal timing of Star Power can
heavily influence the score. Calculating how to do this is not obvious, but as we will demonstrate later it can be modelled and solved using Dynamic Programming.
Turn based strategy games
Many turn based strategy games offer the option to “boom” the economy. This is a period
MATH3202/7232 Operations Research & Mathematical Planning 2021
of rapid transition through in game economic stages before active interaction with other players. There are many resource allocation decisions to be made. These decisions can be
Week 9 – Stochastic Dynamic Programming
modelled using Dynamic Programming.
Network Applications
A Transcontinental Drive
A transcontinental drive
An up-and-coming actor decides to drive from New York to Los Angeles to seek
An up and coming actor decides to drive from New York to Los Angeles to seek fame and
fame and fortune. Because he is more or less penniless, he needs to stay with
fortune. Because he is more or less penniless, he needs to stay with friends along the way.
friends along the way. Joe only has a limited number of cities in which he has
Joe only has a limited number of cities in which he has friends, and he categorises each of
friends, and he categorises each of these cities as one, two or three days driving
these cities as one, two or three days driving from New York. With the help of a friend who
from New York. With the help of a friend who does some OR, he comes up with
does some OR, he comes up with the following graph and distance table:
the following graph and distance table:
14
7 NY25 LA
NY to: (1, 550), (2, 900), (3, 770) 1 to: (4, 680), (5, 790), (6, 105) 2 to: (4, 580), (5, 760), (6, 700) 3 to: (4, 510), (5, 700), (6, 830) 4 to: (7, 610), (8, 790)
5 to: (7, 540), (8, 940) 6 to: (7, 790), (8, 270) 7 to: (LA, 1030)
8 to: (LA, 1390)
8
Chess Strategy
5 to: (7, 540), (8, 940) 6 to: (7, 790), (8, 270)
36
NY to: (1, 550), (2, 900), (3, 770) 1 to: (4, 680), (5, 790), (6, 105)
What is the shortest path from NY to LA?
2 to: (4, 580), (5, 760), (6, 700)
3 to: (4, 510), (5, 700), (6, 830)
4 to: (7, 610), (8, 790)
Vladimir is playing Keith in a two-game chess match. Winning a game scores one
m7atoc:h(LpAo,i1n0t3a0n)d drawing a game scores a half match point. After the two games
are played, the player with more match points is declared the champion. If the
8 to: (LA, 1390)
two players are tied after two games, they continue playing until somebody wins a game (the winner of that game will be the champion).
During each game, Vladimir can play one of two ways: boldly or conservatively. If he plays boldly, he has a 45% chance of winning the game and a 55% chance of losing the game. If he plays conservatively, he has a 90% chance of drawing the game and a 10% chance of losing the game.
What strategy should Vladimir follow to maximize his probability of winning the match?
Betting Strategy
Suppose Michelle currently has $2 and is allowed to play a game of chance three times. If she bets b dollars on a play of the game then with probability 0.4 she wins b dollars while with probability 0.6 she loses b dollars. (Each bet must be in a whole number of dollars. She can choose to bet $0 on a game.) Suppose Michelle wants to maximise her probability of having at least $5 after the three games. What strategy of bets should she use to achieve this?
Optimal Stopping
Jenny drives along a straight road towards a particular shop, looking for a vacant parking space. Vacancies occur at random, on average once in every 10 places. Once past the shop, Jenny will take the next available space. But at what point in approaching the shop should she accept a vacant space?