[アルゴリズム] MINMAXアルゴリズム (アルファ·ベータ法)

10月 24, 2013 nguyenvanquan7826 アルゴリズム 4 回答

アルゴリズムMINMAXを学ぶ間、 (剪定アルファ – ベータ) 彼の多数の記事を参考にし、あなたの投稿を感じます QUANG WILDのブログ 比較的簡単かつ詳細. 私たちは、記事の著者に感謝し、作者を引用することが要求されました, あなたの記事の内容を参照してください。.

二人はチェスのように自分たちの国に目を向けるするゲームを考えてみましょう, チェス, カロ,… ゲームがスタートしており、すべての州の移動は新しい状態に現在の状態を変更します. ゲームは、一定の規則で終了します, 、そのゲームは勝者または両方のプレイヤーが自分の動きを開発することができない状態を反映した状態につながります, 私は平和のフラグ状態を呼び出します. 私たちは、特定の状態から選手になりますかどうかを分析しようとした条件で勝つ両方のプレイヤーが同じレベルを持っています.

そのようなゲームは、ツリーで表すことができます。, と呼ばれる木のゲーム. ツリーの各ノードは、状態を表します. ルートノードは、プレイの状態の開始を表し、. 各リーフノードは、ゲームの最終状態を表します (勝利やエアコン). 状態xは、子供のノードによって表されるN N移動の結果の最新の状態を表している場合は、状態xから幹ができます.

例 3-5: そこチェッカーゲームを考えます 9 傘. 二人は、XまたはOに向けます. 行く人はあります 3 アライメントボックス (横の, 毒性, 斜めの) 受賞者. すべての細胞型はまだ決定的でない持っている場合、2つのプレーヤーはネクタイ. このゲームの一部は後に、ツリーで表され、:
アルゴリズムMINMAX

ゲームツリーで, リーフノードは他のノードと簡単に区別ペアの背景や枠線を網掛けされています. 私たちは、WIN-失ったり、描画の選手の状態を反映するように、各葉ノードの値を割り当てることができます. このようなリーフノードは、次の値を割り当てました:

· 1 ライダーは、Xを獲得していることであれば,

· -1 人々はそこに行くとXを失った場合

· 0 二人の選手は、ディケンズを持っている場合.

したがって、任意の状態から, 彼のターン, Xライダーは最大値につながっている状態に戻り、国を選択します (この場合、 1). 我々はXの動きがMAXを選択言います, 彼の動きは、ボタンMAXからコールされるX選択したノード. Oのライダーは、最小値と状態につながった移動を選択しますオン (この場合、 -1, Xは失うことになるので、O勝). O MIN選択して移動を言います, O彼の動きからコールされる選択されたノードは、MINノード. 二人のプレイヤーはターンは、いくつかの木のゲーム上の水のレベルを上に行くluanphienだけでなく、MAXとMIN取りますか. ツリーゲームとも呼ばれる木MIN-MAXそう. 我々は2つ​​の選手の入賞または空気条件と能力の勝利を反映するために、ツリー内のノードの処理ルールを提供することができます.

リーフノードは、その値がそのボタンに割り当てられた値であるノードの場合. 反対, MAXボタン、その子のすべての値の最大値によって、その値であればボタン. ボタンがボタンMINである場合、その値は、そのすべての子の値の最小値であります.

この処理規則は、演算式ツリーの規則に似ています, ここでの違いは、オペレータが最大または最小の関数であることである取り、各ボタンは、より多くの子供を持つことができます. そこで我々は、ツリーノードのゲームのバックトラックを治療するための技術を使用することができます.

私たちは以下のいずれかのいくつかの仮定をインストールするには:

· 私たちは学校を持っています インフォ の値を与えます.
· 定数 2 と -2 それぞれ最大かつ各ノードの最小値.
· バリアント ℃ 行くためにXまたはOボタンの値を決定するチャー.
· 別のタイプ ポインタ 宣言されたツリー内のノードを表現する適切な方法は、プレイの状態を反映します.
· 我々は、機能を持っています にNutL() ノードがリーフノードであるか否かを判断します?
· 顎 最大値と最小値 それぞれ2つの値の最大値と最小値をとります.

木ゲームの徹底的な治療アルゴリズム
顎 営業時間 Qボタンや文字cに入るノードの値を返します。.

qがリーフノードである場合、戻り値はリーフノードに割り当てられています. 逆に、我々はq値を与える値は一時的なもので -2 または 2 Qに依存することは、XまたはOボタンとqのレビューです. qの値は、リセットのval = V maxを一度(営業時間,ザ·) qは、Xボタンおよび値の場合=分(営業時間,ザ·) QはOボタンである場合. すべての子供は、QのヴァルのQ値であった場合には、一時的にその値になります.

MINMAX

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
{Ham tra ve gia tri trang thai khi dung minmax - thuat toan minmax}
function val(var q: pointer; c: char; Vp: item): item;
var
    i: integer;
begin
    if (nutLa(q)) then      {Neu la nut la thi lay ngay KQ gia tri cua nut do}
        begin
                {writeln(q^.lab,'->>> ', q^.info);}
                val:= q^.info;
        end
    else
    begin
        for i:= 1 to q^.numChild do   {Duyet cac nut con cua q}
        begin
            if c = 'X' then       {Neu dang la luot X}
            begin
                q^.info:= max(q^.info, val(q^.child[i], 'O', q^.info));
                {writeln(q^.lab,'->>> ', q^.info);}
                val := q^.info;
            end
            else                    {Nguoc lai la luot O}
            begin
                q^.info:= min(q^.info, val(q^.child[i], 'X', q^.info));
                {writeln(q^.lab,'->>> ', q^.info);}
                val := q^.info;
                break;
            end;
        end;
    end;
end;

一般的な木Tに適用されますインストールされています:

01
02
03
04
05
06
07
08
09
10
procedure catTia(var T: pointer);  {Dua thuat toan vao cay}
var
    p: pointer;
    i: integer;
begin
    if T <> nil then
    begin
        T^.info := val (T, 'X', T^.info);
    end;
end;

チェスカロ

あなたが見ることができるプログラムを完了 ここに

続きを読む: 一般的な木