author: grafi
Haskellで実装したリバーシエンジン．
- 64ビットのレジスタを前提としたビットボードを用いてビット演算を多用した盤面処理
- ビットボードの場合当然な気はするが，盤面は都度コピーする実装
- Edaxに近いアルゴリズム
- ただし実装はEdaxよりもかなり単純
- 斜めのラインの取得にrotate命令を使う点が異なる
- αβ法
- 古典的評価関数
- 着手可能数，角の数，駒差を用いる
- 浅い読みの結果を用いたMove Ordering
評価関数を先に改良しないと、評価関数の重さが全然変わるので枝狩り数の改良の効果がよく分からない気がする。
- パターンに対する評価関数を機械学習によって作る
- NegaScout
- 置換表
- ProbCut
- 定石
- ゲーム木という木構造を探索するプログラムである「樹」
- リバーシの盤面が満月と新月に例えられることから「多月」
現状，隅の数と着手可能数に基づく古典的評価関数によって，中盤10手読み，終盤18手読み切りを行っている．GHC 7.6.1でO2オプションでコンパイルし，1.8 Ghz i7搭載のMacBook Airで動作させて，序中盤は平均的に0.1秒くらい，遅くとも1秒以内くらいで動作し，18手読みは盤面によって速度差が激しいが遅くとも30秒以内くらいには行えることを確認している．LLVMでのコンパイルは試していないが，数値計算を主体とするプログラムでは速くなる傾向があるようなので，ビット演算などを多用している関係上ある程度速くなると予想される．開発環境と同等以上の性能のマシンを用いた対局であれば，1分のレギュレーションはほぼ満たせるはずである．シングルスレッドしか使っていないので，コア数は関係無い．
現状，残り時間によって探索深さを決定するなどの工夫は行なっていない．局面によって読みきり時間の差が激しいので，このような工夫を行えば，今と大きく変わらない実装で20手読みくらいまでは1分のレギュレーションの中で現実的に試みることができそうである．
対局は，田中諒さんのAI，城戸さんのAIと行い，共に勝利した．二人のAIと対戦したのはチューニングが不十分な頃だったが，彼／女のAIも改良されていれば提出された実装においては負けている可能性もある．ランダムに打つ実装に対しては，自滅するようなバグがあるときには時々負けたが，そういうバグが無いと思われる状態で100回以上は試験して一度も負けていない．
Move Orderingの深さは，ある程度ランダムに打つクライアントとの対局や自己対局を行い，なんとなく安定して速度が出るように調整してParameter.hsに書いている．これによって，中盤10手読みは安定して高速におこなえるようになった．またビットボードによる高速化はかなり大きいと思われる．姑息な最適化はかなり意識しているが，厳密にベンチしながら行ってはいない上そもそも置換表の実装なども行なっていないため，premature optimizationとの誹りを免れ得ないとも自覚している．
NegaScout法の実装は試みたが，NegaScoutを使った場合に一番速くなるくらいのMove Orderingの読み数にするよりも，NegaScoutを使わずにより浅い読みでMover Orderingする方が速くなったので，今のところ採用していない．NegaScoutはMove Orderingが上手くいっている場合の探索速度を上げる手法であるが，わたしの現状の実装はMover Orderingが失敗している場合に極端に遅くなってしまうことが課題であり，この点の解決には寄与しないと考えられないというのも理由である．
抜本的な解決には，やはりパターン評価に基づく優秀な評価関数と，置換表が必要になると思われる．
上下左右斜めに盤面をシフトしていくやり方で，wZebraの実装と同じ手法である．
日本語の解説記事である，http://d.hatena.ne.jp/ainame/20100426/1272236395を参考にした．
着手可能手のイテレートでは，y=x.&.(-x)によって，yにはxの一番下に立っている1だけが立ったビットが入ることを用いて行っている．y-1に対してpopCountすることで，64未満の自然数として着手位置を得ることができる．
こちらは割合に複雑な手法で，また既存の資料が無くて自分で考えた部分が大きいので詳しく書く．
まず，駒を置くマスから見て縦横斜めの4方向の8つの駒の並びを，それぞれ8ビットの値として取得する．各方向について，8つの駒の並びから，ひっくり返る駒を取得する．次に，盤面上の元々の位置に戻した上で，全てをORして盤面全体でのひっくり返す駒を取得している．
ビットの移動に乗算を多用していることが特徴である．近年のCPUは乗算が早いため，複数のビットを別々の距離でシフトするといったときに上手く乗算を使えば高速化が可能である．Kindergarden Bitboardとして知られる手法のようで，Edaxでも実装されていたが，Edaxの実装はかなり読みづらく詳しいドキュメントも存在しないと思われる．また，HaskellのDataBitsライブラリにあるrotateShiftを用いているのがEdaxの実装と本質的に異なる点である．なお，GHCでは現状rotateはprimOpとして存在せず，後段でのstrength reductionなどにも乗らずx86などに存在する命令にコンパイルされず通常のビットシフトによって実現されるようであるのは残念であるhttp://ghc.haskell.org/trac/ghc/ticket/7337．
8つの駒の並びからひっくり返る駒を取得する部分では，合計1.6KiB程度の二つの配列を使用している．二回のメモリアクセスとビット演算数回で出来るため，配列がL1キャッシュに載っていればかなり速いと考えられる．
以下，具体的な処理を示す．レジスタ1つ（64bit）を8×8の配列で表記し，LSB（0の位）を右下，MSB（2^63の位）を左上として，右から左，左端に達したら一つ上に上がって右端に移動，という順で位を上げていくとする．盤面の右下を，xy座標の原点とし，またxy座標だけではなく各方向の処理に都合のいいnmという二数の組み合わせを考えて説明を行うこととする．
また，省略しているが，斜めの盤面の処理のときは，盤面の上下をまたいで循環するところを適宜ビットマスクしないといけない．
n = y
m = x
77 76 75 74 73 72 71 70
67 66 65 64 63 62 61 60
57 56 55 54 53 52 51 50
47 46 45 44 43 42 41 40
37 36 35 34 33 32 31 30
27 26 25 24 23 22 21 20
17 16 15 14 13 12 11 10
07 06 05 04 03 02 01 00
shift right by (n*8), then mask the board
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
n7 n6 n5 n4 n3 n2 n1 n0
n = x
m = 7 - y
70 60 50 40 30 20 10 00
71 61 51 41 31 21 11 01
72 62 52 42 32 22 12 02
73 63 53 43 33 23 13 03
74 64 54 44 34 24 14 04
75 65 55 45 35 25 15 05
76 66 56 46 36 26 16 06
77 67 57 47 37 27 17 07
shift right by n, then mask the board
-- -- -- -- -- -- -- n0
-- -- -- -- -- -- -- n1
-- -- -- -- -- -- -- n2
-- -- -- -- -- -- -- n3
-- -- -- -- -- -- -- n4
-- -- -- -- -- -- -- n5
-- -- -- -- -- -- -- n6
-- -- -- -- -- -- -- n7
multiply by
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
n0 -- -- -- -- -- -- --
n1 n0 -- -- -- -- -- --
n2 n1 n0 -- -- -- -- --
n3 n2 n1 n0 -- -- -- --
n4 n3 n2 n1 n0 -- -- --
n5 n4 n3 n2 n1 n0 -- --
n6 n5 n4 n3 n2 n1 n0 --
-------------------------overflow
n7 n6 n5 n4 n3 n2 n1 n0
-- n7 n6 n5 n4 n3 n2 n1
-- -- n7 n6 n5 n4 n3 n2
-- -- -- n7 n6 n5 n4 n3
-- -- -- -- n7 n6 n5 n4
-- -- -- -- -- n7 n6 n5
-- -- -- -- -- -- n7 n6
-- -- -- -- -- -- -- n7
shift right by 56
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
n7 n6 n5 n4 n3 n2 n1 n0
n ≡ (y - x) (mod 8)
(n >> 3 may be any number)
m = x
07 16 25 34 43 52 61 70
77 06 15 24 33 42 51 60
67 76 05 14 23 32 41 50
57 66 75 04 13 22 31 40
47 56 65 74 03 12 21 30
37 46 55 64 73 02 11 20
27 36 45 54 63 72 01 10
17 26 35 44 53 62 71 00
rotate right by (n*8), then mask the board
n7 -- -- -- -- -- -- --
-- n6 -- -- -- -- -- --
-- -- n5 -- -- -- -- --
-- -- -- n4 -- -- -- --
-- -- -- -- n3 -- -- --
-- -- -- -- -- n2 -- --
-- -- -- -- -- -- n1 --
-- -- -- -- -- -- -- n0
multply by
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
n7 -- -- -- -- -- -- --
n7 n6 -- -- -- -- -- --
n7 n6 n5 -- -- -- -- --
n7 n6 n5 n4 -- -- -- --
n7 n6 n5 n4 n3 -- -- --
n7 n6 n5 n4 n3 n2 -- --
n7 n6 n5 n4 n3 n2 n1 --
-------------------------overflow
n7 n6 n5 n4 n3 n2 n1 n0
-- n6 n5 n4 n3 n2 n1 n0
-- -- n5 n4 n3 n2 n1 n0
-- -- -- n4 n3 n2 n1 n0
-- -- -- -- n3 n2 n1 n0
-- -- -- -- -- n2 n1 n0
-- -- -- -- -- -- n1 n0
-- -- -- -- -- -- -- n0
shift right by 56
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
n7 n6 n5 n4 n3 n2 n1 n0
mask by M
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
rotated right by n
n ≡ (y + x - 7) (mod 8)
(n >> 3 may be any number)
m = x
77 66 55 44 33 22 11 00
67 56 45 34 23 12 01 70
57 46 35 24 13 02 71 60
47 36 25 14 03 72 61 50
37 26 15 04 73 62 51 40
27 16 05 74 63 52 41 30
17 06 75 64 53 42 31 20
07 76 65 54 43 32 21 10
rotate right by (n*8), then mask the board
-- -- -- -- -- -- -- n0
-- -- -- -- -- -- n1 --
-- -- -- -- -- n2 -- --
-- -- -- -- n3 -- -- --
-- -- -- n4 -- -- -- --
-- -- n5 -- -- -- -- --
-- n6 -- -- -- -- -- --
n7 -- -- -- -- -- -- --
multply by
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
-- -- -- -- -- -- -- n0
-- -- -- -- -- -- n1 n0
-- -- -- -- -- n2 n1 n0
-- -- -- -- n3 n2 n1 n0
-- -- -- n4 n3 n2 n1 n0
-- -- n5 n4 n3 n2 n1 n0
-- n6 n5 n4 n3 n2 n1 n0
-------------------------overflow
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 --
n7 n6 n5 n4 n3 n2 -- --
n7 n6 n5 n4 n3 -- -- --
n7 n6 n5 n4 -- -- -- --
n7 n6 n5 -- -- -- -- --
n7 n6 -- -- -- -- -- --
n7 -- -- -- -- -- -- --
shift right by 56
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
n7 n6 n5 n4 n3 n2 n1 n0
mask by
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
rotated left by n
n = y
m = x
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
n7 n6 n5 n4 n3 n2 n1 n0
shift left by (n*8)
77 76 75 74 73 72 71 70
67 66 65 64 63 62 61 60
57 56 55 54 53 52 51 50
47 46 45 44 43 42 41 40
37 36 35 34 33 32 31 30
27 26 25 24 23 22 21 20
17 16 15 14 13 12 11 10
07 06 05 04 03 02 01 00
n = x
m = 7 - y
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
n7 n6 n5 n4 n3 n2 n1 n0
multply by
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
-- n7 n6 n5 n4 n3 n2 n1
-------------------------overflow
n0 -- n7 n6 n5 n4 n3 n2
n1 n0 -- n7 n6 n5 n4 n3
n2 n1 n0 -- n7 n6 n5 n4
n3 n2 n1 n0 -- n7 n6 n5
n4 n3 n2 n1 n0 -- n7 n6
n5 n4 n3 n2 n1 n0 -- n7
n6 n5 n4 n3 n2 n1 n0 --
n7 n6 n5 n4 n3 n2 n1 n0
mask board, then shift right by (7-n)
70 60 50 40 30 20 10 00
71 61 51 41 31 21 11 01
72 62 52 42 32 22 12 02
73 63 53 43 33 23 13 03
74 64 54 44 34 24 14 04
75 65 55 45 35 25 15 05
76 66 56 46 36 26 16 06
77 67 57 47 37 27 17 07
n ≡ (y - x) (mod 8)
(n >> 3 may be any number)
m = x
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
n7 n6 n5 n4 n3 n2 n1 n0
multply by
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
mask board, then rotate left by (n*8)
07 16 25 34 43 52 61 70
77 06 15 24 33 42 51 60
67 76 05 14 23 32 41 50
57 66 75 04 13 22 31 40
47 56 65 74 03 12 21 30
37 46 55 64 73 02 11 20
27 36 45 54 63 72 01 10
17 26 35 44 53 62 71 00
n ≡ (y + x + 7) (mod 8)
(n >> 3 may be any number)
m = x
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
n7 n6 n5 n4 n3 n2 n1 n0
multply by
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
n7 n6 n5 n4 n3 n2 n1 n0
mask board, then rotate left by (n*8)
77 66 55 44 33 22 11 00
67 56 45 34 23 12 01 70
57 46 35 24 13 02 71 60
47 36 25 14 03 72 61 50
37 26 15 04 73 62 51 40
27 16 05 74 63 52 41 30
17 06 75 64 53 42 31 20
07 76 65 54 43 32 21 10
C言語の記法を用いる．
black，whiteを，列上に既にある着手する側の駒と相手側の駒をそれぞれ表す，8bitの値とする．OutFlank[8][64]とFlipped[8][137]という二つの配列を用いる．それぞれの配列には，8bitの値が入っている．
OutFlank[i][L]において，L'=0・L・0として8bit数L'を6bit数Lを元に定義すると，L'iの左側にある連続する1の直ぐ左にある0および，L'iの右側にある連続する1の直ぐ右にある0の位置だけが1であるような8bit数が格納されている（L'の左右端は最終的な出力に関係ないので端折っている）．tmp = outFlank[i][(white >> 1) & 63] & blackという風にすると，相手の駒を挟んでいる自分の駒の位置を取得できる．
flipped[i][tmp]に，i番目のビットとtmpの中で1になっているビットに挟まれたビットだけを1とした値を格納することで，どの駒がひっくり返るかを取得できる．tmpは最大でも二進で10001000なので，配列サイは137でよい．
今回は最終的にかなり姑息な実装に行き着いたが，どうするのが綺麗かと考えたことを書いておく．
minimax法やαβ法などで探索するのは木構造である．すなわち，根と葉があり，葉に辿り着いたら評価関数を走らせて，葉以外のノードでは各子ノードの評価結果を元に自らの評価結果を生成する．探索時にdepthを指定することがあるが，これも完全なゲーム木について根からdepth以内の距離にあるノードだけを持つ部分木を作った上で，その部分木について探索していると考えることができる．盤面から木構造を生成し深さが一定の部分木を生成するという構造は遅延評価を用いれば直接実装可能ではあるが，深さ優先探索を行った場合に，普通なら探索が済んだノードは即座にスタックから破棄されるが，遅延評価で木を作るような実装ならおそらく木の破棄がGC任せとなり，あまり実用的では無さそうである．そのかわりに，探索関数の引数としてdepthを引き回して，depthが0なら葉であるかのように動作するようにするごく普通の実装をするのが良い．
リバーシでは，葉であるノード，すなわちゲームが終了した状態というのは，自分も相手も打つ手がない場合として定義される．一方，自分にとって打つ手が無いが相手に打つ手がある状態は，パスという一つの遷移が存在すると扱われる．このような木構造の探索としてプログラムを書くのが，他のゲームへの一般化なども考えた場合に一番適切だと思われるが，実際にはオセロの探索は自分に打つ手がない場合にも常にパスという遷移があるとして実装しても，結局どこかの深さで探索は打ち切られるしパスを繰り返しても盤面は変化しないので，正常に動作する．
minimax法やαβ法で，葉以外のノードにおいて各子ノードの評価結果を元に評価結果を得る際に，関数型プログラミングfoldを使うことになる．ノードの評価値は，評価関数の返り値の最大値や最小値が決まっていない場合には，maxやminに対して半群となる．実際には，最大値や最小値を決め打ちにできるためモノイドとみなさせるが，例えば評価結果が最大となるのはどこに打った場合かを覚えておくために，評価値と着手のタプルについて処理するようにすれば，やはり畳み込む対象はモノイドではなく半群となる．df-pnなどの，他のDFSによるアルゴリズムの際にも，同じように半群となるような何らかの特徴値の畳み込みと考えられそうである（他のアルゴリズムを理解していないので自信は無いが）．（一方，Move-Orderingはpriority queueというモノイドに対する畳込みか）
半群であるならば，foldを用いる際の初期値として取りあえず零元を使うということができないため，全ての子ノードについて畳み込む処理が行いづらい．ここで，Maybe型で包むことでモノイドとみなせるようにするか（Edward Kmett氏によるHaskellのSemigroupsパッケージはまさにそういうことをしている），foldr1のように，1つ以上の要素が存在することを前提とした関数を使うかという選択肢が存在する．後者の場合，現在の盤面からの遷移が有るか無いかを予め確かめる必要があり，これはリバーシの場合は何とかなるかもしれないが一般のゲームにおいてはコストが大きい処理に成り得る．また，前者のMaybeでくるむというアプローチは手続き型言語と比べて一見無駄なことをしているように感じられるが，実際のところ手続き型言語でもループの内部で「ループの中身を初めて実行しているのかどうか」を表す変数を用いて分岐するということは普通に行われるため，本質的な差は無いと考えられる．なので，前者のアプローチの方が一般的にはより良いと考えられる．このプログラムでは，アドホックな実装でお茶を濁している．
また，ループが存在するゲームだと，DFSだと問題が生じうる．同一局面が何度も生じた場合引き分けとなるゲームが多いが，その場合局面の履歴を元に引き分け判定をしなければならず，また将棋では連続王手の千日手は負けというルールがあるので詰将棋の探索においても問題となる．履歴も含めた上で盤面の状態とすれば当然解決はするだろうが，リソースを無駄遣いするので現実的ではない．一般のゲームではこうした問題の対処も必要だが，リバーシでは関係ないので特に考慮していない．
このプログラムでは置換表を使用していないが，置換表について考えたとこも書いておく．
一般に置換表が役立つのは，
- 余分な合流する探索を端折る
- ループの検出
- 正確なMove-Ordering
である．
合流する探索を端折れるメリットは自明であり，ループはリバーシの場合は関係ない．
Move-Orderingについては，
- より深い読みによる精度向上
- 置換表に入っているのは枝狩りされていないため，良い手であると推測できる
- 移動した後の盤面が置換表に入っている場合も良いが，移動前の盤面が置換表に入っていてその盤面からの最善手が移動後の盤面であると確定している場合はさらに良い
- ただし，枝狩りがあるので最善手が読まれるノードは多くは無さそう
- 具体的な手を置換表に入れなければならない（最善手だけならたかだか1byteなので悪くはないのかも？）
といったメリットを得られる．
置換表に入っているノードの情報が，どの程度の深さの探索によって得られものなのかを保持するかどうかという問題がある．Edaxのようにパラメータの組み合わせで決まる様々な深さで探索する場合は，同じノードを違う深さの探索で辿ることが起こりえるため，置換表に入っているのが浅い探索の結果なら無視して，深い探索の結果なら採用するという風にするために，深さを保持するのは有用である．一方，vsOtha，Thellでは決まった反復深化+深さが決め打ちされた二枚の置換表という実装で，深さは入っていない（ような気はするが自信無い）．
リバーシだと，何も考えずに評価関数を作ると，局面の進行具合に応じて評価関数の値の平均が変わることが起こりかねない．この場合異なる深さの読みを比較できなくなってしまう．リバーシは単調に駒の総和が増える方向に局面が変化していくという特徴があるかあ，異なる深さの読みを比較しないという前提で，こんな実装も可能であるが，いずれにせよ将棋などを考えるとよろしくない．
浅い探索によるMove-Orderingや，置換表は，深さ優先探索をある程度SSS*のような最良探索アルゴリズムに近づける試みとも捉えられるという印象を受ける．実際，MTD-fは置換表が完全に機能した場合最良探索アルゴリズムと等価であるようである．
Edaxでは，着手によってひっくり返る駒を取得する処理などは，着手位置ごとに必要最小限の処理だけを行うように最適化された計64個の関数が機械的に生成されて，配列に関数ポインタを入れてジャンプするようになっていた（64個の関数をべたっと定義するのはC言語では致し方なくとも，その後はインライン展開と定数畳み込みによってコンパイラに自動的に最適化させるように書けばいいとは感じたが）．一方，このような実装では，行き先が予測しづらいジャンプによって発生するストールのオーバーヘッド，メモリ使用量が増えることによるキャッシュミスという問題が発生しうる．他にも同様の最適化は随所で為されている．
速度的にどうなるのかは測定していないため分からないが，高速になるからEdaxはわざわざ複雑なことをしているのだろうし，キャッシュミスが多発することが無ければ速くはなりそうという印象は何となく受けた．普通のプログラムでここまで無理するのはどうかと思うが，とにかく速く動かしたいアプリケーションにおいては有用なのかなあと感じた．