あまり頭を使わずに負けない三目並べを作る
4月書き忘れてることに気づいて、もう、5月31日ではないか....。
StreamDeckで遊ぶために、以前に三目並べを作ったのですが、その解説です。割と力技で作った感じなので、もっと頭のいい方法が知りたい方はぐぐると出てきます。
三目並べとは
説明するまでもないですが、9マスに先手後手で、◯×を埋めていって、3つ並べたら勝ちですね。 先手後手に関わらず最適な手を打てば必ず引き分けになります。
負けないためにはどうするか？
負けないためにはどうしたら良いのかというと、
- 負けそうなとき(相手の三目が成立する時)は妨害する
- 負ける配置(二目が同時に2つ成立する)にさせない
- 勝ち筋が多くなる(二目が同時に2つ成立する)ところに置く
の3点を守るのが基本です。
実装方法
マスをビットで表す
9マスをビットで表します。
# 三目並べのビット 1 2 4 8 16 32 64 128 256
見やすいようにテーブルにします。
| a | b | c | |
|---|---|---|---|
| A | 1 | 2 | 4 |
| B | 8 | 16 | 32 |
| C | 64 | 128 | 246 |
勝利条件bit和で考える
勝利条件のbit和は下記のようになります(8列分)。
- 84 ... 斜め(cA,bB,cC)
- 7 ... A行
- 56 ... B行
- 448 ... C行
- 273 ... 斜め(aC,bB,cA)
- 73 ... a列
- 146 ... b列
- 292 ... c列
次で勝つときのbit和と、次どこを打てばよいかのbit は下記のようになります(8列x3=24)。
- 84
- 20: 64 ... cA(4)とbB(16)をとっていたら、 aC(64)が勝利手
- 80: 4
- 68: 16
- 7
- 3: 4
- 6: 1
- 5: 2,
- 56
- 24: 32
- 48: 8
- 40: 16
- 448
- 192: 256
- 384: 64
- 320: 128
- 273
- 17: 256
- 272: 1
- 257: 16
- 73
- 9: 64
- 72: 1
- 65: 8
- 146
- 18: 128
- 134: 2
- 130: 16
- 292
- 36: 256
- 288: 4
- 260: 32
負けないための戦略を考える
最初の3つの負けないためのルールを実行するためには、下記のようにする必要があります。
- 初手真ん中に置かれた場合は、端を取る(二目が2つ成立するのを防ぐ)
- ユーザーが対角、CPUが真ん中の場合は、辺の中を取る(二目が2つ成立するのを防ぐ)
- 真ん中が空いているなら、真ん中を取る(勝ちやすいだっけかな...。そうでもないかも)
- CPUの三目が成立するところに置く(勝利条件なので)
- 次にユーザーの三目が成立するところに置く(負けないために必要)
- 次にユーザーの二目が成立しそうなところに置く(ただし、ユーザーの二目が同時tに2つ成立する場合のみ)
- CPUが勝てそうなところ(次で勝つbit和となるところに置く、勝ち筋が同時に2つ発生する場所を優先)
- それでも決まらなかったらランダムで良い
だいたいこんな感じでやると負けません。 もし、人相手に勝ちたいなら、上を守っていれば、相手が油断してれば勝てるかと思います。
終わり
以上、あまり頭を使わずに負けない三目並べを作る方法でした。 ソースコードは下記にあります。
