Discrete Games: Strategies, Minimax, Dakestra, A*

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

Back to the table of contents
Alterna chapter 19
Discrete Games: Strategies, Minimax, Dakestra, A*
Foundation for EGE Nos. 19, 20, 21 (games) and 1 (graphs).
Disaggregated games are a problem where two players make their moves until someone wins.
End-to-end analysis
- mark the loser positions (L) and the winning positions (W), as well as the Dakestra short way algorithm (EG1).
GEF · 11 grade
PIF · Baseline
EEG No. 1, 19, 20, 21
19
Chapter Pages
Five pages with theory, interactors and a bank of assignments.
19.1
Winning Positions
End-to-end analysis, L/W.
Playing with the AI
"Cambers +1 or ×2." Mini test 5/50.
19.2
Game Tree
Algorithm minimax with alpha-beta cut-off.
Visualizer
For trees of depth 3.
20.3
The Shortest Way
Dakestra algorithms and A*.
Visualizer
step by step on the 6th line.
19.4
Workshop
Bank 50+works: EEG + EEG No. 1.19-21.23 with reviews.
19.5
Polygon examination
Quest 800 XP + test 10 min +
2 tasks developed
(game + tree).
🔗
Links with other chapters
Chapter 17 (Graphs)
Dakestra works on weighted graphs.
Calculation of the routes to the DAG
uses dynamic programming, as well as game analysis from the end.
Chapter 24
DAG, topsort, track count.
Dakstra is the extension of the search for the shortest path to the weighted graphs. The formula dp[v] = .dp[u] is similar to the analysis from the end.
Chapter 18
Boolean algebra
The Minimax uses the logic of AND/OR to select a move. L-position = FALSE (lose), W-position=TRUE (win).
Chapter 25
Trees, BST
The tree of the game is the same binary tree as BST. Leaves = terminal positions. Overtaking the anorder = calculation of the minimax.
EEG/EEG Liaison
OGE No. 4
- diagrams, graphs, paths
EGE No. 1
- Dakestra (shortest route)
EEG No. 3
- Counts, finding a way.
EGE No. 19-21
- Game theory, analysis from the end.
EEG No. 23
- logical equation systems (minimex on trees)