ゲーム木の解法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/31 05:03 UTC 版)
完全ゲーム木があれば、ゲームを解くことができる。つまり、その解に従って打っていけば、負けないことを保証できる。そのアルゴリズムは再帰的に以下のように説明できる。 最終盤面でプレイヤー1が勝つ盤面とプレイヤー2が勝つ盤面を色分けし、引き分けになる盤面を第三の色にする。 1つ前の手（盤面）を見る。そのレベルの盤面になる手を自分の手とする。そのとき相手が勝つ盤面が子ノードとして1つでも存在する場合、このノードを相手の色に塗る。直下の子ノードの色が全て同じなら、このノードも同じ色に塗る。そうでない場合は引き分けの色に塗る。 以上を順次上に向かって繰り返し、全てのノードを色分けする。根ノードがどの色になるかで、このゲームの性質が決まる。 右図は、上記のアルゴリズムに従って色分けしたあるゲームのゲーム木を示したものである。
※この「ゲーム木の解法」の解説は、「ゲーム木」の解説の一部です。
「ゲーム木の解法」を含む「ゲーム木」の記事については、「ゲーム木」の概要を参照ください。
ウィキペディア小見出し辞書の「ゲーム木の解法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ゲーム木の解法のページへのリンク
