Discrete games between two players

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 18 · page 18.1
Discrete games between two players
The elements of the game, the analysis from the end, the simulation with the AI.
At the EGE 19, 20, 21 is a game of two players with stones/numbers.
End-to-end analysis
We mark the losing positions (L) as multiple K+1. The rest are winning positions (W).
GEF
PIF
EGE No. 19,20.21
01
Elements of the game
Players
- Two (Peta and Wasa, or First and Second).
Position
is the current state (e.g. the number of stones S).
Progress
- Transforming the position on the rules.
Rules
- permissible steps (e.g. +1 or *2).
Objective
To achieve a win-win situation (≥N, last move).
Strategy
- a win-win plan for every move.
02
End-to-end analysis
Algoritm
Mark
winning final position
(S ≥ N) as W.
Mark position as
L (less)
if all of her moves go to W.
Mark position as
W (win)
if one move leads to L.
Repeat until all positions are marked.
Keypathern
For the "1..N" game, by going +1 or *2, to reach ≥N, the losing positions are multiples.
(K+1)
For example, for N=20: 3, 6, 9, 12, 15, 18 are losers (if you walk first and target ≥20).
03
Game with I.I.: "Cambers +1 or ×2"
You're playing against optimum I. The goal is to reach ≥N.
🎮
Game with I.I.: Up to N
Goal N
Start S
Сделай ход!