せまゲー生半可集（２６）～Phutball（哲学者サッカー）続

前回の記事はこちら。

続きになります。

チャンス

去年の１２月にAdventarで「アブストラクトゲーム Advent Calendar 2023」を立ち上げて、こんな記事を書きました。

組合せゲーム理論の論文を集めた『Game of No Chance』の紹介です。
なんとか５冊分入手（PDFのダウンロード）しまして、ざっと眺めてみると『Phutball』に関する論文がいくつかありました。

シリーズ２冊目の『More Game of No Chance』に２本あります。

・「Phutball Endgames Are Hard」（詰みの判断はNP困難）

【引用】
Abstract. We show that, in John Conway’s board game Phutball (or Philosopher’s Football), it is NP-complete to determine whether the current
player has a move that immediately wins the game. In contrast, the similar
problems of determining whether there is an immediately winning move in
checkers, or a move that kings a man, are both solvable in polynomial time.

概要：ジョン・コンウェイのボードゲーム Phutball (または Philosopher's Football) では、プレイヤーがゲームに即座に勝つ動き（詰め）を持っているかどうかを判断することが NP 完全であることを⽰します。対照的に、チェッカーで即座に勝つ動き（詰め）があるかどうか、または駒をキングする動き（昇格＝プロモート）があるかどうかを判断する同様の問題は、どちらも多項式時間で解決できます。

ざっくり言えば、でかい盤面での必勝法は先手なのか後手なのかは簡単にはわかりません、です。
ある程度の大きさ（小さいサイズ）であれば、例示をしてみるとわかりますが。

小さい盤面の例（左：５×５　右：７×７）。
どちらも先手必勝。

・One-Dimensional Phutball（一次元哲学者サッカー）

【引用】
Abstract. We consider the game of one-dimensional phutball. We solve
the case of a restricted version called Oddish Phutball by presenting an
explicit strategy in terms of a potential function.

概要：1次元のphutballゲームを考える。Oddish Phutballと呼ばれる制限版の場合、潜在的な機能の観点からの明⽰的な戦略。

雑に説明すると、上と下しかボールが移動しない『Phutball』です。
この論文で、１次元にすると、千日手（手順を進めると以前の盤面の配置に辿り着いて勝敗がつかない）があることがわかります。

千日手

シリーズ５冊目（最新）の『Game of No Chance 5』に１本。

・Phutball draws（引き分けになるよ）

【引用】
In this short note, we exhibit a draw in the game of Philosopher’s Phutball. We construct a position on a 12×10 Phutball board from where either player has a drawing strategy, and then generalize it to an m ×n board with m −2 ≥ n ≥ 10.

拙稿では、Philosopher's Phutball のゲームで引き分けがあることを⽰します。12 ×10 のPhutball ボード上で、引き分け戦略を持つ（千日手となる）ポジションが構築できることを示し、それをm ×nボード（m −2 ≥ n ≥ 10 の条件付き）に⼀般化します。

引用：『Game of No Chance 5』P443

上の図が、12×10の盤面で千日手になるパターンです。
ざっくりと手順を追ってみます（上のゴールが先手、下のゴールが後手）。

手番は後手（下がゴール）とします。
左図が最初の配置となります。
すでに、先手がゴールするルートがあります（矢印を追っていく）。
なので後手は、中図のように黄色の位置にコマを置きます。
ゴールを阻止するだけでなく、後手がゴールするルートが出来上がります（矢印を追っていく）。
互いに、阻止とゴールルートの構築の繰り返しあいで、斜めにコマが置かれていき、右図になります。
右図のときは先手番となるのですが、赤の矢印にボールを動かさないとなりません（さもないと、後手が水色の位置にコマを置くと、後手の勝ちが確定（青の矢印）します）。

ボールを動かすと、

となりますが、後手は当然というかゴールを狙いますので、

と、最初の配置と上下逆転し、今度は先手番となります。

『Phutball』の場合も、上の配置にならい以下の図のようにすると千日手の配置となります。

Phatballの盤面は19×15のサイズですが、
実質16×14のサイズにおさめています。

下の図のように、先手（上：黃）後手（下：橙）と駒を置きます。

このあと先手は、今まで斜めに置いた駒を一気にまたいで球を動かし、
天地逆転の配置になります。

締め

ということで『Phutball』の紹介の続きでした。
次回も、もう一回やろうかと目論んでおります。

では。