Agent-based Systems
Paolo Turrini
↸ www.dcs.warwick.ac.uk/~pturrini p.turrini@warwick.ac.uk
Strategies
Paolo Turrini Strategies Agent-based Systems
The plan for today
Today we are going to define the notion of strategy, in a very basic form of extensive game.
Actions, players, histories
Strategies and winning conditions (in chess and beyond)
Then we are going to move to an abstract treatment of group strategies, which will be the prelude for the second part of the module instead, that dealing with cooperation.
We start without numbers, we are going to add them later on. If you are interested in further results, Chapter 1 of:
M. Maschler, E. Solan and S. Zamir
Game Theory.
Paolo Turrini Strategies Agent-based Systems
What is a strategy?
The blue circle is a lake. The black point is you, on a boat. The red point is a brute, who wants to catch you. The brute can’t swim but moves quicker than you: if you travel a radius, the brute travels half a circumference. On land, you are quicker.
How do you escape? 1
1Credit for this example goes to Chess GM Mihai Suba.
Paolo Turrini Strategies Agent-based Systems
What is a strategy?
”I will not spoil your own pleasure in discovering the solution. I want to emphasise that here you are not supposed to find a move but a strategy, that is a succession of moves, each one depending on the sum total of your own and your opponent’s previous moves, and leading to a clear result.”
Mihai Suba,
Dynamic Chess Strategy, 1991
Mihai Suba
Paolo Turrini Strategies
Agent-based Systems
Chess
Two-player Turn-based
Pieces move according to specific rules
Game ends when a player captures the opponent’s king 2
2This is pretty much the same as using checkmate as terminating condition. My educated guess (I haven’t checked) is that this is a more ancient variant of the game, from which the modern version was born.
Paolo Turrini Strategies Agent-based Systems
Chess
The rules of the game
(in particular captures and three-fold repetition) force the game to be finite
Mathematically, it is a representable as a finite tree, where players (White and Black) take turns to move
Paolo Turrini Strategies Agent-based Systems
Chess
Our set of states is the set of all possible board positions. The starting state is the standard starting board position.
Notice that a board position might be reached in di↵erent ways. We call these ways histories.
Question: is the set of histories finite?
Paolo Turrini Strategies Agent-based Systems
Chess histories, formally
Definition (Chess Histories)
A history is a sequence (x0,x1,…,xK) such that
x0 is the opening board position
For each even integer k with 0 6 k < K, going from position xk to position xk+1 can be accomplished by a single legal move by White.
For each odd integer k with 0 6 k < K, going from position xk to position xk+1 can be accomplished by a single legal move by Black.
Paolo Turrini Strategies Agent-based Systems
Chess strategies
Suppose we want to construct a computer program to play chess.
This program will have to take a decision at each history, where its assigned role (White or Black) can move.
We call this decision a strategy.
Paolo Turrini Strategies Agent-based Systems
Chess strategies, formally
Definition (Strategies)
A strategy for White is a function W that associates to each history (x0,x1,...,xK), with K even, a board position xK+1 reachable by White with a legal move.
A strategy for Black is a function B that associates to each history (x0,x1,...,xK), with K odd, a board position xK+1 reachable by Black with a legal move.
A play of the game is a pair of strategies ( W , B ).
Paolo Turrini Strategies Agent-based Systems
Winning strategies
A play of the game ends either in: a victory for White
a victory for Black a draw
Definition (Winning strategies)
A strategy for White is called winning if, no matter the strategy chosen by Black, it guarantees a win for White.
Formally:
W is winnng for White if and only if 8 B0 , ( W , B0 ) wins for White. For Black, the definition of winning strategy is the same
(but with reversed names!)
Paolo Turrini Strategies Agent-based Systems
At-least-drawing stratgies
Definition (At-least-drawing strategies)
A strategy for White is called at-least-drawing if, no matter the strategy chosen by Black, it guarantees a win or a draw for White.
Formally:
W is at-least-drawing for White if and only if 8 B0 , ( W , B0 ) wins for White or draws.
For Black, the definition of at-least-drawing strategy is the same (but with reversed names!)
Paolo Turrini Strategies Agent-based Systems
An ancient result
Theorem (Zermelo (1913), von Neumann (1928))
In Chess, one of the following must be true:
White has a winning strategy
Black has a winning strategy
Both players have an at-least-drawing strategy
Over 100 years and we still don’t know which one of them is true!
Paolo Turrini Strategies Agent-based Systems
Proof (1/3)
Proof.
Let us first recall that the game is finite, i.e., there is a natural number K such that every play of the game concludes after at most 2K rounds,
(K turns by White, K by Black).
Paolo Turrini Strategies Agent-based Systems
Proof (1/3)
Proof.
Let us first recall that the game is finite, i.e., there is a natural number K such that every play of the game concludes after at most 2K rounds,
(K turns by White, K by Black).
Assume there are exactly 2K turns in every play of the game. Notice that if some plays are shorter, we can simply continue them by adding a “do nothing” move, preserving the result (so, for instance if we extend a play where White wins, we keep track of this).
Paolo Turrini Strategies Agent-based Systems
Proof (2/3)
Proof.
For every k with 1 6 k 6 K denote:
Paolo Turrini Strategies Agent-based Systems
Proof (2/3)
Proof.
For every k with 1 6 k 6 K denote:
ak the move implemented by White at their turn. bk the move implemented by Black at their turn.
Paolo Turrini Strategies Agent-based Systems
Proof (2/3)
Proof.
For every k with 1 6 k 6 K denote:
ak the move implemented by White at their turn. bk the move implemented by Black at their turn.
Denote W the fact that White wins (after 2K turns), ¬W the fact that White does not.
Paolo Turrini Strategies Agent-based Systems
Proof (2/3)
Proof.
For every k with 1 6 k 6 K denote:
ak the move implemented by White at their turn. bk the move implemented by Black at their turn.
Denote W the fact that White wins (after 2K turns), ¬W the fact that White does not.
But then, the fact that White has a winning strategy can be written as:
9a18b19a28b2 . . . 9aK 8bK (W )
Paolo Turrini Strategies Agent-based Systems
Proof (3/3)
Proof.
So, the fact that White has not a winning strategy can be written as:
¬9a18b19a28b2 . . . 9aK 8bK (W )
Paolo Turrini Strategies Agent-based Systems
Proof (3/3)
Proof.
So, the fact that White has not a winning strategy can be written as:
¬9a18b19a28b2 . . . 9aK 8bK (W ) This, using first-order logic, is equivalent to:
8a19b18a29b2 . . . 8aK 9bK (¬W )
Paolo Turrini Strategies Agent-based Systems
Proof (3/3)
Proof.
So, the fact that White has not a winning strategy can be written as:
¬9a18b19a28b2 . . . 9aK 8bK (W ) This, using first-order logic, is equivalent to:
8a19b18a29b2 . . . 8aK 9bK (¬W ) But this says that Black is guaranteed at least a draw!
Paolo Turrini Strategies Agent-based Systems
Proof (3/3)
Proof.
So, the fact that White has not a winning strategy can be written as:
¬9a18b19a28b2 . . . 9aK 8bK (W ) This, using first-order logic, is equivalent to:
8a19b18a29b2 . . . 8aK 9bK (¬W ) But this says that Black is guaranteed at least a draw!
We can do exactly the same for Black.
Paolo Turrini Strategies Agent-based Systems
Proof (3/3)
Proof.
So, the fact that White has not a winning strategy can be written as:
¬9a18b19a28b2 . . . 9aK 8bK (W ) This, using first-order logic, is equivalent to:
8a19b18a29b2 . . . 8aK 9bK (¬W ) But this says that Black is guaranteed at least a draw!
We can do exactly the same for Black.
Therefore, one of the three alternatives must hold.
Paolo Turrini Strategies Agent-based Systems
Solving a game vs beating the World Champion
Solving a game = finding the objectively best continuation from the start. Solving a position = solving the game starting from there.
AI is very good at some games. But is it perfect?
Paolo Turrini Strategies Agent-based Systems
Solving a game vs beating the World Champion
Chess is not a solved game. Even if DeepBlue has beaten Kasparov.
Paolo Turrini Strategies Agent-based Systems
Solving a game vs beating the World Champion
Go is not a solved game. Even if AlphaGo has beaten Lee Sedol.
Paolo Turrini Strategies Agent-based Systems
Solving a game vs beating the World Champion
Checkers is a solved game. It’s a draw.
Paolo Turrini Strategies Agent-based Systems
Solving a game vs beating the World Champion
Chess is not solved, but some chess endgames are. Chance it gets solved any soon? https://arxiv.org/abs/1712.01815
Paolo Turrini Strategies Agent-based Systems
What Next?
In Chess, we might have a strategy to win or to draw.
But, if we don’t know it, there is not so much we can do....
We are going to be talking about knowledge
(e.g., knowing that you can win vs. knowing how you can win)
Paolo Turrini Strategies Agent-based Systems