オセロゲームを作ってみました。minMax探索のプログラムを作るのは久しぶりです。
探索はnegaMax
評価関数は、終端は石数、途中は打手可能数＋星＋隅を取ったかどうかってだけのシンプルです。
Unityなので深くは読めないので、５手読みです。
一応ハッシュテーブルも実装しました。
ハッシュでは、ベータカットが発生した場合に、現在のハッシュ値をキーにして、残り探索数と値を格納しています。
negaMaxはAlphaBeta探索と違ってシンプルにコードが書けますが、評価関数の手番違いの処理がややこしいですね(´･ω･｀)
ここがバグってて、しばらく劇弱でした（むしろ負ける手を打ってるだろレベル）
隅がただで打てる場合も打ってこないので、おかしいと思ったんですが(´・ω・`)
オセロ・無料ゲーム - Othello! JAPAN
このサイトの初級には勝てました( ﾟДﾟ)
中級にも勝てた(＾◇＾)
しかし、これってJavaAppletかな？ もしJavaScriptだと勝てても嬉しくないな(´・ω・`)
リバーシ3｜リバーシ｜無料ゲームならワウゲーム
ここのフラッシュの奴に勝てた(＾◇＾)
上級には負けた(´･ω･｀)
強いオセロだと、評価関数を学習させてるんですよね。
終端は真の評価が分かるので、そこから遡るみたいな手法で。
オセロの評価関数の特徴もビットパターンが確立しているし。
オセロの要である石をひっくり返しながら打つ処理
void putKoma(int x, int y, int k) { if (ban[x, y] != (int)koma.empty) Debug.Log("error"); ban[x, y] = k; hash ^= hashTable[ x * y * k * turn ]; reverse(x, y, -1, 0, k);// left reverse(x, y, +1, 0, k);// right reverse(x, y, 0, -1, k);// up reverse(x, y, 0, +1, k);// down reverse(x, y, -1, -1, k);// left up reverse(x, y, +1, -1, k);// right up reverse(x, y, -1, +1, k);// left down reverse(x, y, +1, +1, k);// right down } void reverse(int x, int y, int dx, int dy, int k) { int k2 = reverseKoma(k); if (x + dx <= 0 || x + dx >= 9) return; if (y + dy <= 0 || y + dy >= 9) return; if (ban[x + dx, y + dy] != k2) return; int x0 = x; int y0 = y; while (x0 + dx <= 8 && x0 + dx >= 1 && y0 + dy <= 8 && y0 + dy >= 1 && ban[x0 + dx, y0 + dy] == k2 ) { x0 += dx; y0 += dy; } //research if (ban[x0 + dx, y0 + dy] != k) return; while (x + dx <= 8 && x + dx >= 1 && y + dy <= 8 && y + dy >= 1 && ban[x + dx, y + dy] == k2) { x += dx; y += dy; ban[x, y] = k; hash ^= hashTable[ x * y * k * turn ]; } }
石の色が変わったり、打つ度にhashを更新して、局面の違いを識別できるようにする。
hash ^= hashTable[ x * y * k * turn ];
betaカット発生時に この値の信頼度として、残り探索深さ＝depthMax-depthと値を登録。
例えば残り深さ４で400という値だったとすれば、残り深さ0～４ならば値は400を超えないことが保証される
ただし、残り深さ5では、値が変わる可能性がある（もっと良い値が見つかる。または実は悪いことが分かる）
なので、その場合はこのハッシュは使えない。
if (ret >= beta)
{
HH[hash & 0xffff].hash = hash;
HH[hash & 0xffff].value = beta;
HH[hash & 0xffff].depth = depthMax - depth;
return beta;
}
