クアルトの引き分け盤面をPythonで考察してみた

# クアルトの引き分け盤面をPythonで考察してみた

## はじめに

クアルトは4×4の盤面に16個の異なる駒を並べ、縦・横・斜めのいずれかのラインに色や大きさ・形などの属性が一つでも揃えば勝利となるゲームです。  
今回は、「引き分けになる盤面は何通りあるのか？」を、数式的に近似しつつ、実際の駒の構造的制約を考慮しながら、Pythonを用いて考察してみました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3841466/4cae8aaf-e4b5-4cb4-b8d9-21878e11eae7.png)

---

## 1. クアルトの勝利条件と引き分けの定義

- 駒は4つの属性（高さ・色・形・穴）を持ち、それぞれ2値です。  
- 任意のライン（横・縦・斜め4マス）にて、いずれかの属性が全て揃うと勝利。  
- 引き分けとは、すべてのマスが埋まっているにも関わらず、どのライン（縦・横・斜め）にも共通属性が存在しない状態です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3841466/5a2c5c72-82e3-4ebd-8dd7-a9eb928d419e.png)


## 2. 数式的なアプローチ：1ラインの安全な並びを考える
駒が持っている4つの属性（高さ・色・形・穴）はそれぞれ
| 属性名 | 0 | 1 |
|--------|--------|--------------|
| 高さ      | 高     | 低            |
| 色      | 白      | 黒           |
| 形     | 四角      | 丸            |
| 穴      | 空いてる      | 空いていない            |

1ラインに対して、どの属性も4つ揃わない並び方を考えると：

| 0の数 | 1の数 | 組み合わせ数 |
|--------|--------|--------------|
| 1      | 3      | 4            |
| 2      | 2      | 6            |
| 3      | 1      | 4            |

→ 合計14通り
計算でも、全通りの 2×2×2×2 = 16 から、  
完全に一致する「0000」「1111」（すべての属性が一致する2通り）を除くと、  
**揃っていない組み合わせは 14通り**となります。

一ラインで、駒の置けるのが14通り
| ライン数（例） | 駒の残り数 | 組合せ                       |
| ------- | ----- | ------------------------- |
| 最初の1列目  | 16個全部 | C(16, 4)                  |
| 2列目     | 12個残る | C(12, 4)                  |
| 3列目     | 8個残る  | C(8, 2)                   |
| 4列目以降   | …     | C(6, 2), C(4, 2), C(2, 2) |

このように、1ラインごとに駒を選びながら、被りのないように安全な（非クアルト）並びを作っていきます。
ただし、盤面ではライン同士が交差するため、「すでに置かれている駒」は次のラインで**選ぶものではなく、使うもの（＝制約）**になります。
3列目以降は、すでにおかれている駒がラインで用いられるので4つ選ぶのではなく2つ使われることになります。このとき注意が必要なのは、**1つの駒が4つの属性すべてを持っているため、属性ごとに独立して考えることができない**という点です。

たとえば「属性ごとに14通り×4属性 = 56通り」としてしまうと、  
実際に存在しない駒の組み合わせや、物理的に不可能な盤面を数えてしまいます。

そのため、ここでは **1ライン全体として「どの属性も揃わないこと」だけを条件に**14通りとし、属性ごとの独立は仮定しません。
よって、理論的な最大安全ライン数（駒の組合せに対する）は以下の通り：
14 × (16C4 + 12C4 + 8C2 + 6C2 + 4C2 + 2C2)=33110
33110通り

## 3. 重複なしで4つの駒を選ぶと…
では、これをpythonを用いてパソコン上で仮想的に並べて確認します
Pythonで16個の駒から4つ選び、非勝利パターンを調べると、  
安全な組み合わせは **1,284通り** でした。

```python
from itertools import combinations, product

pieces = list(product([0, 1], repeat=4))

def is_quarto(combo):
    for i in range(4):
        values = [p[i] for p in combo]
        if all(v == 0 for v in values) or all(v == 1 for v in values):
            return True
    return False

valid_combos = [combo for combo in combinations(pieces, 4) if not is_quarto(combo)]
print(len(valid_combos))  # 1284
```

## 数式の見積もりとPythonによる厳密計算の違いについて

ここまでで、以下の2つの結果が出てきました。

- 数式的な見積もりによる非勝利ラインの組み合わせ数：**33,110通り**  
- Pythonで16個の駒から4つ選び、実際に非勝利パターンとなる組み合わせ数：**1,284通り**

この差はなぜ生じるのでしょうか？

### 数式の見積もり（33,110通り）の特徴

- 属性ごとに「14通りの非勝利パターン」があると仮定し、これを単純に掛け合わせた近似値です。  
- 駒の属性が独立していると仮定し、駒の重複や実際の存在制約をゆるく見積もっています。  
- つまり、**理論上の上限に近いざっくりした数**です。

### Pythonの厳密計算（1,284通り）の特徴

