Language: C++

#include <iostream>
#include <vector>
using namespace std;

// DP テーブル
long long dp[3100][3100];

int main() {
    // 入力受け取り
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // 初期条件
    for (int i = 0; i < N; ++i) dp[i][i] = 0;

    // DP
    for (int len = 1; len <= N; ++len) {
        for (int i = 0; i + len <= N; ++i) {
            int j = i + len;

            // 先手番
            if ((N - len) % 2 == 0)
                dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1]);

            // 後手番
            else
                dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1]);
        }
    }

    // 答え
    cout << dp[0][N] << endl;
}
4. 後退解析： サイクルによる引き分けのあるゲーム
4-1. 後退解析の考え方
ここまで、ゲームの局面がサイクルしないものだけを考えて来ました。そのようなゲームではすべての局面について「勝ち」か「負け」かが決まります (得点差を競うゲームでは「引き分け」もありえます)。

一方、将棋のようにサイクルすると話が少しややこしくなります。そのようなゲームでは無限に同じことを繰り返してしまうことがないように

同一局面が kk 回あらわれたら引き分け
という規定を設けていることが多いです。これによって二人零和有限確定完全情報ゲームでいうところの「有限性」が担保されることとなります。ゲームの局面に「勝ち」と「負け」だけでなく「引き分け」が新たに加わりました。このようなゲームでは後退解析と呼ばれる手法が有効です6。

アイディアはとてもシンプルで今までは

相手に「負け」の局面を渡せるような手を選べる局面は「勝ち」
どの手を選んでも相手に「勝ち」の局面を渡してしまうような局面は「負け」
としていましたが、これに

そのどちらでもない局面は「引き分け」
とするだけです！！！！！！！！
順を追って見てみます。以下のような局面遷移図をもつゲームを考えてみましょう。まず「次に遷移するところのない頂点」は「負け」が確定しているので「×」を描いています。



まず「×」へと進める局面は「○」が確定して...



行き先がすべて「○」になっている局面は「×」が確定して... (このとき、行き先の中に「○」か「×」かわからないようなものがある場合は放置します)



この調子で続けていくと、以下のようになります。



ここで残った頂点はいずれも

そこから「×」には行けない
行き先の中に「残った頂点」がある
という性質をもっています。残った頂点は実は「引き分け」になります。なぜなら、「残った頂点」から移動できるのは「○」か「残った頂点」のどちらかですが、「○」に移動すると相手が勝ってしまうため「残った頂点」へと移動させることになります。

相手も同じことを行うため、「残った頂点」から「残った頂点」への移動を繰り返しているうちは負けることはありません。一方そうすると、「残った頂点」から「×」へ移動させるようなことは、永遠にできないことがわかります。

よって永遠に「残った頂点」から「残った頂点」への移動を繰り返すことになります。勝てないですが負けない戦略です。将棋の場合は同一局面が 44 回登場したら千日手 (引き分け) になります。



このような「残った頂点」の勝敗に関する取り扱いに関しては、ゲームによって様々でしょう。

4-2. 後退解析の実装
後退解析の実装には std::queue を使うと簡明です。ここで各頂点 vv から出ている辺の本数のことを、頂点 vv の出次数とよび、deg[v]deg[v] と表すこととします。また

dp[v]=1dp[v]=1 (勝ち)、00 (負け)、−1−1 (未確定)
とします。このとき、キューを用いて後退解析は以下のように実装できるでしょう。

Q をキューとする
dp テーブル全体を -1 に初期化する
for each 各ノード v do
    if deg[v] == 0 then
        dp[v] = 0
        v を Q に push

while Q が空ではない do
    Q からノード v を pop して取り出す
    for each v を終点とする辺 e とその始点のノード nv do
        if nv はすでに訪れたノード then
            continue
        辺 e をグラフから削除 (実装上は deg[nv] の値を減らせば OK)
        if dp[v] = 0 then
            dp[nv] = 1
            nv を Q に push
        else if dp[v] = 1 then
            if deg[nv] = 0 then (辺を削除して行ったことで出次数が 0 になったら負けノード確定です)
                dp[nv] = 0
                nv を Q に push
