好玩儿的Game

时间:2024-01-04 16:19:14

1. 种类:

  威佐夫游戏, Bash游戏, Nim游戏, 等.

2. 理论:

  胜态一定可以通过某种策略走向必败态; 而必败态采取任何策略都将走向胜态. 用图论的话来说, 因为必败态只能走向胜态, 所以任何两个必败态结点之间不可能存在边; 因为胜态总能走到必败态, 所以对任何一个非必败态的结点, 一定存在一个从它指向必败态结点的边.

  定义:有向图中,集合X中任意两点之间无边,称集合X为内固集.
  定义:有向图中,任意不在集合X中的点存在一条指向集合X的边,称集合X为外固集.
  定义:有向图中,集合X 既是外固集,又是内固集,称集合X为核.
  显然,内,外固集的定义正好针对上面的两句话,而核就是包含所有必败态的集合。

好玩儿的Game

Reference:

[1] http://www.bubuko.com/infodetail-806583.html

[2] 百度百科:威佐夫博弈