ゲームが「解けた」とは

　オセロや将棋やチェスや碁といったゲームは、数学やコンピューター科学の研究対象で、これらのゲームをプレイするコンピュータープログラムはそうした研究の成果です。

　こうしたゲームを数学やコンピューター科学はどのように扱うのでしょうか。原理を見てみましょう。

　オセロは中心部に黒石が2個と白石が2個置かれた最初の状態（局面）から始まります。盤面は、プレイヤーが手を打つたびに別の状態（局面）に変化していきます。

0手目：最初の状態です。中心部の4×4のマスだけ示します。

□□□□
□○●□
□●○□
□□□□

↓

1手目（4通り）：黒の番です。黒の打てるマスは4マスありますが、代表として1状態だけ示しておきます。

□□□□
□○●□
□●○●
□□□□

↓

1手目つづき：白の石が裏返されました。

□□□□
□○●□
□●●●
□□□□

↓↓↓

2手目（12通り）：白の番です。白の打てるマスは3マスあるので、ありえる棋譜は4×3=12通りに枝分かれします。

□□□□  □□□□  □□□□
□○●○  □○●□  □○●□
□●●●  □●●●  □●●●
□□□□  □○□□  □□□○

↓↓↓

2手目つづき：黒の石が裏返されました。

□□□□  □□□□  □□□□
□○○○  □○●□  □○●□
□●●●  □○●●  □●○●
□□□□  □○□□  □□□○

↓↓↓↓↓↓↓↓↓↓

3手目（168通り）：黒の番です。棋譜は168通りに枝分かれします（が、図は省略します）。

↓↓↓↓↓↓↓↓↓↓
・
・
・
↓↓↓↓↓↓↓↓↓↓↓↓↓↓・・・↓

　こうしてゲームが進行するにつれて、どんどん棋譜は枝分かれして、その数は爆発的に増えていきます。枝分かれするさまはツリーにたとえられます。