Summary Modelling Computing Systems Hoofdstuk 10 Faron Moller & Georg Struth
26 vistas 0 compra
Grado
Logic For Computer Science (INFOB1LI)
Institución
Universiteit Utrecht (UU)
Book
Modelling Computing Systems
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...
modelling computing systems faron moller amp georg struth
Libro relacionado
Título del libro:
Autor(es):
Edición:
ISBN:
Edición:
Más resúmenes para
Samenvatting alle stof logica voor informatica
Samenvatting Logica voor Informatica (INFOB1LI)
Samenvatting Logica voor informatica
Todos para este libro de texto (13)
Escuela, estudio y materia
Universiteit Utrecht (UU)
Informatica
Logic For Computer Science (INFOB1LI)
Todos documentos para esta materia (12)
Vendedor
Seguir
luukvaa
Comentarios recibidos
Vista previa del contenido
Hoofdstuk 10:
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.
Los beneficios de comprar resúmenes en Stuvia estan en línea:
Garantiza la calidad de los comentarios
Compradores de Stuvia evaluaron más de 700.000 resúmenes. Así estas seguro que compras los mejores documentos!
Compra fácil y rápido
Puedes pagar rápidamente y en una vez con iDeal, tarjeta de crédito o con tu crédito de Stuvia. Sin tener que hacerte miembro.
Enfócate en lo más importante
Tus compañeros escriben los resúmenes. Por eso tienes la seguridad que tienes un resumen actual y confiable.
Así llegas a la conclusión rapidamente!
Preguntas frecuentes
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
100% de satisfacción garantizada: ¿Cómo funciona?
Nuestra garantía de satisfacción le asegura que siempre encontrará un documento de estudio a tu medida. Tu rellenas un formulario y nuestro equipo de atención al cliente se encarga del resto.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller luukvaa. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for $3.44. You're not tied to anything after your purchase.
