py_practice_3

自分用 公開下書き

31game とは何か

2022年9月24日~25日の 📺 Mathpower で取り上げられたゲーム

固く説明すると、 📖 21game の 21 を 31 にしたもの

ゲームのジャンルは 📖 Nim(二ム)
Nim のジャンルは 📖 不偏ゲーム

31game は細かく言うと、

の2種類ある。あとで説明する

Mathpower のタコ部屋の人たちは、広く知られた 31ゲーム ではなく、バリアント(変則ルール,ローカルルール)の方で調べている

Nim とは何か

(例:マッチ棒,碁石,etc)が、(例:机,床,etc)に1個以上あるとする。
プレイヤー は2人とする

先行プレイヤーが物を1つ以上取り除く。
後攻プレイヤーも物を1つ以上取り除く。
物の最後の1個を取らされた方が 負け(『ミゼールルール』と呼ぶ)

👇 バリアント(変則ルール,ローカルルール)が いくつも考えられる

  • 最後の1個を取った方が 勝ち(何が通常なのか分からないが『通常のルール』と呼ぶ)
  • 物の個数を制限する
  • 1度に取れる物の数を制限する
  • 物を複数の (ヒープ,Heap) に分ける

ミゼールゲームとは何か

Nim で、敗者が1人決まったところで終わるもの

「普通のルール」とは何か

Nim で、勝者が1人決まったところで終わるもの

タコ部屋で調べている 31game のバリアントルール(ローカルルール)は?

📄 二日間通し企画 ~31ゲームに潜む未解決問題に挑戦!~ MATH POWER 2022 9/24-9/25
の中の、 31ゲームの仲間 ~制限石取りゲーム~ の、さらにルールを拡張した サブトラクションゲーム を調べている

  • 「普通のルール」とする
  • 石を取っていく
  • 最初の石の個数は可変
  • 取れる石の数は「1,2,3」から選ぶだけでなく、「1,3,5」など色々なパターンを調べている

サブトラクションゲームとは

よくあるルールでは、取れる石の数は「1,2,3」の3つの内から選べるが、
この「1,2,3」のことを サブトラクションセット と呼んで、 S = { 1, 2, 3 } のように書く

ここで、 S の内容を { 1, 3, 5 } でも { 2, 4, 6, 8 } でも、好きな非負整数を入れて作ってもいい、としたものを
サブトラクションゲーム と呼ぶ

1 が入ってないと 山の石に取れない余りが出ることがあるが、その場合は、取れなかった人の負けとする

除去可能数 とは

例えば S = { 1, 2, 4 } のとき、 S の要素、つまり 1 とか 2 とか 4 のことを 除去可能数 と呼ぶ。
つまり 取る石の数 のことだ

用語説明

mex

📖 mex ,最小除外数 (minimum exclusion)

(1) 非負整数をいくつか選んで、 T とする。例えば T は 0, 1, 2, 3 とする
(2) T に含まれない非負整数のうち、最小のものを mex T と呼ぶ。この例では mex T は 4

練習

  • T が 1, 2, 3 のとき、 mex T は 0
  • T が 0, 1, 3 のとき、 mex T は 2

グランディ数

非負整数。
グランディ数とは何か、その求め方についてはあとで説明する。
特に略語はないので プログラミング中の変数名では grundy といった名前を付けるかもしれない

📖 グランディ数

グランディ数と必勝戦略

  • 手番を持つ方(これから石を取る方)に、グランディ数が 非0の局面 が回ってきたら、手番を持つ方が手を抜かない(勝つ手を選び続ける)限り 必勝だ。
  • 手番を持つ方に、グランディ数が 0の局面 が回ってきたら、相手(Opponent)が手を抜かない限り 必敗だ。
  • 相手に、グランディ数が 非0の局面 を回したら、相手が手を抜かない限り 手番を持つ方は必敗だ。
  • 相手に、グランディ数が 0の局面 を回したら、手番を持つ方が手を抜かない限り 必勝だ

つまり、両者に、グランディ数を計算する能力があり、手を抜かなければ、対局開始時点で グランディ数を確認すれば、勝敗は決定している

  • ただし、この法則は、千日手の有るゲームを想定していない

ここで、必勝戦略は以下のようになる

  • 自分に グランディ数 非0 の局面が回ってきたら、相手に常に グランディ数 0 の局面を回す
  • 自分に グランディ数 0 の局面が回ってきたら、相手が必勝手順から外れることを期待して 粘る

グランディ数の説明

S={1,2,3} のゲームのときの、グランディ数について説明する