グラフを葉から順番に削り落としていくイメージですね。葉を削ることでまた新たな葉が生まれ、それを削ることでまた新たな葉が生まれ...を繰り返していく感じです。実際にはグラフから辺を削除するのを愚直に実装するのではなく、各頂点 vv の出次数 deg[v]deg[v] を減らしていけばいいです。

4-3. 後退解析の使い所
後退解析がゲーム解析に有効に用いられた例として、どうぶつしょうぎがあります。
小さな子供たちや初心者にも楽しめるようにしたにミニ将棋ですね。通常の将棋と同様、同一局面の繰り返しがあるので、後退解析的な処理が必要になります。具体的な解析の様子を記述した論文があります:

田中哲郎: 「どうぶつしょうぎ」の完全解析
どうぶつしょうぎに関する有用の知見も含まれていて、とても面白いです (下図は論文より引用)。

どうぶつしょうぎ.png

また、後退解析的な queue の使い方はゲームの解析のみならず、様々な有向グラフの解析に有効なケースも多々あります。プログラミングコンテストにおいても以下のような出題例があります:

キューを用いたトポロジカルソート
AOJ 2891 な◯りカット (AUPC 2018 day3 C)
AtCoder AGC 027 C - ABland Yard
AtCoder ARC 038 D - 有向グラフと数
Codeforces Manthan Codefest 18 E - Trips
次節で、このうちの「AtCoder ARC 038 D - 有向グラフと数」を解いてみます。

例題 4. AtCoder ARC 038 D - 有向グラフと数
後退解析を用いる例題を解いてみます。少し難しめです。

問題概要
NN 頂点 MM 辺の有向グラフが与えられる。各頂点 vv には値 XvXv が割り振られている。先手と後手とで以下の対戦を行う

スタート時には駒を頂点 11 に置く
各プレイヤーは各ターンにおいて
駒をどこかに移動させる (グラフの辺に沿って)
ゲームを終了宣言する
双方ともに終了宣言しないまま後手が 109109 回目のプレイをしたならばその時点でゲームは強制終了する
ゲームを終了宣言された時点での駒の置いてあるノードの値 XX がこのゲームにおける得点となる。先手は得点を最大化したくて、後手は得点を最小化したい。双方最善を尽くしたときの得点を求めよ。

入力ケースの制約
1≤N≤1051≤N≤105
1≤M≤2×1051≤M≤2×105
解法
判定問題にして解くことを考えます。つまり

与えられた値 DD に対して、得点が DD 以上で終えることができるか

という問題を考えます。DD 以上にできるならば先手勝ち、できないならば後手勝ちということになります。そしてこの答えが Yes となるような DD の値の最大値を二分探索で求めます。それがこの問題の答えです。

さて、まずはこのゲームのグラフがどのようになるかですが、

駒がどのノードにあるか
先手番か後手番か
に応じて 2N2N 個の局面があることがわかります (NN 個として扱う方法もあるようです)。ここでは

先手がノード ii (i=0,1,…,N−1i=0,1,…,N−1) にいる状態: ii
後手がノード ii (i=0,1,…,N−1i=0,1,…,N−1) にいる状態: i+Ni+N
で表すことにします。また v=0,1,…,2N−1v=0,1,…,2N−1 に対して

dp[v]dp[v] = ノード vv の状態でその手番の人が勝つときは 11、負けるときは 00、未確定は −1−1
とします。まずゲームの勝敗が予め明らかな部分を列挙します。

値 XvXv が DD 以上で先手番: そのまま「先手勝ち」で dp[v]=1dp[v]=1 です
値 XvXv が DD 未満で先手番で deg[v]=0deg[v]=0: 「先手負け」で dp[v]=0dp[v]=0 です
値 XvXv が DD 未満で後手番: そのまま「後手勝ち」で dp[v]=1dp[v]=1 です
値 XvXv が DD 以上で後手番で deg[v]=0deg[v]=0: 「後手負け」で dp[v]=0dp[v]=0 です
そしてここから後退解析をして行きます。なお退解析を終えたとき、「引き分け」ノードの扱いについては、109109 回後の後手の移動の直後にゲーム強制終了となることから結果として後手勝ちになります。

