

このゲームでは先手に必勝法がある。参照Youtube：Numberphile 3 board tic tac toe  
ただし、プログラミングに落とし込むぐらいの簡単な必勝法がみつからない。  
目標はその必勝法を利用して疑似AIを作ること。

ルール：  
このゲームの盤面は基本的に三つの三目ならべのボードで構成されている  
参加者二名が使う印は”X”で共通  
ひとりずつ任意の格子に印をつける  
三つ印がつながったらそのボードだけ消える。  
最後に残ったボード（場面）で、三つXをならべてしまった参加者が負ける

ボード一つの場合は先手が真ん中に駒をおけば簡単にかてるが、ボード三つだと難しい。


CC BY-SA 4.0
2021-10-28T10:26:26.333
83306
2021-10-29T07:23:00.157
2021-10-29T06:47:04.417
48340
48340
question
アルゴリズム
三目並べ、三つの盤面で同時、✖のみ使用　先手の必勝法を考える


まずはご自身で何回か手を動かし、このゲームを実際にプレイしてみてください。すると規則性が見えてくるかなと思います。

このゲームは、ゲームの最中に取り得る場面の状態を列挙できます。27 マスのそれぞれに印がついているかついていないかなので高々 2^27
通りで、ゲームのルールや対称性を気にすると更に減ります（ひとつの盤面に置ける印の数は最大いくつでしょうか）。またこのゲームにはランダム要素が一切なく、ゲームをするにあたって必要な情報は全て全員に公開されています。

したがって、今どの状態にいるかが分かると、次どの状態になれば最適なのかが必ず分かります。最初に全部探索して覚えておいて、今いる状態から望ましい状態に向けて次の手を選べば良いです。

もしこれで計算時間が長くなりすぎてしまうのであれば、ミニマックス法やアルファ・ベータ法などの有名な枝刈り法が役に立つでしょう。


CC BY-SA 4.0
2021-10-29T05:32:07.100
83319
2021-10-29T05:32:07.100
19110
83306
answer