2048 の AI を読んでみた

以前第一回2048AIコンテスト 結果報告という記事を見かけて,興味がわいたので 2048 の AI について調べてみました. 2048 は 4x4 のパズルゲームで,ルールは実際にやってもらったほうが分かりやすいぐらい簡単なものですが,テンポが良くて結構ハマりました. 今回は公開されている 2048 の AI の中で一番メジャーっぽいものを TokyoVim #19 で読んでみました.

ov3y/2048-AI - Github

小並感

平穏な感じ AI でした. js/grid.js に各評価関数の定義があり,js/ai.js に探索を行うメインの部分の処理があります.

評価関数

良い手を選ぶには,ある盤面が与えられたときにその盤面がどれだけ有利な状態かを知る必要があります.それを知るために必要なのが評価関数で,今回だと 2048 の 4x4 の盤面を引数に取り,その盤面のスコアを返すものになります.

概要

評価関数 eval(grid) は次のようになっています

eval(grid) = smoothness(grid) * 0.1
                + monotonicity(grid) * 1.0
                + log(emptyCells(grid)) * 2.7
                + maxValue(grid) * 1.0

盤面の有利さを表す指標として smoothnessmonotonicityemptyCellsmaxValue の4種類があり,それにかけられている重みや対数関数はチューニングした結果のようです.

それぞれの指標の意味について説明していきます.

emptyCells(grid)

関数名からも分かるように,盤面上のタイルが存在しない空きセルの数です.

maxValue(grid)

盤面上のタイルの値のうち,最大の値に底が2の対数を取って返します.対数を取っているのは,2048 はタイルの値が 2 の累乗倍で大きくなっていくためです.

smoothness(grid)

smoothness は盤面上の各タイルの値が,スライドした時に隣り合うタイルの値とどれだけ離れているかを示す指標です. スライドさせて隣り合った2つのタイルの値が離れていれば離れているほど,その2枚のタイルが同じ値になって1つのタイルに合体するのは困難になります.

アルゴリズムトップダウンから見ていくとこんな感じです.

smoothness = 0
for タイル in 盤面
    for 向き in [上向き, 右向き]
        smoothness -= abs(value(タイル) - value('向き'の方向にスライドした方向に隣接するタイル))
    endfor
endfor
return smoothness

各タイルごとに上向き/右向きに動かした時に隣接するタイルの値と自身の値の絶対値を引いて求めるので,smoothness は負数で 0 に近いほど良い盤面ということになります. なお,value() はタイルの実際の値に底が2の対数を取ったものです. 4方向あるのに2方向しか見ていないのは,4方向でやると例えばタイルAが下方向へスライドしてタイルBに隣接するのとタイルBが上方向にスライドしてタイルAに隣接するのは意味が同じだからです.

|8|2|2| |
| |4|4| |
| |2|2|2|
|2|2| | |

例えばこの盤面で左下の2に着目して上方向にスライドした場合,その方向に隣り合うのは 8 なので log(8) - log(2) = 2 だけ smoothness が差し引かれます.

monotonicity(grid)

monotonicity(単調性)は隣り合う2つの列/行のそれぞれの隣り合うタイルの値がどれぐらい離れているかを示した指標です. この指標では,上下左右のそれぞれの方向について monotonicity を出して

monotonicity =
        max(右方向のmonotonicity, 左方向のmonotonicity)
      + max(上方向のmonotonicity, 下方向のmonotonicity)

という式によって最終的な値を算出します.

それぞれの方向の monotonicity の計算については一般的な説明が難しいので例を出して雰囲気を説明します.

まず上下左右4方向についてそれぞれの monotonicity を入れるための配列を用意します.

初期値は次のとおりです.それぞれの要素は [上, 下, 左, 右] を表します.

monotonicities = [0, 0, 0, 0]

現在の盤面が以下の盤面だった時の計算方法を説明します.

|8|2|2| |
| |4|4| |
| |2|2|2|
|2|2| | |

まず,今までと同様に各タイルの値に底が 2 の対数を取ります.(この時,空のセルは値 1 とします)

|3|1|1|0|
|0|2|2|0|
|0|1|1|1|
|1|1|0|0|

上記の盤面で一番左 3001 の列とその右隣の列 1211 に着目します. 2つの列の各行ごとの値を見ていきます.

  1. 1行目 (3, 1) を見ると 3>1 なので,左方向に 1-3 が可算され,[0, 0, -2, 0] になります
  2. 2行目 (0, 2) を見ると 2>0 なので,右方向に 0-2 が可算され,[0, 0, -2, -2] になります
  3. 3行目 (0, 1) を見ると 1>0 なので,左方向に 0-1 が可算され,[0, 0, -2, -3] になります
  4. 4行目 (1, 1) を見ると 1=1 なので,配列の値は変わりません.

隣り合う2組の列ごとに行っていきます.これで monotonicities の第2要素と第3要素の値が求まります.

さらに,同じ要領で隣り合う2組の各行ごとに各列の値を見ていくことで,monotonicities の第0要素と第1要素を求めます.

上記で説明したように,最終的に

max(monotonicities[0], monotonicities[1]) + max(monotonicities[2], monotonicities[3])

を計算し,これが monotonicity(grid) の評価値になります.monotonicities の各要素はすべて 0 以下の整数なので,0 が一番良い値ということになります.

検索アルゴリズム

上記で説明した評価関数を使って,4方向のうちどの方向にスライドするのが一番良いかを判断し選択します. 検索アルゴリズムにはアルファ・ベータ法を使っています.

上記日本語記事の模擬コードのうち,node が現在の盤面,child が現在の盤面から4方向に動かした結果の盤面4つ,depth が 何手先まで読むかをそれぞれ表しています.

アルファ・ベータ法にはプレイヤーのターンと相手側のターンがあり,相手側のターンのときは 2048 に達する手が見つかるか,一定の深さ(2048 では深さd = d 手先)まで計算したら終了します. 2048 では,内部的にはプレイヤーがタイルをスライドした後に相手ターンがあるようです. プレイヤーターン中では,計算したスコアが最悪値 -10000 に達するか最良値 10000 に達するか一定の深さまで計算したら終了,相手ターン中では,現在の盤面の次の盤面で 2 か 4 のタイルが新たに挿入されるのも考慮して,計算したスコアが最良値 10000 に達するか一定の深さまで計算したら終了となります.

アルファ・ベータ法を現在の盤面から4方向に動かしたそれぞれの盤面に適用して,一番良いスコアを得られた方向を採用します. 100 ms の時間制限の中で深さを 1 ずつ増やしながら探索を行い,一番深くもぐれたときのスコアをベストスコアとします.

2048-AI の AutoRun ボタンでは繰り返しベストスコアを求めて盤面を進めていき,2048 になったら終了します. Hint ボタンでは現在の盤面に対してのみベストスコアを求め,ベストスコアが出た方向をヒントとして表示しています.