ARC_038_D
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// グラフの頂点数、辺数、各ノードの重み
int N, M;
vector<int> X;

// ゲームグラフ (後退解析のために辺の向きを逆にする)
vector<vector<int> > G;
vector<int> deg; // ゲームグラフにおける出次数 (辺の向きを逆にした状態で入次数)

// 二分探索判定 (D 以上にできるかどうか)
bool judge(int D) {
    vector<int> cdeg = deg;
    queue<int> que; // キュー
    vector<int> dp(N * 2, -1); // 最初は全体を -1 で初期化

    // 初期条件
    for (int i = 0; i < N; ++i) {
        if (X[i] >= D) {
            dp[i] = 1; // 先手勝ち
            que.push(i);

            if (cdeg[i] == 0) {
                dp[i + N] = 0; // 後手負け
                que.push(i + N);
            }
        }
        else {
            dp[i + N] = 1; // 後手勝ち
            que.push(i + N);

            if (cdeg[i] == 0) {
                dp[i] = 0; // 先手負け
                que.push(i);
            }
        }
    }   

    // 後退解析 (ここは自動的に書ける)
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
             // すでに見た頂点はスルー
            if (dp[nv] != -1) continue;

            --cdeg[nv]; // 辺 (nv, v) を削除
            if (dp[v] == 0) {
                dp[nv] = 1;
                que.push(nv);
            }
            else if (dp[v] == 1) {
                if (cdeg[nv] == 0) {
                    dp[nv] = 0;
                    que.push(nv);
                }
            }
        }
    }

    // ノード 0 が先手番で勝ちかどうか
    return (dp[0] == 1);
}

int main() {
    // 入力
    cin >> N >> M;
    X.resize(N*2);
    for (int i = 0; i < N; ++i) cin >> X[i];
    for (int i = 0; i < N; ++i) X[i+N] = X[i];
    G.assign(N*2, vector<int>());
    deg.assign(N*2, 0);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[b + N].push_back(a); // 後手番での後退遷移
        G[b].push_back(a + N); // 先手番での後退遷移
        deg[a]++; deg[a + N]++;
    }

    // 二分探索
    int low = 0, high = 1000000007; // low: 絶対先手勝つ、high: 絶対先手負ける
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (!judge(mid)) high = mid;
        else low = mid;
    }
    cout << low << endl;
}
5. 発展的話題
今回の記事ではゲーム探索の考え方を紹介しましたが、組合せゲーム理論にはさらにずっと深淵な理論が続いています。その一端を簡単に紹介してみます。

5-1. α-β 探索法
例題 3. EDPC L 問題 - Deque にて、ゲーム探索の基本手法である min-max 法を紹介しましたが、これを高速化したものが α-β 探索法です。基本的には、min-max 法をベースにしていますが、

探索の必要がないことが確定した部分を枝刈りする

というアイディアを実現したものです。基本的には分枝限定法と同様の枝刈りを行っています。

5-2. Nim
石取りゲームの山が複数個になったバージョンを考えてみます。

山が NN 個あって、それぞれ初期状態で a1,a2,…,aNa1,a2,…,aN 個の石が積まれている
先手と後手は交互に、好きな山を一つ選んで、好きな個数の石を取り去る
先に石をとれなくなった方の負けです。先手と後手のどちらが勝つでしょうか？

これをゲーム探索のフレームワークで解こうとすると、ありうる局面数が

(a1+1)(a2+1)…(aN+1)(a1+1)(a2+1)…(aN+1)
となって大変なことになってしまいます。しかし実はこのゲームは数学的に鮮やかに解かれていて

a1XORa2XOR…XORaN=0a1XORa2XOR…XORaN=0 のとき、後手必勝
そうでないとき、先手必勝
であることが知られています。この答えさえ知っていれば、証明は意外と簡単なので是非チャレンジしてみてください。