手番から見た机の上
┌───────┐
│       │
│       │
│       │
└───────┘
石の数が 0 個のとき、グランディ数は 0
手番なら: 負けている
相手なら: さっきの自分の手番で勝った
手番から見た机の上
┌───────┐
│       │
│    o  │
│       │
└───────┘
石の数が 1 個のとき、グランディ数は 1
手番なら: 1つ取って勝ち
相手なら: 回ってこない。負け
手番から見た机の上
┌───────┐
│       │
│  o o  │
│       │
└───────┘
石の数が 2 個のとき、グランディ数は 2
手番なら: 自分が手を抜かなければ、2つ取って勝ち
相手なら: 手番を持つ方が手を抜かなければ、回ってこない。負け
手番から見た机の上
┌───────┐
│       │
│  o o  │
│   o   │
└───────┘
石の数が 3 個のとき、グランディ数は 3
手番なら: 自分が手を抜かなければ、3つ取って勝ち
相手なら: 手番を持つ方が手を抜かなければ、回ってこない。負け
手番から見た机の上
┌───────┐
│   o   │
│  o o  │
│   o   │
└───────┘
石の数が 4 個のとき、グランディ数は 0
手番なら: どう石を取っても、石が残る。相手が手を抜かなければ負け
相手なら: 手番を持つ方が石をどう残しても、全部取る方法あり。自分が手を抜かなければ自分の勝ち
手番から見た机の上
┌───────┐
│   o   │
│  o o  │
│   o o │
└───────┘
石の数が 5 個のとき、グランディ数は 1
手番なら: 石を2つか3つ取れば、机の上に石が4つ残るということはない。以降、自分が手を抜かなければ勝ち
相手なら: 手番を持つ方が石を1つだけ取るでもなければ、机の上に石が4つ残るということはない。手番を持つ方が手を抜かなければ負け
手番から見た机の上
┌───────┐
│   o   │
│  o o  │
│ o o o │
└───────┘
石の数が 6 個のとき、グランディ数は 2
手番なら: 石を1つか3つ取れば、机の上に石が4つ残るということはない。以降、自分が手を抜かなければ勝ち
相手なら: 手番を持つ方が石を2つ取るでもなければ、机の上に石が4つ残るということはない。手番を持つ方が手を抜かなければ負け
手番から見た机の上
┌───────┐
│   o o │
│  o o  │
│ o o o │
└───────┘
石の数が 7 個のとき、グランディ数は 3
手番なら: 石を1つか2つ取れば、机の上に石が4つ残るということはない。以降、自分が手を抜かなければ勝ち
相手なら: 手番を持つ方が石を3つ取るでもなければ、机の上に石が4つ残るということはない。手番を持つ方が手を抜かなければ負け
手番から見た机の上
┌───────┐
│ o o o │
│  o o  │
│ o o o │
└───────┘
石の数が 8 個のとき、グランディ数は 0
手番なら: どう石を取っても、5つ~7つの石が残る。相手には残りの石の数を4つにする方法がある。相手が手を抜かなければ負け
相手なら: 手番を持つ方が石をどう残しても、自分には残りの石の数を4つにする方法あり。自分が手を抜かなければ自分の勝ち

以下は、表にしたものだ

残りの石の数 0 1 2 3 4 5 6 7
グランディ数 0 1 2 3 0 1 2 3

サブトラクションセットと、残りの石の数 に対して、対応するグランディ数は決まる

グランディ数の求め方

まず用語を説明する

  • 非負整数 とは、 0, 1, 2, 3, 4, ... のように増えていく数列に含まれる数を言う

  • 遷移 (せんい,Transition) とは、ここでは、 今、目の前に残っている石 から、いくつか石を取ったら 石を取った残りの石 に変わった、というような意味だ

👇 例えば以下のとき

手番を持つ方から見た机の上
┌───────┐
│   o   │
│  o o  │
│ o o o │
└───────┘
石の数が6個

S = { 1, 2, 3 } のゲームでは、遷移先は3つある(位置ではなく、個数だけに注目)

↓ 石を1つ取った   ↓ 石を2つ取った  ↓ 石を3つ取った

┌───────┐        ┌───────┐        ┌───────┐
│   o   │        │   o   │        │       │
│  o o  │        │  o o  │        │  o o  │
│ o o   │        │   o   │        │   o   │
└───────┘        └───────┘        └───────┘
石の数が5個       石の数が4個      石の数が3個

👇 遷移をまとめるとグラフになる。次に示す

                                                                                先3                                          ┌─────┐
                                                                                後3 -----------------------------------┬---> │ 1個 │
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │ 7個 │ 後3 ------------------------------------┬---> │ 4個 │ 先2                                     │         先1
│ 8個 │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │ 6個 │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                                  │                |                │            後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │ 3個 │ 先3    │                          │ 0個 │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │
                                          後1 ----┤           先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │ 5個 │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │                  │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │ 2個 │ 後2────┘
                                                                                                             └─────┘

