スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

MinMax法による2手先読みの実装


Novice ver0.5では王手を放置したので、さすがにそれは駄目だろうと思い2手先を読ませ、王が取られる場合の評価値を-15000に設定することにした。

そこで2手先を読ませる際の評価の付け方にはMinMax法と全幅探索を採用することを決めMinMax法とはなんぞや?というところから始めた。

MinMax法とは、簡単に言えば自分が指した手に対し相手が最善手を選ぶことを前提に評価値を決めるもの。(だと思う)

Wikipediaを見たら

function MIN_MAX(position:局面, depth:integer): integer
begin
if depth=0 then return STATIC_VALUE(position); {読み深さに達した}
positionを展開→すべての子ノードをchildren[]に。子ノードの数をwに。
if w=0 then return STATIC_VALUE(position); {終局}

if positionは自分の局面 then begin
max := -∞;
for i:=1 to w do begin
score = MIN_MAX( children[i], depth-1);
if(score>max) max := score;
end;
return max;
end else begin{positionは相手の局面}
min := ∞;
for i:=1 to w do begin
score = MIN_MAX( children[i], depth-1);
if(score end;
return min;
end;
end;

というのが貼ってあったんだが、プログラミング初心者の私には何がなにやらさっぱり分からない。
ということで、我流でやってみた。

まず、ver0.5の仕様を見てみる。
ver0.5では盤の端から1マスずつ自分の駒を探していき、すべての駒を全ての方向に動かして最大の評価値の手を採用していた。
その際の方法は、動かしてみた手が最善手であれば次の一手をその手に書き換えるというものである。

2手先を読ませるために、これと同じことを相手の駒でもう一度させたのである。
つまり、自分の駒を動かしてみる→その後相手の駒を動かしてみる→そのタイミングでの評価値をつけて、先手から見てそれが一番高いものを採用するということだ。

理論上、この関数を増やし続ければ、いくらでも先読みするのだが、一手指すのに恐ろしく時間がかかる。だから、いずれαβ法を実装したいと思う。

その前にUSIに対応させないといけない。
手動で手を入力していくのは大変だ(笑)

そういえば、電王戦に関する会見が6/3に行われるようなので、電王トーナメントの有無に関してもそこで発表されると予想される。私としては是非とも開催して欲しいと思う。
その際には、きふわらべに一発入れて欲しい(笑)
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

kuma

Author:kuma
FC2ブログへようこそ!

最新記事
最新コメント
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。