5-3. Grundy 数
一見すると、Nim はすごく特殊なゲームに見えるかもしれません。複数山の石取りゲームという特殊な問題をたまたま鮮やかに解けただけに見えるかもしれません。しかし Nim の発想を多くのゲームに適用できるようにした理論があります。Grundy 数を学ぶと、Nim が組合せゲーム理論の基本をなす重要なゲームであることが実感できます。

興味のある方は是非「石取りゲームの数学」を読んでみてください。とても面白いです。

6. おわりに
ネットなどではしばしば「将棋に必勝法はあるのか」「将棋はいつか完全に解かれてしまうのではないか」といった議論を見かけます。実際は探索空間があまりにも膨大で、現在のところ完全解析の目処はまったく立っていない状態と言えます。しかし一方では「原理的には先手必勝か後手必勝か決まっているはず」と随所で言及されることについて、その原理を理解することは有益だと思います。

さて、基本的なゲーム探索手法の習得の後に続いていく世界としては、

ゲームに限らず、探索法そのものを深く深く追求していく世界
ゲームそのもののもつ構造を深く深く追求していく世界
とがあるでしょう。どちらもすごく面白そうです。

7. 参考資料
参考になる資料を挙げていきます。

各種ゲームの完全解析
各種ボードゲームを完全解析した旨の報告たちを挙げます:

[1] Janos Wagner and Istvan Virag: Solving renju, ICGA Journal, Vol.24, No.1, pp.30-35 (2001), http://www.sze.hu/~gtakacs/download/wagnervirag_2001.pdf

[2] Martin Muller, Robert Lake, Paul Lu, and Steve Suphen: Checkers is solved, Science Vol.317, No,5844, pp.1518-1522 (2007), http://www.sciencemag.org/content/317/5844/1518.full.pdf

[3] Joel Feinstein: Amenor Wins World 6x6 Championships!, Forty billion noted under the tree, pp.6-8, British OthelloFederation's newsletter., (1993), http://www.britishothello.org.uk/fbnall.pdf

[4] 清慎一, 川嶋俊: 探索プログラムによる四路盤囲碁の解, 研究報告ゲーム情報学(GI), Vol. 2000-GI-004, pp.69-76, 情報処理学会, (2000), http://id.nii.ac.jp/1001/00058633/

[5] Eric C.D. van der Welf, H.Jaap van den Herik, and Jos W.H.M.Uiterwijk: Solving Go on Small Boards, ICGA Journal, Vol.26, No.2, pp.92-107 (2003).

[6] 田中哲郎: 「どうぶつしょうぎ」の完全解析, 情報処理学会研究報告, Vol.2009-GI-22 No.3, pp.1-8, (2009), http://id.nii.ac.jp/1001/00062415/

[7] 塩田好, 石水隆, 山本博史: 「アンパンマンはじめてしょうぎ」の完全解析, 2013年度 情報処理学会関西支部 支部大会 講演論文集, (2013), http://id.nii.ac.jp/1001/00096792/

組合せゲーム理論の参考書
組合せゲーム理論を学ぶことのできる参考書たちです。

M.H.Albert, R.J.Nowakowski, D.Wolfe: 「組合せゲーム理論入門 －勝利の方程式－」
本格的な組合せゲーム理論の入門書です。

スクリーンショット 2019-01-15 12.20.47.png

佐藤文広: 石取りゲームの数学: ゲームと代数の不思議な関係
Nim や Grundy 数から始まる組合せゲーム理論の物語です。

スクリーンショット 2019-01-15 12.21.56.png

初期盤面の勝敗のみがわかることを超弱解決、初期盤面の勝敗がわかっていてそれを証明するのに必要な各局面の最善手もわかることを弱解決、すべての局面について勝敗も最善手もわかることを強解決と呼んで区別することもあります。 ↩

厳密には将棋というゲームは現在「勝ちか負けか引き分けかがルール上曖昧な局面」が存在することがわかっており (「最後の審判」を参照)、それが曖昧なままだと初期盤面において先手必勝かどうかは判断できないかもしれません。 ↩

