挑战≈ 16 分钟未开始
必胜态与必败态
核心概念
把每个游戏局面分成两类(指轮到谁走时该人的前景):
- 必败态(P 态):轮到你走却必输的局面;
- 必胜态(N 态):轮到你走且能取胜的局面。
判定规则(从终局往回推):
- 终局(无法再走)是必败态(该走的人已经输了);
- 一个局面是必胜态,当且仅当存在一种走法能走到必败态(把烂摊子甩给对手);
- 一个局面是必败态,当且仅当所有走法都只能走到必胜态(怎么走都把好局面送给对手)。
直观理解 · 动手试试
这套"P 态 / N 态"的语言,是分析一切公平组合游戏的通用框架。它的逻辑像多米诺一样从终点倒推:终局是必败态;谁能一步踏进必败态,谁就处在必胜态;而四面被必胜态包围、无处可逃的,就是必败态。
求解一个新游戏,标准做法就是从小规模局面开始,逐个标注 P 或 N,直到看出规律。巴什博弈里" 的倍数是必败态"正是这样推出来的——你会发现必败态往往呈现出漂亮的周期或代数模式。
必胜 / 必败态
标注每个石子数的胜负态(每次取 1 ~ 2)
0
P
1
N
2
N
3
P
4
N
5
N
6
P
7
N
8
N
9
P
10
N
11
N
12
P
13
N
14
N
15
P
16
N
P(必败态)= 红色,出现在 3 的倍数处; N(必胜态)= 绿色。规律周期为 3。
2
从 n=0(必败)往右推:能一步走到红色 P 的就是绿色 N。必败态恰好落在 m+1 的倍数上。
游戏: 颗石子,每次取 或 颗,取完者胜。标注 的胜负态。
▸查看解答步骤
答: P 态为 3 的倍数
某游戏中,局面 的所有走法分别到达局面 ,其中 是必败态。 是必胜还是必败?
▸查看解答步骤
答: N 态(必胜)
即时练习
一个局面是必胜态,当且仅当?
存在一种走法到达必败态所有走法都到达必败态存在一种走法到达必胜态无法再走能把对手逼入必败态即为必胜态:存在一步走到 P 态。
终局(无法再走的局面)对该走的人来说是必败态。
轮到他时已无法行动,按"取完者胜"的规则他已输。
每次取 或 颗的取石子游戏中, 到 里的必败态(3 的倍数)有 。其中最大的是?
必败态为 的倍数:,最大为 。
一个局面所有走法都通向必胜态,它是?
必败态必胜态终局无法判断无论怎么走都把必胜态送给对手,自己就是必败态。
易错点
- P/N 的视角搞反。 P/N 都是针对"轮到走的人"而言:P 态 = 该走的人必败。
- 必败态判定写成"存在"。 必败态要求所有走法都到必胜态;必胜态才是"存在"一步到必败态。
- 忘了从终局倒推。 必须先定下终局的胜负,再逐步往回标注。