2020-2021:teams:legal_string:lgwza:博弈论
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:博弈论 [2020/09/25 17:43] lgwza |
2020-2021:teams:legal_string:lgwza:博弈论 [2021/07/18 22:26] (当前版本) lgwza [博弈论和 SG 函数] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 博弈论和 SG 函数 ====== | + | ====== 博弈论 ====== |
| ===== 必胜点和必败点 ===== | ===== 必胜点和必败点 ===== | ||
| 行 111: | 行 111: | ||
| **题意**： | **题意**： | ||
| - | * 这是一个二人游戏，两人轮流走； | + | * 这是一个二人游戏，两人轮流走； |
| * 一共有 3 堆石子，数量分别是 $m,n,p$ 个； | * 一共有 3 堆石子，数量分别是 $m,n,p$ 个； | ||
| * 每走一步可以选择任意一堆石子，然后取走 $f$ 个； | * 每走一步可以选择任意一堆石子，然后取走 $f$ 个； | ||
| 行 334: | 行 334: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| + | ===== 威佐夫博弈 ===== | ||
| + | |||
| + | ==== 简介 ==== | ||
| + | |||
| + | 两个玩家轮流行动，在两堆石子中选一堆取走任意个，或同时在两堆石子中取走相等的石子数，最后取光所有石子的人获胜。这个游戏的一个等价描述是：一个棋子放在一个大棋盘上，两人轮流移动棋子，向下，向左或向左下移动任意步，胜者是将棋移动至原点的人。 | ||
| + | |||
| + | ==== 最优策略 ==== | ||
| + | |||
| + | 游戏中的任一状态可由一对整数描述 $(n,m)(n\le m)$，游戏中的状态点分为必败点和必胜点。在必胜点的最优策略是移动至任一可到达的必败点。必败点和必胜点的分类由以下三条规则递归给出： | ||
| + | |||
| + | - $(0,0)$ 是必败点； | ||
| + | - 可一步走到必败点的点是必胜点； | ||
| + | - 如果无论怎样走都只能到达必胜点，则该点是必败点。 | ||
| + | |||
| + | 前几个必败点是：$(0,0),(1,2),(3,5),(4,7),(6,10),(8,13)$。 | ||
| + | |||
| + | === 变形：最后一步移动的人为败者 === | ||
| + | |||
| + | $(0,1),(2,2)$ 是必败点，$(n,m)(2<n\le m)$ 是必败点当且仅当 $(n-2,m-2)$ 在正常游戏中是必败点。 | ||
| + | |||
| + | ==== 必败点的判定准则 ==== | ||
| + | |||
| + | $\phi=\dfrac{\sqrt 5+1}{2}$，第 $k$ 个必败点 $(n_k,m_k)$： $$ | ||
| + | n_k=\lfloor k\phi\rfloor=\lfloor m_k\phi\rfloor-m_k\\ | ||
| + | m_k=\lfloor k\phi^2\rfloor=\lceil n_k\phi\rceil=n_k+k | ||
| + | $$ 若给定 $(n,m)$，判断其是否为必败点，则判断 $\lfloor(m-n)\dfrac{\sqrt 5+1}{2}\rfloor==n?$，必要时使用 $\lfloor\sqrt{5(m-n)^2}\rfloor==3n-m?$ 来判定（二分答案算根号）。 | ||
| + | |||
| + | ==== 多于两堆的情况 ==== | ||
| + | |||
| + | 玩家可任选一堆石子取走任意数量，当选择多于一堆石子时，则每堆取走的石子数需相同。 | ||
| + | |||
| + | 例如，$(1,1,3)$ 和 $(1,2,3)$ 是必胜点，因为它们能到达必败点 $(0,1,2)$。$(1,1,4),(1,3,3)$ 是必败点。 | ||
2020-2021/teams/legal_string/lgwza/博弈论.1601026994.txt.gz · 最后更改: 2020/09/25 17:43 由 lgwza