基本定理の主張には「引き分け」を含むゲームについては含めないことも多いです。 ↩

石を残り 00 個にして相手に手番を回せば勝ちという理由から、これを「○」にする考え方もあります。どちらの考え方をしているのかを混乱しないようにすることが肝要です。 ↩

言い換えると、自分は X−YX−Yを最大にしたくて、相手は Y−XY−X を最大にしたいです。これらを合計すると 00 になっています。これが二人零和有限確定完全情報ゲームで言うところの「零和」の意味です。 ↩

今までのも解析も後退解析の一種ではあるのですが、特に引き分け局面も含む場合に後退解析と呼ぶことが多いです。 ↩

編集リクエスト
ストック
いいね
180
drken
けんちょん (Otsuki)
@drken
ntt-data-msi
NTTデータ数理システムでリサーチャーをしている大槻です。 機械学習やアルゴリズムに関して面白いと思ったことを記事にしていきたいと思います。記事へのリンク等についてはお気軽にしていただいて大丈夫です。よろしくお願いします。
http://www.msi.co.jp/
フォロー
ntt-data-msi
株式会社NTTデータ数理システム
数理科学とコンピュータサイエンスの融合！！
http://www.msi.co.jp/
ユーザー登録して、Qiitaをもっと便利に使ってみませんか。
あなたにマッチした記事をお届けします
ユーザーやタグをフォローすることで、あなたが興味を持つ技術分野の情報をまとめてキャッチアップできます
便利な情報をあとで効率的に読み返せます
気に入った記事を「ストック」することで、あとからすぐに検索できます
より詳しく
登録するログインする
0. ゲームを解くとは
すべての局面には答えがある
1. 二人零和有限確定完全情報ゲーム
2. ゲーム探索
2-1. ゲームのグラフ
2-2. ゲーム解析の例
例題 1. 石取りゲーム
石取りゲームのグラフの探索
3. 単純なゲーム探索の実装 〜 EDPC K, L 問題を題材に 〜
例題 2. EDPC K 問題 - Stones　〜 石取りゲームの一般化 〜
問題概要
入力ケースの制約
解法
例題 3. EDPC L 問題 - Deque　〜 得点差も最大化したい 〜
問題概要
入力ケースの制約
例
解法
4. 後退解析： サイクルによる引き分けのあるゲーム
4-1. 後退解析の考え方
4-2. 後退解析の実装
4-3. 後退解析の使い所
例題 4. AtCoder ARC 038 D - 有向グラフと数
問題概要
入力ケースの制約
解法
5. 発展的話題
5-1. α-β 探索法
5-2. Nim
5-3. Grundy 数
6. おわりに
7. 参考資料
各種ゲームの完全解析
組合せゲーム理論の参考書
コメント
あなたもコメントしてみませんか :)
ユーザ登録
すでにアカウントを持っている方はログイン
How developers code is here.
Qiita
About
利用規約
プライバシー
ガイドライン
API
ご意見
ヘルプ
広告掲載
Increments
About
採用情報
ブログ
Qiita Team
Qiita Jobs
Qiita Zine
© 2011-2019 Increments Inc.

Compiler output:
a.cc:37:1: error: extended character 、 is not valid in an identifier
   37 | ここまで、ゲームの局面がサイクルしないものだけを考えて来ました。そのようなゲームではすべての局面について「勝ち」か「負け」かが決まります (得点差を競うゲームでは「引き分け」もありえます)。
      | ^
a.cc:37:1: error: extended character 。 is not valid in an identifier
a.cc:37:1: error: extended character 「 is not valid in an identifier
a.cc:37:1: error: extended character 」 is not valid in an identifier
a.cc:37:1: error: extended character 「 is not valid in an identifier
a.cc:37:1: error: extended character 」 is not valid in an identifier
a.cc:37:139: error: extended character 「 is not valid in an identifier
   37 | ここまで、ゲームの局面がサイクルしないものだけを考えて来ました。そのようなゲームではすべての局面について「勝ち」か「負け」かが決まります (得点差を競うゲームでは「引き分け」もありえます)。
      |                                                                                                                                           ^