次に グランディ数の求め方を示す

👇 まず、石が0個の局面(★)のグランディ数を 0 とする

                                                                                先3                                          ┌─────┐
                                                                                後3 -----------------------------------┬---> │     │
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │     │ 後3 ------------------------------------┬---> │     │ 先2                                     │         先1
│     │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │     │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                                  │                |                │            後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │     │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │        ★
                                          後1 ----┤           先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │     │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │                  │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │     │ 後2────┘
                                                                                                             └─────┘

👇 石が1個の局面(★)は、非負整数から、隣接する遷移先(◆)のグランディ数を除外し、残った非負整数の最小の数を入れる

                                                                                先3                                          ┌─────┐
                                                                                後3 -----------------------------------┬---> │  1  │ ★
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │     │ 後3 ------------------------------------┬---> │     │ 先2                                     │         先1
│     │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │     │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                                  │                |                │            後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │     │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │         ◆
                                          後1 ----┤           先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │     │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │                  │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │     │ 後2────┘
                                                                                                             └─────┘

👇 石が2個の局面(★)は、非負整数から、隣接する遷移先(◆)のグランディ数を除外し、残った非負整数の最小の数を入れる

                                                                                先3                                          ┌─────┐
                                                                                後3 -----------------------------------┬---> │  1  │ ◆
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │     │ 後3 ------------------------------------┬---> │     │ 先2                                     │         先1
│     │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │     │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                                  │                |                │            後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │     │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │         ◆
                                          後1 ----┤           先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │     │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │      ★           │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │  2  │ 後2────┘
                                                                                                             └─────┘

👇 石が3個の局面(★)は、非負整数から、隣接する遷移先(◆)のグランディ数を除外し、残った非負整数の最小の数を入れる

                                                                                先3                                          ┌─────┐
                                                                                後3 -----------------------------------┬---> │  1  │ ◆
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │     │ 後3 ------------------------------------┬---> │     │ 先2                                     │         先1
│     │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │     │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                                  │                |                │      ★    後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │  3  │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │         ◆
                                          後1 ----┤           先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │     │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │      ◆           │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │  2  │ 後2────┘
                                                                                                             └─────┘

👇 石が4個の局面(★)は、非負整数から、隣接する遷移先(◆)のグランディ数を除外し、残った非負整数の最小の数を入れる

                                                                                先3                                          ┌─────┐
                                                                          ★    後3 -----------------------------------┬---> │  1  │ ◆
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │     │ 後3 ------------------------------------┬---> │  0  │ 先2                                     │         先1
│     │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │     │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                                  │                |                │      ◆    後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │  3  │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │
                                          後1 ----┤           先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │     │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │      ◆           │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │  2  │ 後2────┘
                                                                                                             └─────┘

👇 石が5個の局面(★)は、非負整数から、隣接する遷移先(◆)のグランディ数を除外し、残った非負整数の最小の数を入れる

                                                                                先3                                          ┌─────┐
                                                                          ◆     後3 -----------------------------------┬---> │  1  │
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │     │ 後3 ------------------------------------┬---> │  0  │ 先2                                     │         先1
│     │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │     │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                                  │                |                │      ◆    後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │  3  │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │
                                          後1 ----┤      ★   先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │  1  │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │      ◆           │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │  2  │ 後2────┘
                                                                                                             └─────┘

👇 石が6個の局面(★)は、非負整数から、隣接する遷移先(◆)のグランディ数を除外し、残った非負整数の最小の数を入れる

                                                                                先3                                          ┌─────┐
                                                                          ◆     後3 -----------------------------------┬---> │  1  │
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │     │ 後3 ------------------------------------┬---> │  0  │ 先2                                     │         先1
│     │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │  2  │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                     ★           │                |                │       ◆    後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │  3  │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │
                                          後1 ----┤      ◆    先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │  1  │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │                   │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │  2  │ 後2────┘
                                                                                                             └─────┘

👇 石が7個の局面(★)は、非負整数から、隣接する遷移先(◆)のグランディ数を除外し、残った非負整数の最小の数を入れる

                                                                                先3                                          ┌─────┐
                     ★                                                   ◆     後3 -----------------------------------┬---> │  1  │
                  ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │  3  │ 後3 ------------------------------------┬---> │  0  │ 先2                                     │         先1
│     │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │  2  │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                     ◆            │                |                │            後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │  3  │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │
                                          後1 ----┤      ◆    先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │  1  │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │                   │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │  2  │ 後2────┘
                                                                                                             └─────┘