- 実際に16種類ある駒の中から4つを重複なく選び、  
- それらが「1つも属性が4つ揃わず勝利条件を満たさない」かを厳密に判定しています。  
- つまり、**駒の実体と複雑な属性の絡みを正確に反映した結果**です。

### なぜ差が大きいのか？

| ポイント             | 数式の見積もり               | Pythonの計算               |
|----------------------|-----------------------------|----------------------------|
| 属性の独立性         | 仮定している                 | 実際は複雑に絡み合っている |
| 駒の存在性           | 無視している                 | 16駒のみから選択           |
| 駒の重複             | 一部考慮不足                 | 重複なし                   |
| 複数属性の相関関係   | 無視                       | 正確に判定                 |

---

このように、数式で表現が難しい事象や、実際に手で並べるのが困難なケースでも、  
パソコン上で仮想的に駒を並べて検証すれば、正確な組み合わせを簡単に得ることができます。

とはいえ、数式的な考察も決して無駄ではありません。  
特に、バックトラッキングなどの探索アルゴリズムを実装する際に、  
今回の数式や条件を活用することで、無駄な探索を大幅に減らせるためです。今回は、もとが16の階乗もあり少し私のおんぼろでパソコンでは難しい所ではあります。

## 4. 統計的推定による引き分け率の確認

今回は計算負荷の大きい全探索を避け、モンテカルロ法を使って引き分け率を推定しました。
### 今回のケースでのモンテカルロ法
- 盤面をランダムに何度も生成して、その中で引き分けになる割合を計測することで、「引き分けの確率」を推定している。
- 今回は100万回（1,000,000回）ランダムに盤面を生成し、引き分け率の推定を行いました。  
その結果、引き分け率は約 **0.0196（約2%）** と推定されました。
この推定値を全盤面の通り数（16! ≈ 2.09×10^{13}通り）に掛け合わせると、  
引き分け盤面はおよそ **4.10×10^{11}通り** となります。
今回求めた推定値は、数式で計算した理論上の安全ライン数や、  
Pythonで実際に16個の駒から4つ選んで非勝利パターンを判別した数に比べると非常に大きな数字となっています。  
しかし、盤面全体での引き分け条件は複雑であり、  多くの重なりや制約が絡み合っているため、このように膨大な数になるのは妥当と考えられます。
```python
import random
from itertools import product

def is_quarto_line(line):
    """
    1ライン（4つの駒）を受け取り、
    どの属性でも4つすべてが同じ値（0か1）ならTrueを返す（勝ちライン）
    """
    for i in range(4):  # 属性は4つある（高さ・色・形・穴）
        values = [piece[i] for piece in line]
        if all(v == 0 for v in values) or all(v == 1 for v in values):
            return True  # 勝ちライン成立
    return False  # 勝ちラインなし

def is_draw(board):
    """
    4x4盤面(board)が引き分けかどうか判定する関数
    boardは4x4のリストで、各要素は4属性を表すタプル（例：(0,1,0,1)）
    """
    lines = []

    # 横ライン4本（boardの各行）
    for row in board:
        lines.append(row)

    # 縦ライン4本（boardの各列）
    for c in range(4):
        col = [board[r][c] for r in range(4)]
        lines.append(col)

    # 斜めライン2本
    diag1 = [board[i][i] for i in range(4)]
    diag2 = [board[i][3 - i] for i in range(4)]
    lines.append(diag1)
    lines.append(diag2)

    # どれかのラインが勝ちラインならFalse（引き分けではない）
    for line in lines:
        if is_quarto_line(line):
            return False

    # 全ラインで勝ちラインなしならTrue（引き分け）
    return True

def random_draw_estimate(trials=1000000):
    draw_count = 0
    for _ in range(trials):
        pieces = list(product([0,1], repeat=4))
        random.shuffle(pieces)
        board = [pieces[i*4:(i+1)*4] for i in range(4)]
        if is_draw(board):
            draw_count += 1
    return draw_count / trials

rate = random_draw_estimate()
print(f"引き分け率の推定値: {rate:.4f}")

```

## まとめ

数式による見積もりは、あくまで理論上の最大数を示す目安であり、
実際に存在可能な駒の組み合わせを反映するにはプログラムによる列挙・判定が不可欠です。

また、モンテカルロ法などの統計的推定は計算負荷を抑えられますが、
今回のような複雑な盤面条件では、大量の試行が必要になるため、計算時間やリソースが膨大になることもあります。数が少ないとあまり正確な値が出にくくなります。

今回は簡易的でしたが、クアルトというゲームを引き分けと言う視点から盤面解析しました。
式や条件を立て、それをプログラムに落とし込んで比較・検証する方法は、他の分野でも活用できます。
興味のあるテーマで試してみると、新しい発見があるかもしれません。
自由研究や趣味のプロジェクトにもぜひ挑戦してみてください！