a.cc:37:139: error: extended character 」 is not valid in an identifier
a.cc:37:186: error: extended character 。 is not valid in an identifier
   37 | ここまで、ゲームの局面がサイクルしないものだけを考えて来ました。そのようなゲームではすべての局面について「勝ち」か「負け」かが決まります (得点差を競うゲームでは「引き分け」もありえます)。
      |                                                                                                                                                                                          ^
a.cc:39:1: error: extended character 、 is not valid in an identifier
   39 | 一方、将棋のようにサイクルすると話が少しややこしくなります。そのようなゲームでは無限に同じことを繰り返してしまうことがないように
      | ^
a.cc:39:1: error: extended character 。 is not valid in an identifier
a.cc:42:1: error: extended character 。 is not valid in an identifier
   42 | という規定を設けていることが多いです。これによって二人零和有限確定完全情報ゲームでいうところの「有限性」が担保されることとなります。ゲームの局面に「勝ち」と「負け」だけでなく「引き分け」が新たに加わりました。このようなゲームでは後退解析と呼ばれる手法が有効です6。
      | ^
a.cc:42:1: error: extended character 「 is not valid in an identifier
a.cc:42:1: error: extended character 」 is not valid in an identifier
a.cc:42:1: error: extended character 。 is not valid in an identifier
a.cc:42:1: error: extended character 「 is not valid in an identifier
a.cc:42:1: error: extended character 」 is not valid in an identifier
a.cc:42:1: error: extended character 「 is not valid in an identifier
a.cc:42:1: error: extended character 」 is not valid in an identifier
a.cc:42:1: error: extended character 「 is not valid in an identifier
a.cc:42:1: error: extended character 」 is not valid in an identifier
a.cc:42:1: error: extended character 。 is not valid in an identifier
a.cc:42:1: error: extended character 。 is not valid in an identifier
a.cc:46:1: error: extended character 「 is not valid in an identifier
   46 | 相手に「負け」の局面を渡せるような手を選べる局面は「勝ち」
      | ^
a.cc:46:1: error: extended character 」 is not valid in an identifier
a.cc:46:1: error: extended character 「 is not valid in an identifier
a.cc:46:1: error: extended character 」 is not valid in an identifier
a.cc:47:1: error: extended character 「 is not valid in an identifier
   47 | どの手を選んでも相手に「勝ち」の局面を渡してしまうような局面は「負け」
      | ^
a.cc:47:1: error: extended character 」 is not valid in an identifier
a.cc:47:1: error: extended character 「 is not valid in an identifier
a.cc:47:1: error: extended character 」 is not valid in an identifier
a.cc:48:1: error: extended character 、 is not valid in an identifier
   48 | としていましたが、これに
      | ^
a.cc:50:1: error: extended character 「 is not valid in an identifier
   50 | そのどちらでもない局面は「引き分け」
      | ^
a.cc:50:1: error: extended character 」 is not valid in an identifier
a.cc:52:1: error: extended character 。 is not valid in an identifier
   52 | 順を追って見てみます。以下のような局面遷移図をもつゲームを考えてみましょう。まず「次に遷移するところのない頂点」は「負け」が確定しているので「×」を描いています。
      | ^
a.cc:52:1: error: extended character 。 is not valid in an identifier
a.cc:52:1: error: extended character 「 is not valid in an identifier
a.cc:52:1: error: extended character 」 is not valid in an identifier
a.cc:52:1: error: extended character 「 is not valid in an identifier
a.cc:52:1: error: extended character 」 is not valid in an identifier
a.cc:52:1: error: extended character 「 is not valid in an identifier
a.cc:52:1: error: extended character × is not valid in an identifier
a.cc:52:1: error: extended character 」 is not valid in an identifier
a.cc:52:1: error: extended character 。 is not valid in an identifier
a.cc:56:1: error: extended character 「 is not valid in an identifier
   56 | まず「×」へと進める局面は「○」が確定して...
      | ^