👇 石が8個の局面(★)は、非負整数から、隣接する遷移先(◆)のグランディ数を除外し、残った非負整数の最小の数を入れる

                                                                                先3                                          ┌─────┐
                     ◆                                                          後3 -----------------------------------┬---> │  1  │
   ★             ┌─────┐                                              ┌─────┐                                         │     └─────┘
┌─────┐  先1 -->  │  3  │ 後3 ------------------------------------┬---> │  0  │ 先2                                     │         先1
│  0  │           └─────┘ 後2 --------------------┐               │     └─────┘ 後2 ─────────────────────┐              │        後1
└─────┘                   後1 ---> ┌─────┐        │               │                                     │               │         │
         先2 --------------------> │  2  │ 先2     │               │           先1                       │              │          │
                                   └─────┘ 後2--- │ --------------┘            後1---┐           先2     │              │          │
                                     ◆            │                |                │            後2 -- │ --------------┘         ↓
                                           先3    │                |                │    ┌─────┐        │               │         ┌─────┐
                                           後3--- │ ---------------------------------┬-> │  3  │ 先3    │                          │ 0  │
                                                  │                |                 |   └─────┘ 後3 -- │ ─────────────────┼────> └─────┘
                                          先1     │                |                 |                  │                  │
                                          後1 ----┤      ◆    先1  |                 |          先1     │               │   │
                                                  │   ┌─────┐ 後1--┘                 |          後1 ----┤               │   │
         先3 -------------------------------------┴-> │  1  │                        |                  │               │   │
                                                      └─────┘ 先2                    |                  │            先1│   │
                                                              後2--------------------┘                  │            後1┘   │
                                                                                                        │                   │
                                                              先3                                       │    ┌─────┐ 先2    │
                                                              後3---------------------------------------┴--> │  2  │ 後2────┘
                                                                                                             └─────┘

以下同様

グランディ数を実装するには

グランディ数の集合 Grundy の要素は、 0 ~ len(S) だけあればよいことがわかる。
例えば S = { 1, 2, 5 } なら、 Grundy = { 0, 1, 2, 3 } でカバーできる

例2. S = { 1, 20, 300, 4000, 50000 } なら、 Grundy = { 0, 1, 2, 3, 4, 5 }

mex() という関数は 非負整数 を扱うが、非負整数は無限にある。 プログラミングで使う分には Grundy 集合で十分だ


山の石の数の集合を N と呼ぶとし、N 集合の長さ len(N) が 6 のとき、 N = { 1, 2, 3, 4, 5, 6 } とする

ただ、プログラミングでは、石の数が 0 の場合も扱えた方が便利だから、ゼロを含んでいるという意味で Nz とでも造語し、
Nz = { 0, 1, 2, 3, 4, 5, 6 } を作って使うことも あるかもしれない

Nz はちょうど、石が置いていない局面も含んだ、すべてのゲームの局面(その石の個数)にあたる


遷移先のグランディ数の集合を T と呼ぶとする。その要素のグランディ数は t とでも呼ぶことにする
さきほどのグラフを使った説明は、 T 集合を生成(追加、削除)する説明だ

例を追ってみよう

NzT も配列とする。
T集合生成アルゴリズムが始まる前は T = [] だ。
Nz 配列の添え字を i とし、0 から始まるとする。

Nz[i] (i は 0)の局面では mex(T) を呼び出すことで t値 0 が算出され、 T = [ 0 ] となる。
Nz[i] (i は 1)の局面では mex(T) を呼び出すことで t値 1 が算出され、 T = [ 0, 1 ] となる。
Nz[i] (i は 2)の局面では mex(T) を呼び出すことで t値 2 が算出され、 T = [ 0, 1, 2 ] となる。
Nz[i] (i は 3)の局面では mex(T) を呼び出すことで t値 3 が算出されるが、
ここで Nz の [0] はもう隣接していないことから t値 0 が除去され、 T = [ 1, 2, 3 ] となる

以下繰り返し

局面に対応付くグランディ数の配列 GrundyNz があるとし、添え字は i とする。 ( 0
内容は、算出した t値 が入っているとする

隣接している局面のグランディ数がいくつかは、 S 集合の要素が距離になっているから、 S = { s1, s2, s3 } (s1 < s2 < s3)とでも表すとすると、
GrundyNz[ i - s3 ]
GrundyNz[ i - s2 ]
GrundyNz[ i - s1 ]
で取ってこれる。配列の範囲外アクセスはしないように注意


tail length (尻尾の長さ)

1 2 3 4 5 6 4 5 6 4 5 6 ...

という数があり、 4 5 6 で循環しているとき、
循環に入る前の 1 2 3 の部分が尻尾で、その要素数 3 が tail length

関連する記事

📖 o31game - 遊んで覚えるPythonプログラム
📖 グランディ数列の探索プログラム - Ackvy さんの電卓

EOF

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事