反復深化深さ優先探索(IDDFS;Iterative deepening depth-first search)やろうぜ(^~^)?

反復深化深さ優先探索(IDDFS;Iterative deepening depth-first search)やろうぜ(^~^)?

20210124shogi2a2b1.png
「 イテレーティブ ディープニング デプス ファースト サーチ やろうぜ?」

kifuwarabe-futsu.png
「 何だぜ それ?」

ohkina-hiyoko-futsu.png
「 時間切れ負け しないように 途中で 計算を投げ捨てる 探索よ」

ramen-tabero-futsu2.png
「 どうやって やるんだぜ?」

kifuwarabe-futsu.png
「 IDDFS のことか。
説明すると お父んが寝てしまうので 手順を進めながら やってみよう」

反復深化(Iterative deepening)とは

20210716shogi141.png

kifuwarabe-futsu.png
「 👆 反復深化探索は、よく こんな絵で 説明されるな」

ramen-tabero-futsu2.png
「 ぢごく だ。 デザインがうまく機能していない建築だ」

kifuwarabe-futsu.png
「 将棋盤の前に座っている気分になってくれだぜ」

デプス(Depth)

20210716shogi153a1.png

kifuwarabe-futsu.png
「 👆 まず、 デプス(Depth)というのを 覚えてくれだぜ。
これから、上図を使って デプス を説明しよう」

ohkina-hiyoko-futsu.png
「 数学に 毒されたみたいな図 わらう」

デプス1

20210716shogi154a1.png

kifuwarabe-futsu.png
「 👆 デプス1 というのは、最後の扉の 前にいるところだぜ」

ramen-tabero-futsu2.png
「 麻雀の テンパイ みたいだな」

kifuwarabe-futsu.png
「 奥の扉を開けるのは、将棋で例えると 1手指すことだと思ってくれだぜ」

デプス0

20210716shogi155.png

kifuwarabe-futsu.png
「 👆 デプス 0 というのは、基本的には 指さない ということだぜ」

ramen-tabero-futsu2.png
「 わらう」

kifuwarabe-futsu.png
「 デプス 0 で何をやるかは まあ プログラマーが好きにしろだぜ」

ohkina-hiyoko-futsu.png
「 何が できんの?」

kifuwarabe-futsu.png
「 デプスをいったん忘れて、もうちょっと 深く読む、とか そういうことだぜ」

20210716shogi156a1.png

kifuwarabe-futsu.png
「 👆 探索(たんさく;Search) と呼ばれるものは、行ったっきり戻ってこないものと、
再び帰ってくるものがある。 コンピューター将棋で探索と言えば、 再び帰ってくると思っていい。
これを 再帰(さいき;Recursive)と呼ぶぜ」

ohkina-hiyoko-futsu.png
「 おかえり」

ramen-tabero-futsu2.png
「 開けた扉を閉めろだぜ」

kifuwarabe-futsu.png
「 絵を描くのが めんどくさいので 省略するぜ。
頭の中で バタン バタン してくれだぜ」

ohkina-hiyoko-futsu.png
「 デプス0 って Uターン してくるとこなのね」

20210716shogi157a1.png

kifuwarabe-futsu.png
「 👆 イテレーションが 1回終わっているときの デプス 0 もまた、基本的には 指さない ということだぜ」

ramen-tabero-futsu2.png
「 そこも デプス0 かあ」

ohkina-hiyoko-futsu.png
「 その 数えで1歳、 満0歳 みたいなの、どうにかなんないの?」

kifuwarabe-futsu.png
「 デプス0 と同じ呼ばれ方をしても、
イテレーションが 0回目、1回目、2回目 と増えていくたびに デプス0 に着くまでに開けたドアの数が増えていることを
よく意識しておいてくれだぜ」

kifuwarabe-futsu.png
「 ここでクイズだぜ」

ramen-tabero-futsu2.png
「 8年ぐらいブログを書いているが、クイズが出たのは 初めてだよな」

kifuwarabe-futsu.png
「 先ほどの図で、 イテレーションが 1回終わってるときの デプス0 のすべての部屋に入ったとき、
それまでに開けた ドアの数を答えなさい」

ramen-tabero-futsu2.png
「 わざわざ クイズにするんだから 6 とか答えたら ハズレなんだろ。
同じ部屋に 何度も出たり入ったりすれば 答えは無限にあるんじゃないかだぜ?」

kifuwarabe-futsu.png
「 ブーッ。 正解は 8つだぜ。 数えろ」

ohkina-hiyoko-futsu.png
「 んー、どこを どう数えたら 8なんて言う 中途半端な数が 出てくるのかなあ?」

20210716shogi158.png

kifuwarabe-futsu.png
「 👆 納得できるまで 数えろだぜ」

ramen-tabero-futsu2.png
「 なんか 何回も同じとこ 通ってる気がするな……」

ohkina-hiyoko-futsu.png
「 開いているドアの数は 8つ ねえ」

探索経路

20210716shogi159.png

kifuwarabe-futsu.png
「 👆 イテレーションが 2回終わっているときの デプス 0 も、基本的には 指さない ということだぜ」

ohkina-hiyoko-futsu.png
「 そのドアは、横へ、横へ 開けてんの?」

kifuwarabe-futsu.png
「 いいや」

20210716shogi160a1.png

kifuwarabe-futsu.png
「 👆 まず デプス1 で 深さ優先探索 をするぜ」

ohkina-hiyoko-futsu.png
「 その グネグネ したやつよね」

20210716shogi162a2.png

kifuwarabe-futsu.png
「 👆 次に デプス2 で 深さ優先探索 をするぜ」

ramen-tabero-futsu2.png
「 ぜったい わらう」

20210716shogi163a1.png

kifuwarabe-futsu.png
「 👆 次に デプス3 で 深さ優先探索 をするぜ。 おっ、玉を発見」

ohkina-hiyoko-futsu.png
「 超・大変じゃない?」

20210716shogi165a1.png

kifuwarabe-futsu.png
「 👆 目的のものを見つければ すぐ帰ってきても いいわけだしな」

20210716shogi166.png

kifuwarabe-futsu.png
「 👆 時間が切れる前に すぐ帰るのも 同じ手順を踏まえろだぜ」

20210716shogi167.png

ohkina-hiyoko-futsu.png
「 👆 時間切れになったら、途中まで探索していた分、全部 無駄になんの?」

kifuwarabe-futsu.png
「 そのイテレーションで 探索が途中だった分は 無駄になるな」

ohkina-hiyoko-futsu.png
「 なんだか もったいないわねえ」

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事