a.cc:56:1: error: extended character × is not valid in an identifier
a.cc:56:1: error: extended character 」 is not valid in an identifier
a.cc:56:1: error: extended character 「 is not valid in an identifier
a.cc:56:1: error: extended character ○ is not valid in an identifier
a.cc:56:1: error: extended character 」 is not valid in an identifier
a.cc:60:1: error: extended character 「 is not valid in an identifier
   60 | 行き先がすべて「○」になっている局面は「×」が確定して... (このとき、行き先の中に「○」か「×」かわからないようなものがある場合は放置します)
      | ^
a.cc:60:1: error: extended character ○ is not valid in an identifier
a.cc:60:1: error: extended character 」 is not valid in an identifier
a.cc:60:1: error: extended character 「 is not valid in an identifier
a.cc:60:1: error: extended character × is not valid in an identifier
a.cc:60:1: error: extended character 」 is not valid in an identifier
a.cc:60:58: error: extended character 、 is not valid in an identifier
   60 | 行き先がすべて「○」になっている局面は「×」が確定して... (このとき、行き先の中に「○」か「×」かわからないようなものがある場合は放置します)
      |                                                          ^
a.cc:60:58: error: extended character 「 is not valid in an identifier
a.cc:60:58: error: extended character ○ is not valid in an identifier
a.cc:60:58: error: extended character 」 is not valid in an identifier
a.cc:60:58: error: extended character 「 is not valid in an identifier
a.cc:60:58: error: extended character × is not valid in an identifier
a.cc:60:58: error: extended character 」 is not valid in an identifier
a.cc:64:1: error: extended character 、 is not valid in an identifier
   64 | この調子で続けていくと、以下のようになります。
      | ^
a.cc:64:1: error: extended character 。 is not valid in an identifier
a.cc:70:1: error: extended character 「 is not valid in an identifier
   70 | そこから「×」には行けない
      | ^
a.cc:70:1: error: extended character × is not valid in an identifier
a.cc:70:1: error: extended character 」 is not valid in an identifier
a.cc:71:1: error: extended character 「 is not valid in an identifier
   71 | 行き先の中に「残った頂点」がある
      | ^
a.cc:71:1: error: extended character 」 is not valid in an identifier
a.cc:72:1: error: extended character 。 is not valid in an identifier
   72 | という性質をもっています。残った頂点は実は「引き分け」になります。なぜなら、「残った頂点」から移動できるのは「○」か「残った頂点」のどちらかですが、「○」に移動すると相手が勝ってしまうため「残った頂点」へと移動させることになります。
      | ^
a.cc:72:1: error: extended character 「 is not valid in an identifier
a.cc:72:1: error: extended character 」 is not valid in an identifier
a.cc:72:1: error: extended character 。 is not valid in an identifier
a.cc:72:1: error: extended character 、 is not valid in an identifier
a.cc:72:1: error: extended character 「 is not valid in an identifier
a.cc:72:1: error: extended character 」 is not valid in an identifier
a.cc:72:1: error: extended character 「 is not valid in an identifier
a.cc:72:1: error: extended character ○ is not valid in an identifier
a.cc:72:1: error: extended character 」 is not valid in an identifier
a.cc:72:1: error: extended character 「 is not valid in an identifier
a.cc:72:1: error: extended character 」 is not valid in an identifier
a.cc:72:1: error: extended character 、 is not valid in an identifier
a.cc:72:1: error: extended character 「 is not valid in an identifier
a.cc:72:1: error: extended character ○ is not valid in an identifier
a.cc:72:1: error: extended character 」 is not valid in an identifier
a.cc:72:1: error: extended character 「 is not valid in an identifier
a.cc:72:1: error: extended character 」 is not valid in an identifier
a.cc:72:1: error: extended character 。 is not valid in an identifier
a.cc:74:1: error: extended character 、 is not valid in an identifier
   74 | 相手も同じことを行うため、「残った頂点」から「残った頂点」への移動を繰り返しているうちは負けることはありません。一方そうすると、「残った頂