ゲームプログラミングの基礎

「二人零和完全情報ゲーム」というのは，ゲーム全体の中で以下のような制約 が加えられたものである．

二人

ゲームにはトランプの1人遊び(ソリテア)のようなものから，マージャ ンのような4名(あるいは3名)，あるいは多数でおこなわれるゲームまである． 1人遊びは一種の最適化の問題としてとらえることができる．2人で，それぞれ が対立した意図を持って行動するという要素が入る．3人以上の場合は，協力 や取引などより複雑な要素も入る．

零和

ゲームの結果がどうなっても，参加プレイヤの得られる利得の総和が零 であるというもの．将棋であっても，リーグ戦の最終戦で片方は挑戦権がかかっ ていて，片方は挑戦権も陥落も関係ない場合のように，グローバルな視点でみ ると零和でないというシチュエーションもあるが，

完全情報

囲碁や将棋では，自分の行動を決定する際には，局面の状態がすべて得 られている．それに対して，トランプやマージャンなどでは，山札，他のプレ イヤなど見えない部分がある．

確定

サイコロのようなプレイヤの意思とは無関係に影響を与える要素がない．

局面(State) -> 着手(Move)

このようなゲームをプレイするプログラムを作るには，局面に対して評価関 数を定義するのが一般的である．この評価関数は，勝つ確率(引き分けがない 二人零和完全情報ゲームでは，0か1の2値)が高い局面ほど高い評価値になるよ うな関数が望ましい．

局面に対して，すべての着手を生成し，それぞれの着手を適応した局面の評 価値を計算し，評価値が最大になるような着手を選択するという単純な方法で も，評価関数が正確なら，常に最善手が選ばれる．

しかし，実際に使える評価関数は不正確なので，より局面を進めてその上で の評価関数を計算する方法が使われる．これは，人間のプレイの場合と良く似 ている．

探索を表現するために，探索木というものがよく用いられる．