このページは本家wikiのWhyWritingAWesnothAIIsHardを訳したものです。
私はこの問いの答えとして、主にWesnothのAIを伝統的に書いていた数人と、Summer of Codeの一部としてAIの開発をした学生について書く。
WesnothのAIは非常に役に立つものだが、その難しさを侮ってはいけない。ほとんどの伝統的なAIメソッドをWesnothに適用させることはできず、非常に革新的な解決策を使う事が必要とされた。
多くの人はWesnothのとても強力なAIをかなり簡単なはずだと思っている。結局のところ、コンピュータはチェスやバックギャモンの世界チャンピオンを負かしている。どちらもターン制のゲームなのに、Wesnothはなぜこれらとは違うのだろうか？このドキュメントでは、なぜWesnothがチェスやバックギャモンのテクニックを使わずに成功に近づいたのかについて示そう。
Wesnothは非常に柔軟だ。それは様々なサイズやユニットで作られた、多くの異なるマップに現れている。プレイヤーは自分のユニットをどこにでも置く事が出来る。これで、一般的なAIを作る事はより難しくなる。
コンピュータがチェスがとてもうまいのは、チェスが比較的小さなボードで、いつも同じであり、こまが同じポジションからスタートするからである。これは、コンピュータが処理しなければならない盤面が、比較的制限されていることを意味する。そして、特にコンピュータが処理しなければならない盤面のタイプはかなり限られている。例えば、チェスで城のキングの前に3つの連続したポーン(将棋で言うと歩)があるパターンはチェスではよくあるパターンだ。そしてそのパターンをチェスの評価エンジンが認識して、強さを判定するのは比較的簡単なことなのだ。
Wesnothは全く違う。Wesnothとチェスを比べるまでもなく、もしチェスが違う形や大きさだったら、その都度チェスのプログラムが書かれるだろう、とあなだって思うはずだ。真ん中が通れない正方形かもしれないいし、近づけない角があるかもしれない。その他いろいろ考えられる。しかも、プレイヤーは複雑なルールに従って、様々な「空想のコマ」を考えるかもしれない。ナイトのように動くが、特別に1歩進めるコマ、とか、ナイトとビショップのように動き、前方に進めるコマ、とか。
そんなプログラムは熟練した人間のようにはプレイできないだろうし、人間の方が新しいコマに対して、コンピュータのプログラムよりもはるかに進んだ対応ができるだろう。
しかし、これではまだWesnothの複雑さにはアプローチしていない。Wesnothは、不安定な情報を持ち、ランダムな結果を出す。チェスのプログラムはかなりチェスの決定性を頼りにしている。Wesnothは、「あなたには結果がどうなるか分からない」という点ではバックギャモンに近い。しかし、バックギャモンの盤面の状態は小さいが、Wesnothは巨大だ。
Wesnothの計算複雑性はチェス、バックギャモン、将棋、碁などのボードゲームと比べると膨大だ。30×20のマップを考えてみよう。Wesnothのマップでは典型的なサイズだ。さらに16の標準的な地形のタイプを考えてみる。これを表現するには2400ビットのデータが必要だ。従って、このサイズのマップは2の2400乗通り作る事が可能だ。まっさらなものを除いて、多くのユニットの組み合わせが可能になり、違った場所、違った状態などを作る事が出来る。可能な位置の数は本当に膨大な量になる。Wesnothの盤面の状態は10の1000乗をゆうに超え、おそらく10の10000乗にもなる。これでは碁の複雑性さえもまるで小人だ。碁の盤面の状態は"たった"10の171乗なのだから。
Wesnothは分枝度も巨大だ。たいていの伝統的なボードゲームでは、コンピュータの分析ができるが、それは大体のゲームにおいて、プレイヤーが動かすコマが1つで、もう一方のプレイヤーも動かすコマが1つだからだ。Wesnothでは、別のプレイヤーが動かす前に、一度に全てのコマを動かす。また、Wesnothではたいていコマを動かしたあと、多くのオプションを持っている。20以上のタイルを移動できるコマも珍しくなく、プレイヤーはコマを12人かそれ以上持つ事が出来る。コマは攻撃を選択することもでき、武器での攻撃など様々だ。攻撃が発生すると、ヒットした攻撃に基づいて多くの結果が出される。
Wesnothの分岐度はこうして巨大になっていく。Wesnothの差し手の過程の組み合わせ(GTC)は計り知れないほど大きい。先々の多くの移動を考える事は難しいのだ。
Wesnothでの離散分析は失敗する。厳密にはWesnothも離散ゲームだが、とても多くの位置があるため、離散分析の技術では失敗するからだ。
幸運にも、Wesnothは長くプレイできるゲーム(連続ゲーム)として扱う事ができる。なぜなら、多くのポジションがお互いに酷似している傾向があるからだ。加えて、離散ボードゲームと違って、Wesnothでは小さな間違いの移動が命取りになる、ということはそうそう無いからだ。
total: - today: - yesterday: -
