ゲームの木

OR事典

ゲームの木

読み方：げーむのき
【英】：game tree

展開形ゲームにおいてプレイヤーの手番の系列をグラフ理論の有向木の概念を用いて表現するモデル. 木の分岐点はプレイヤーの手番, 木の枝はプレイヤーの選択可能な行動(選択肢)を意味する. 木の始点から終点までの経路をゲームの1つのプレイという. 木の各終点にはプレイヤーが得る利得が与えられる.

「OR事典」の他の用語

ゲーム理論：

カライ・スモルディンスキー解  カーネル  ゲームの値  ゲームの木  ゲーム理論  ゲーム理論の応用  コア

ウィキペディア小見出し辞書

ゲームの木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 01:24 UTC 版)

「展開型ゲーム」の記事における「ゲームの木」の解説

ゲームの木は点で示されるノードと2点を結ぶ有向線分である枝とから成る。ノードは状態とも呼ばれ、ゲームのひとつの局面を表す。枝は一人のプレイヤーの意志または偶然による選択により、あるノードから別のノードへ遷移できることを示すもので選択肢(alternative)とも呼ばれる。ノードは分岐点と頂点に分けられる。頂点はそこから枝が出ていないノード、すなわちゲームが終了した局面を示す点であり、各プレイヤーの利得(pay off)が与えられている。利得は利得関数とも呼ばれ、プレイヤーの数だけの成分数を持つベクトル量として表せる。分岐点は頂点以外のノードであり、手番(move)とも呼ばれる。各手番では一人のプレイヤーの意志または偶然により、その手番から出ている選択肢のひとつが選択されてその先の手番に遷移する。偶然により選択がなされる手番を偶然手番と呼ぶ。またプレイヤー甲の意志で選択がなされる手番を甲の手番と呼ぶ。プレイヤー分割とは手番の集合を各プレイヤーの手番に分割したものである。偶然手番の確率分布族とは偶然手番での確率分布を定めたものである。そこに遷移する選択肢がひとつもない分岐点を底点と呼び、これはゲームの初期状態、つまり出発局面である。 以下に「奇数偶数ゲーム」（MorraまたはOdd-or-evenと呼ばれる）を例としてゲームの木を示す。これは、双方が偶数か奇数のどちらかを示し、示された数の和が偶数ならAの勝ちで奇数ならBの勝ちとするゲームである（外部リンクの英語版wikipedia参照）。 図1A.不完全情報ゲームの木の例。点線で囲んだものが情報集合のひとつ。 図1B.図1Aの標準型表現。同時手番ゲームの例。 図2A.完全情報ゲームの木の例。 図2B.図2Aの標準型表現。Bの戦略はAの第1手に対応して4通り。Bの第2戦略は必勝戦略である。