Summary Modelling Computing Systems Chapter 10 Faron Moller & Georg Struth
26 views 0 purchase
Course
Logic For Computer Science (INFOB1LI)
Institution
Universiteit Utrecht (UU)
Book
Modelling Computing Systems
Logic for Computer Science/Logic for Computer Technology Chapter 10 Summary of the book Modelling Computing Systems written by Faron Moller and Georg Struth. Summary written in English. Using examples and pictures, the substance and theory are clarified. Given at Utrecht University.
modelling computing systems faron moller amp georg struth
Connected book
Book Title:
Author(s):
Edition:
ISBN:
Edition:
More summaries for
Samenvatting alle stof logica voor informatica
Samenvatting Logica voor Informatica (INFOB1LI)
Samenvatting Logica voor informatica
All for this textbook (13)
Written for
Universiteit Utrecht (UU)
Informatica
Logic For Computer Science (INFOB1LI)
All documents for this subject (12)
Seller
Follow
luukvaa
Reviews received
Content preview
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
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.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes 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 these notes for $3.21. You're not tied to anything after your purchase.
