How to solve real-time games?

Question

In game theory, we can solve a game by calculating its game tree as backward induction. This method seems to work for turn-based games, but how about real-time games? Are they have game trees? It seems we cannot even talk about 'next move'.

Answer 1

Consider a single-player game in which the player can at each point in $[0,1]$ play an action ${A,B}$. She can choose history dependent strategies, so a strategy is a function that maps elements of $\{A,B\}^{[0,r)}$ (the history) to $\{A,B\}$.

Consider first the strategy "Play $A$, unless you have played $B$ before." That is, the strategy maps histories in which $B$ has been played to $B$ and all others to $A$. Let $r\in(0,1)$. Then the player playing $A$ on $[0,r)$ and $B$ on $[r,1]$ is compatible with this strategy. A continuum of outcomes is compatible with the strategy.

Next, consider the strategy "Play $A$ initially. Then play $B$ if $B$ has never been played before. Otherwise play $A$." Since this strategy would require to play $B$ at the smallest positive real and $A$ everywhere else, there is no outcome compatible with the strategy.

So even the simplest games in continuous times can be very badly behaved (all these problems would occur in a continuous time version of the prisoners dilemma). A detailed study of what games have the property that every strategy profile induces a unique outcome can be found in the paper Trees and Extensie Forms (not open access) by Alos-ferrer and Ritzberger.

Answer 2

A real-time game is just a turn-based game where simultaneous turns are allowed(e.g. rock paper scissors) and there are lots of turns. e.g. starcraft, every frame you can do one move and your opponent can do one move

Answer 3

Think about playing singles Mario tennis against an opponent. At each instant you can make one of a finite number of 'moves' (move left, move right, hit one or more buttons corresponding to hitting the ball, pause, etc.) This can be seen as the 'limit' of a series of games that are turn based but have more and more frequent turns (maybe one thousand per second).

Let's say you and your opponent each make one move per second and there are ten buttons on your game pad (for simplicity, assume you can only hit one button at a time.) If you assume a game lasts two minutes, that is 20^240 possible ways the game can play out. Now think about fifty possible moves per second instead of one and you can see that the task of 'calculating a game tree' as hopelessly intractable.

Answer 4

"Differential Games" are one way of modelling strategic interactions where time is continuous. One tutorial: http://www.math.psu.edu/bressan/PSPDF/game-lnew.pdf