スポンサーサイト

上記の広告は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に行われるようなので、電王トーナメントの有無に関してもそこで発表されると予想される。私としては是非とも開催して欲しいと思う。
その際には、きふわらべに一発入れて欲しい(笑)
スポンサーサイト

Noviceの歩み(とりあえず動くまで)


昨日Novice がver.0.5になって、とりあえず駒を動かせることと駒を成ることが出来るようになったので、
開発開始からこれまでの歩みを書いていこうかと思います。

3/20プログラミングを学び始める。

~4/8 C言語の基礎的な部分(if文やfor文)をオセロを作りながら学ぶ。
オセロはコンピューターがランダムに手を生成するとこまで作り中断。

4/8~4/11 将棋プログラム制作開始。
最初はsimkや、れさぴょんを参考に作り始める。挫折。

4/11~ 0から自分で作ることを決め、フルオリジナルの将棋プログラムを制作開始。その日のうちに、局面をコマンドブロンプト上で表示出来るようにする(init_boardとprint_board)。

4/12~ 二次元配列を用いて思考部を作り始める。とりあえず合法手を読むことから。

4/17 プログラム名をNoviceに決定。名前の由来は前の記事を見てね★

4/18 上手く動かないので最初から考え直す。以下、Twitterのつぶやき。

プログラム組み直し(メモ)
左筋から自分の駒を探す→その駒が動けるか→動けるなら動かしてみて点数をつける→それがそれまでで一番高い点数ならキープ→次の駒→最後までいったらキープしてる動作を出力→手番を渡す


4/25~4/28 USI通信部の作成に着手するも挫折。

4/28 相手の手を入力出来るようにする。

4/29~5/10 思考部の構想をいろいろ弄りまわす。

5/10 コマンドブロンプトで出力テストを試みるもエラーを95個も吐いて動かず。

5/11 エラーを潰していき、とりあえず出力は出来るようになった…………なったけど………汗

ここから


こうなる


探索時に動かした駒をもとに戻していないのが原因。飛車が消えたのは未だに謎。

5/13 バグを修正して……



5/13 相手の駒を取ると五枚目の香車が発生するバグを発見。

5/14 成りを実装し、vs きふわらべ電王T ver. を実施(USIに対応してないので手動)


結果は、きふわらべが王手を放置しNoviceの勝ち。

5/15~5/18 金駒を左方向に動かす手を読まなかったり、飛車が左右に動かなかったり、角が桂馬みたいな動きをするバグに苦しめられながらもなんとか修正。


5/18 vs きふわらべ最新版。




手数的に終わらなかったので中断。


これからの課題。

2手先を読み、王手を回避する。
駒を打つ手を読む。
USIに対応させる。
 
etc……



将棋プログラム Novice について


今回は将棋プログラムNoviceの開発コンセプトについて書きたいと思っています。

そもそもNoviceという名前は未熟者、初心者という意味です。
これは制作者の私がプログラミング初心者ということや、Novice自体が将棋プログラムとして未熟であるという意味でつけています。

私はNoviceが、プログラミング初心者が将棋プログラムに興味を持っていただく際のきっかけになれば幸いだと考えています。

そのためNoviceは極力簡単な文法を用いて書いています(私自身が、それしか書けないこともあるが…笑)

たとえば、データ構造は二次元配列を用いており、探索もswitch関数による分岐を用いています。速度を考えたら、他のソフトに比べ最遅でしょう(笑)

ですが、Noviceを見た初心者プログラマーが

こんなん俺ならもっと強いの作れるわ

とでも思っていただき開発を始めてくれたら私は泣いて喜びます(※泣きません)

ということで、これを簡潔にまとめた言葉でコンセプトを示し次回へと引継ましょう。

ルール通り動くだけの将棋プログラムは、プログラミング初心者でも作れる!

Twitter→@naonza0

ブログ方向性の変更

ご無沙汰しております。

なかなか記事が更新出来ず申し訳ありません。

実はオセロプログラムは指し手をランダム生成するとこまで作って、その後、将棋プログラムを書き始めました笑

そのため中々ブログを覗くことすらも出来ていませんでした。

将棋プログラム(以下Novice)は、やっとルール通り指せるのではないかというところまで出来ました。

ということで、オセロはデータ構造までで一旦、休止して、以降はNoviceについて書いていこうと思います。

プロフィール

kuma

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

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

この人とブロともになる

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