Logic for Computer Science / Logica voor computertechnolgie hoofdstuk 10. Samenvatting van het boek Modelling Computing Systems geschreven door Faron Moller en Georg Struth. Samenvatting geschreven in het Engels. Aan de hand van voorbeelden en plaatjes wordt de stof en theorie verduidelijkt. Gegeve...
We can distinguish between different kinds of games:
- Games of chance – like roulette – where there is no good strategy for winning.
- Games of no chance – like tic-tac-toe or chess – where some moves are clearly better than
others.
10.1 Strategies for Games-of-No-Change
We are interested in two-player games of no chance with perfect information. This means that both
platers know what moves have been made up to that point in time, as well as what moves their
opponent can make in response to any move that they themselves make. Chess is a game of perfect
information, poker is not – as players only know the cards in their own hand. And we will only study
finite games that are guaranteed to end after some finite number of moves.
A strategy for a player in a game is a rule which tells that player what move to make each time it is
their turn to move. A position in a game is a winning position, if the player whose turn it is has a
winning strategy from this point. It is a losing strategy if the other player (whose turn it is not) has a
winning strategy from this position.
From a winning position must be a move to a losing position, while every move from a losing
position must lead to a winning position. From a drawing position there must be some move to a
drawing position, perhaps some moves to winning positions, but no moves to losing positions.
Example game “21”:
Two players count, starting from one. They take turns in saying one, two or three numbers. The
player that says “twenty-one” wins. How can player A always beat player B?:
- If it’s player A’s turn to say 21 he has won.
- If it’s player A’s turn, and the current count is 17 – he is in a losing position. Regardless of
player B’s move, he can always reach 21 and player A cannot win.
- By the same argument, 13 is also a winning position;
- As are 9, 5 and 1.
So the first player has a winning strategy: always finish on a number that is 1 modulo 4.
Reminder:
- A strategy is a rule that computes the best move a player can make at any given point in the
game.
- A winning strategy is one that guarantees the player will win the game.
- A drawing strategy is one that guarantees the player will win the game or draw (but not
lose).
- A position in a game is called a winning position if the current player has a winning strategy
(such as 19 in the game Twenty-one).
- If the other player has a winning strategy in the current position, this is known as a losing
position (such as 17 in the game Twenty-one).
, Example game “10 coins”:
There are 10 coins on a table. Players take turns by removing two or three coins. The player that
takes the last coin wins; if one coin remains, the game has ended in a draw.
If it is your turn and:
- there are no coins left, you are in a losing position;
- there is one coin left, you are in a drawing position;
- there are two coins left, you are in a winning position;
- there are three coins left, you are in a winning position;
We can tabulate the different kinds of positions for each number of coins:
We can also visualize this game by drawing a game tree describing the possible moves and
associated positions for each possible game state.
Each node contains a number, corresponding to the current game state; each node has two
subtrees, corresponding to the state after removing 2 or 3 coins. Furthermore, each node has been
decorated with a circle if it is a winning position and square if it is a losing position; the double
arrows indicate the best move to make at any given position.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper luukvaa. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €2,99. Je zit daarna nergens aan vast.
