スマートフォン・タブレットからインターネットサーバーオペレーション
APPW.jp
JavaScript リバーシとアルファベータ法探索のシンプル実装
JavaScript によるリバーシとアルファベータ法探索アルゴリズムのシンプルな実装を試してみることにしました。
リバーシの実装部分は、Google 検索の 「javascript リバーシ」などの結果から、いくつかのサイトのサンプルコードを参照させていただいています。また、アルファベータ法については、アルファ・ベータ法 - Wikipedia を参考にしています。
評価値については、石を打つ位置をもとにして評価値テーブルを作成しています。ただ、ゲーム前半で勝負が見えてしまうことが多かったので、テーブルを前半用と後半用に分けてみました。決して強くはないのですが、ゲーム中盤までは手堅さがみられるようになりました。ゲーム終盤は、評価値にゲームスコア（石の数）をそのまま使用してみています。
また、ゲーム中盤まで、それぞれの局面で石の置ける位置の数とひっくり返す石の数を割合にして評価値に組み入れてみています。勝負をゲーム終盤に持ち込むことが多くなりました。また、ゲーム終盤でどれだけ多くの石をひっくり返せるか、あるいは、リードをキープできるか、リバーシのこの面白さも楽しめるようになりました。
勝負強さをみせるには、もっと工夫を盛り込む必要がありそうですが、シンプル実装としては、ここまでとしました。
Loading...
リバーシの実装サンプルコードです。
minimaxPlayer() からが、アルファベータ法の実装となります。コードの掲載は分割していますが、実際には、ひとつの HTML ファイルにスクリプトコードをまとめたあとで実行することになります。
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="utf-8">
<title>リバーシ minimax サンプル</title>
<style>
#rt{
background-color: #000;
}
#rt td{
background-color: #0b0;
text-align: center;
vertical-align: middle;
height: 36px;
width: 36px;
}
.white{
width: 30px;
height: 30px;
background-color: #fff;
border-radius: 50%;
position: relative;
left: 3px;
}
.black{
width: 30px;
height: 30px;
background-color: #000;
border-radius: 50%;
position: relative;
left: 3px;
}
</style>
<script>
var _tbl; //表示盤面
var cells; // 表示盤面データ
var states; // 処理盤面データ
var side; // 0:ゲームエンド, 1: 白, 2: 黒
var weight; // 評価値テーブル
var _turn; // 表示メッセージ
var _move; // 表示メッセージ
var score = []; // ゲームスコア
var timer;
window.onload = function(){
init();
setup();
}
function init(){
// 初期化
cells = new Array(8);
for(var n = 0; n < 8; n++){
cells[n] = new Array(8);
}
states = new Array(10);
for(var n = 0; n < 10; n++){
states[n] = new Array(10);
}
_tbl = document.getElementById("rt");
for(var y = 0; y < cells.length; y++){
for(var x = 0; x < cells[y].length; x++){
cells[y][x] = _tbl.rows[y].cells[x];
cells[y][x].onclick = function(){clicked(this)};
}
}
weight = [[
[2,0,0,0,0,0,0,2],
[0,0,1,1,1,1,0,0],
[0,1,1,1,1,1,1,0],
[0,1,1,0,0,1,1,0],
[0,1,1,0,0,1,1,0],
[0,1,1,1,1,1,1,0],
[0,0,1,1,1,1,0,0],
[2,0,0,0,0,0,0,2]],[
[2,0,1,1,1,1,0,2],
[0,0,1,1,1,1,0,0],
[1,1,1,1,1,1,1,1],
[1,1,1,0,0,1,1,1],
[1,1,1,0,0,1,1,1],
[1,1,1,1,1,1,1,1],
[0,0,1,1,1,1,0,0],
[2,0,1,1,1,1,0,2]]
];
_turn = document.getElementById('turn');
_move = document.getElementById('move');
}
function setup(){
// 初期値設定
for(var n = 0; n < 10; n++){
for(var i = 0; i < 10; i++){
states[n][i] = 0;
}
}
states[4][4] = 1;
states[4][5] = 2;
states[5][4] = 2;
states[5][5] = 1;
for(var y = 0; y < 8; y++){
for(var x = 0; x < 8; x++){
disc(cells[y][x]);
}
}
side = 2;
score[1] = 2;
score[2] = 2;
score[0] = score[1] + score[2];
_turn.innerHTML = '<strong>BLACK</strong> の番です';
_move.innerHTML = '<strong>WHITE</strong> : ' + score[1] + ' , <strong>BLACK</strong> : ' + score[2];
if(side == 2){
// timer = setTimeout(function(){minimaxPlayer();}, 100);
}
}
function disc(cell){
// 石の表示
var x = cell.cellIndex;
var y = cell.parentNode.rowIndex;
if(states[y + 1][x + 1] == 1){
cell.innerHTML = '<div class="white"></div>';
}else if(states[y + 1][x + 1] == 2){
cell.innerHTML = '<div class="black"></div>';
}else if(states[y + 1][x + 1] == 0){
cell.innerHTML = '';
}
}
function clicked(cell){
// 盤面クリック
var x = cell.cellIndex;
var y = cell.parentNode.rowIndex;
if(side == 2){
moved(x, y);
}
}
function gameover(){
// ゲーム終了
clearTimeout(timer);
_turn.innerHTML = (score[1] > score[2] ? '<strong>WHITE</strong> の勝ちです' : score[2] > score[1] ? '<strong>BLACK</strong> の勝ちです' : '引き分けです');
_move.innerHTML = '<strong>WHITE</strong> : ' + score[1] + ' , <strong>BLACK</strong> : ' + score[2];
side = 0;
}
function moved(x, y){
// 石が打たれた
if(states[y+1][x+1] == 0 && canflip(states, side, x, y, true, true) > 0){
side = 3 - side;
if(side != 3){
_turn.innerHTML = (side == 1 ? '<strong>WHITE</strong> の番です' : '<strong>BLACK</strong> の番です');
}
}else{
_move.innerHTML = 'ここには打てません' + ' [' + x +'] [' + y + ']';
}
if(valid(states, side).length == 0){
side = 3 - side;
if(valid(states, side).length == 0){
gameover();
}else{
_move.innerHTML = (side == 2 ? '<strong>WHITE</strong> は ' : '<strong>BLACK</strong> は') + '<strong>PASS</strong> です';
_turn.innerHTML = (side == 1 ? '<strong>WHITE</strong> の番です' : '<strong>BLACK</strong> の番です');
}
}
if(side == 1){
timer = setTimeout(function(){minimaxPlayer();}, 100);
}else if(side == 2){
// timer = setTimeout(function(){minimaxPlayer();}, 100);
}
}
function valid(board, ct){
// 石を打てる位置を調べる
var pos = [];
var u = 0;
for(var x = 0; x < 8; x++){
for(var y = 0; y < 8; y++){
if(board[y+1][x+1] == 0){
u = canflip(board, ct, x, y, false, false);
if(u > 0){
var po = [];
po.push(y, x, u);
pos.push(po);
}
}
}
}
return pos;
}
function canflip(board, ct, x, y, done, disp){
// 石を打てる位置かをチェック
var op = 3 - ct;
var upset = [];
var cnt = 0;
for(var i = 0; i < 9; i++){
var vx = i % 3 - 1;
var vy = Math.floor(i / 3) - 1;
var vc = 0;
if(!(vx == 0 && vy == 0)){
var tx = x + 1 + vx;
var ty = y + 1 + vy;
if(board[ty][tx] == op){
vc = vc + 1;
var can = false;
for(tx += vx, ty += vy; tx > 0 && ty > 0 && tx < 9 && ty < 9; tx += vx, ty += vy){
if(board[ty][tx] == 0){
vc = 0;
break;
}else if(board[ty][tx] == ct){
can = true;
break;
}else{
vc = vc + 1;
}
}
if(can){
cnt = cnt + vc;
if(done && vc > 0){
var dt = [];
dt.push(vy, vx, vc);
upset.push(dt);
}
}
}
}
}
if(done){
doflip(board, ct, x, y, upset, disp, cnt);
}
return cnt;
}
function doflip(board, ct, x, y, dt, dp, cnt){
// 石を返す
// 処理盤面データ
for(var m = 0; m < dt.length; m++){
for(var n = 0; n <= dt[m][2]; n++){
board[y + 1 + n * dt[m][0]][x + 1 + n * dt[m][1]] = ct;
}
}
if(dp){
// 表示盤面
for(var m = 0; m < dt.length; m++){
for(var n = 0; n <= dt[m][2]; n++){
disc(cells[y + n * dt[m][0]][x + n * dt[m][1]]);
}
}
// スコア表示
if(cnt > 0){
score[ct] = score[ct] + cnt + 1;
score[3 - ct] = score[3 - ct] - cnt;
score[0] = score[1] + score[2];
_move.innerHTML = '<strong>WHITE</strong> : ' + score[1] + ' , <strong>BLACK</strong> : ' + score[2];
}
}
}
</script>
</head>
<body>
<table id="rt" cellspacing="2" cellpadding="0">
<tr><td></td><td></td><td></td><td></td>
<td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td>
<td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td>
<td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td>
<td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td>
<td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td>
<td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td>
<td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td>
<td></td><td></td><td></td><td></td></tr>
</table>
<div id="turn"></div>
<div id="move"></div>
<input id="reset" type="button" value="リセット" onclick="setup();">
</body>
</html>
アルファベータ法の実装サンプルコードです。
関数の引き数に配列を使用しているところがあります。通常、引き数は値参照なのですが、引き数に配列を使用したとき、その配列の要素は値渡しとなるため、関数内で引き数の配列はコピーして使用しています。
評価値は、評価値テーブルの参照をもとにしているためか、探索する深度 ( depth ) を想定よりも深くすることができています。しかし、だからといって、深度の深さだけでは、思っていたよりも勝負には強くならないようです。
そのため、ゲーム中盤までは、評価値テーブルの値に深度を掛けて枝ごとに累積し、さらに、石を置ける位置の数と石をひっくり返す数のそれぞれ割合を評価値に加算してみるなどしています。
そして、ゲーム終盤は、深度 ( depth ) アップをいれてみました。
コンピュータ同士の対戦では、双方ともランダムな手をださないためか、同じ結果が繰り返されます。ただ、ゲーム途中で人の入力に切り替えて１手打って、再び対戦をコンピュータ同士に切り替えると結果が変化することがあります。
なお、実行デモは、掲載しているサンプルコードとはブラウザ表示で異なる部分があります。
<script>
function minimaxPlayer(){
var depth = 6;
var choice = [];
var turn = [];
turn.push(score[0], score[1], score[2]);
turn.push(side);
choice = minimax(states, turn, depth);
moved(choice[1], choice[0]);
}
function minimax(board, turn, depth){
var result = [];
var alpha = [-1, -1, Number.NEGATIVE_INFINITY];
var beta = [-1, -1, Number.POSITIVE_INFINITY];
var node = [];
result = alphabeta(board, node, turn, depth, alpha, beta, 0);
return result;
}
function alphabeta(board, node, turn, depth, alpha, beta, t){
var pos = [];
var cnt;
var rc = []; // 戻り値用 (配列)
var cb = []; // 引数 board (配列) コピー用
var un = node.slice(); // 引数 node (配列) コピー
var ut = turn.slice(); // 引数 turn (配列) コピー
var ct = ut[3];
var ua = alpha.slice(); // 引数 alpha (配列) コピー
var ub = beta.slice(); // 引数 beta (配列) コピー
var uw = 0; // 評価値
var hf = 22; // ゲーム中盤
var gf = Math.floor(ut[0] / hf); // 評価値の切り替え
if(node.length > 0){
// 評価値の選択（子ノード）
if(gf > 1){
// ゲーム終盤は石の数
uw = ut[side] + t;
}else{
// ゲーム中盤まで評価値テーブルの値に深度を掛けて枝ごとに累積
uw = weight[gf][un[0]][un[1]] * (depth + 1) + t;
// ゲーム中盤まで石をひっくり返す数の割合を評価値に加算
uw += (1 - un[2] / 10) * (depth + 1);
}
}
// depth がイレギュラー
if(depth < 1 && node.length == 0){
depth = 1;
}
// depth が 0
if(depth == 0){
rc.push(un[0], un[1], uw);
return rc;
}
if(node.length > 0){
// 盤面を進める（子ノード）
cnt = canflip(board, ct, un[1], un[0], true, false);
// サイドチェンジ（子ノード）
ct = 3 - ct;
ut[3] = ct;
}
// ノード が終端ノード
pos = valid(board, ct);
if(pos.length == 0){
if(valid(board, 3 - ct) == 0){
rc.push(un[0], un[1], uw);
return rc;
}
}
// 石を置く位置（初期値）
if(node.length == 0){
ua[0] = pos[0][0];
ua[1] = pos[0][1];
ub[0] = pos[0][0];
ub[1] = pos[0][1];
// ゲーム終盤は深度アップ
if(gf > 1){
if(ut[0] > 46){
depth = 10;
}else{
depth = 8;
}
}
}
// ゲーム中盤まで石を置ける位置の数の割合を評価値に加算
if(gf < 2){
uw += (pos.length / 100) * depth;
}else{
uw = t;
}
// ノード が自分のノード
if(ct == side){
for(var n = 0; n < pos.length; n ++){
// 盤面複写
for(var i = 0; i < 10; i ++){
cb[i] = board[i].slice();
}
// ゲームスコア更新
ut[ct] = turn[ct] + pos[n][2] + 1;
ut[3 - ct] = turn[3 - ct] - pos[n][2];
ut[0] = turn[0] + 1;
// 子ノード探索
rc = alphabeta(cb, pos[n], ut, depth - 1, ua, ub, uw);
// α 値 ( MAX )
if(ua[2] < rc[2]){
ua = [];
ua.push(pos[n][0], pos[n][1], rc[2]);
}
// α ≥ β ( βカット )
if(ua[2] >= ub[2]){
break;
}
}
return ua;
// node が対戦者のノード
}else{
for(var n = 0; n < pos.length; n ++){
// 盤面複写
for(var i = 0; i < 10; i ++){
cb[i] = board[i].slice();
}
// ゲームスコア更新
ut[ct] = turn[ct] + pos[n][2] + 1;
ut[3 - ct] = turn[3 - ct] - pos[n][2];
ut[0] = turn[0] + 1;
// 子ノード探索
rc = alphabeta(cb, pos[n], ut, depth - 1, ua, ub, uw);
// β 値 ( MIN )
if(ub[2] > rc[2]){
ub = [];
ub.push(pos[n][0], pos[n][1], rc[2]);
}
// α ≥ β ( αカット )
if(ua[2] >= ub[2]){
break;
}
}
return ub;
}
}
</script>
ゲーム中盤まで、評価値を枝ごとに累積し、その際に深度で重みを掛け合わせるなどしてみました。
『JavaScript リバーシとアルファベータ法探索のシンプル実装』を公開しました。
