ИИ и 2048. Часть 2: Минимакс + альфа-бета отсечение

Я — автор программы, о которой упоминали в этой теме. Вы можете посмотреть ИИ в действии или ознакомиться с кодом.

В настоящее время программа выигрывает примерно в 90% случаев, выполняя java-скрипты в браузере на моем ноутбуке, затрачивая 100 миллисекунд на обдумывание хода, работая хоть и не идеально, но довольно хорошо.

Поскольку игра представляет собой дискретное пространство состояний с полной информацией, по сути являясь пошаговой игрой наподобие шахмат и шашек, я использовал те же методы, которые показали свою работоспособность в этих играх, а именно минимаксный поиск с альфа-бета отсечением. Поскольку по ссылкам приводится много информации об этом алгоритме, я просто расскажу о двух основных эвристиках, которые мной использованы в функции статической оценки и формализующие многие интуитивные предположения, высказываемые здесь другими людьми.

Монотонность

Данная эвристика пытается гарантировать, что все значения плиток либо увеличиваются, либо уменьшаются как влево/вправо, так и вверх/вниз. Одна только эта эвристика отражает ту догадку, о которой упоминали многие другие, что более ценные плитки должны быть сгруппированы в углу. Это, как правило, предотвращает нагромождение менее ценных плиток и держит доску в организованном виде, поскольку меньшие плитки каскадно переходят в бóльшие.

Вот скриншот совершенно монотонной сетки. Я получил это положение, запустив алгоритм с установленной eval-функцией, чтобы игнорировать другие эвристики и учитывать только монотонность.

Плавность (гладкость, ровность)

Вышеприведенная эвристика сама по себе имеет тенденцию создавать структуры, в которых соседние ячейки уменьшаются в стоимости, однако, само собой, для объединения соседи должны иметь одинаковое значение. Поэтому эвристика плавности просто измеряет разницу значений между соседними плитками, стараясь минимизировать их число.

Комментатор на Hacker News дал интересную формализацию этой идеи с точки зрения теории графов.

Вот скриншот совершенно гладкой сетки, любезно предоставленной этим отличным пародийным форком. (ссылка на веб-архив, при этом ява-скрипты на странице работают и Вы с помощью клавиатуры можете сделать ход в любом направлении — примечание переводчика).

Свободные плитки

И, наконец, есть штраф за то, что слишком мало свободных плиток, поскольку варианты могут быстро закончиться, когда игровое поле становится слишком тесным.

И это все! Поиск по игровому пространству при оптимизации этих критериев дает удивительно хорошую производительность. Одним из преимуществ использования обобщенного подхода, подобного этому, а не явно закодированной стратегии перемещения, является то, что алгоритм часто может находить интересные и неожиданные решения. Если вы наблюдаете за его ходом, он часто делает удивительные, но эффективные движения, как, например, внезапную смену стен или углов, вблизи которых он выстраивает свою игру.

Небольшое изменение

Скриншот демонстрирует мощность данного подхода. Я отменил ограничение по значению плиток (чтобы они продолжали расти после достижения значения 2048), и вот лучший результат после восьми испытаний.

Да, это 4096 наряду с 2048. =) Это означает, что он достиг неуловимой плитки 2048 на одной доске.

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
''''''''''''''''''''''''''''''''МИНИМАКС'''''''''''''''''''''''''''''''''
'''''''''''''''''''''''(с альфа-бета отсечением)'''''''''''''''''''''''''
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'Оценка позиции с помощью алгоритма минимакса с альфа-бета-отсечением
'Position - матрица 4 на 4 с плитками на ней
'Depth - глубина, на которую считаем
'Alpha, Beta - динамические границы оценок для максимизирующего и минимизирующего игроков
'MaximisingPlayer - это уровень подсчёта для максимизирующго игрока?
Private Function MiniMaxAlpaBeta_Evaluation(Position As Variant, Depth As Long, _
                                            Alpha As Double, Beta As Double, _
                                            MaximisingPlayer As Boolean, _
                                            Optional MainLevel As Boolean = False) As Double
    
    Dim MaxEval As Double 'Правая граница
    Dim MinEval As Double 'Левая граница
    Dim PositionNext As Variant 'Позиция на следующем ходу игрока
    Dim PositionTemp As Variant 'Позиция на следующем ходу игрока
    Dim Eval As Double 'Оценка текущего узла
    Dim Way As Long 'В каком направлении игрок-человек сдвигает позицию на своём ходе
    Dim Row As Long 'Для перебора строк игрового поля
    Dim Col As Long 'Для перебора столбцов игрового поля
    Dim TileNew As Long 'Размер новой плитки при ходе компьютера
    
    'Если игра завершена (в пользу компьютера, ведь 
	'игрок неизбежно проиграет рано или поздно)
    If GameOverPosition(Position) Then 'Игра в текущей позиции закончена?
        'Присваиваем позиции очень низкую оценку
        MiniMaxAlpaBeta_Evaluation = -1000000 + TileMax(Position) 

    'Если углубление вниз по дереву вариантов далее не предполагается
    ElseIf Depth = 0 Then
        'Оцениваем позицию на достигнутом уровне
        MiniMaxAlpaBeta_Evaluation = StaticEvaluation(Position) 
       
    'Пока ещё играем, рекурсивно оцениваем позицию 
    'с точки зрения максимизирующего игрока (человека)
    ElseIf MaximisingPlayer Then
        MaxEval = -1000000 'Пока что присваиваем позиции минимальную оценку
        For Way = 1 To 4 'Все 4 направления хода игрока-человека (вверх, влево, вправо, вниз)
            ChangeCount = 0 'Пока неизвестно, будут ли изменения на поле
            'Позиция, получаемая после хода в данном направлении
            PositionNext = StepHuman(Position, Way)
            If ChangeCount > 0 Then 'Есть изменения на игровом поле
                'Рекурсивно оцениваем полученную позицию со стороны игрока, 
                'к которому перейдёт ход (компьютера)
                Eval = MiniMaxAlpaBeta_Evaluation(PositionNext, Depth - 1, _
                                                  Alpha, Beta, False)
                If Eval > MaxEval Then MaxEval = Eval 'Уточняем оценку
                'Уточняем границу для максимизирующего игрока
                If Eval > Alpha Then Alpha = Eval 
                'Если ветка заведом менее выгодна, чем те 
                'что уже рассмотрели - отсекаем всю ветку
                If Beta > Alpha Then Exit For 
            End If
        Next
        'Итоговое значение выгоды на данном уровне с учётом вложенных уровней
        MiniMaxAlpaBeta_Evaluation = MaxEval 
        
    'Пока ещё играем, рекурсивно оцениваем позицию 
    'с точки зрения минимизирующего игрока (компьютера)
    Else 'Not MaximisingPlayer
        MinEval = 1000000 'Пока что присваиваем позиции максимальную оценку
        For Row = 1 To 4 'Перебираем все места игрового поля
            For Col = 1 To 4 'Перебираем все места игрового поля
                If Position(Row, Col) = 0 Then 'Если место свободно
                    For TileNew = 2 To 4 Step 2 'Компьютер может поставить или 2 или 4
                        'Позиция, после того как в этом месте 
						'компьютер сгенерировал эту плитку
                        PositionNext = StepComp(Position, Row, Col, TileNew)
                        'Рекурсивно оцениваем позицию со стороны игрока, 
                        'к которому перейдёт ход (человека)
                        Eval = MiniMaxAlpaBeta_Evaluation(PositionNext, Depth - 1, _
                                                          Alpha, Beta, True)
                        If Eval < MinEval Then MinEval = Eval 'Уточняем оценку
                        'Уточняем границу для минимизирующего игрока
                        If Eval < Beta Then Beta = Eval 
                        'Если ветка заведом менее выгодна, чем те
                        'что уже рассмотрели - отсекаем всю ветку
                        If Alpha < Beta Then Exit For 
                    Next
                End If
            Next
        Next
        'Итоговое значение выгоды на данном уровне с учётом вложенных уровней
        MiniMaxAlpaBeta_Evaluation = MinEval 
    End If
 
End Function

function AI(grid) {
  this.grid = grid;
}

//Статическая функция оценки (СФО)
AI.prototype.eval = function() {
  var emptyCells = this.grid.availableCells().length;

  var smoothWeight = 0.1,
      //monoWeight   = 0.0,
      //islandWeight = 0.0,
      mono2Weight  = 1.0,
      emptyWeight  = 2.7,
      maxWeight    = 1.0;

  return this.grid.smoothness() * smoothWeight
       //+ this.grid.monotonicity() * monoWeight
       //- this.grid.islands() * islandWeight
       + this.grid.monotonicity2() * mono2Weight
       + Math.log(emptyCells) * emptyWeight
       + this.grid.maxValue() * maxWeight;
};

// alpha-beta depth first search
AI.prototype.search = function(depth, alpha, beta, positions, cutoffs) {
  var bestScore;
  var bestMove = -1;
  var result;

  // the maxing player
  if (this.grid.playerTurn) {
    bestScore = alpha;
    for (var direction in [0, 1, 2, 3]) {
      var newGrid = this.grid.clone();
      if (newGrid.move(direction).moved) {
        positions++;
        if (newGrid.isWin()) {
          return { move: direction, score: 10000, positions: positions, cutoffs: cutoffs };
        }
        var newAI = new AI(newGrid);

        if (depth == 0) {
          result = { move: direction, score: newAI.eval() };
        } else {
          result = newAI.search(depth-1, bestScore, beta, positions, cutoffs);
          if (result.score > 9900) { // win
            result.score--; // to slightly penalize higher depth from win
          }
          positions = result.positions;
          cutoffs = result.cutoffs;
        }

        if (result.score > bestScore) {
          bestScore = result.score;
          bestMove = direction;
        }
        if (bestScore > beta) {
          cutoffs++
          return { move: bestMove, score: beta, positions: positions, cutoffs: cutoffs };
        }
      }
    }
  }

  else { // computer's turn, we'll do heavy pruning to keep the branching factor low
    bestScore = beta;

    // try a 2 and 4 in each cell and measure how annoying it is
    // with metrics from eval
    var candidates = [];
    var cells = this.grid.availableCells();
    var scores = { 2: [], 4: [] };
    for (var value in scores) {
      for (var i in cells) {
        scores[value].push(null);
        var cell = cells[i];
        var tile = new Tile(cell, parseInt(value, 10));
        this.grid.insertTile(tile);
        scores[value][i] = -this.grid.smoothness() + this.grid.islands();
        this.grid.removeTile(cell);
      }
    }

    // now just pick out the most annoying moves
    var maxScore = Math.max(Math.max.apply(null, scores[2]), Math.max.apply(null, scores[4]));
    for (var value in scores) { // 2 and 4
      for (var i=0; i<scores[value].length; i++) {
        if (scores[value][i] == maxScore) {
          candidates.push( { position: cells[i], value: parseInt(value, 10) } );
        }
      }
    }

    // search on each candidate
    for (var i=0; i<candidates.length; i++) {
      var position = candidates[i].position;
      var value = candidates[i].value;
      var newGrid = this.grid.clone();
      var tile = new Tile(position, value);
      newGrid.insertTile(tile);
      newGrid.playerTurn = true;
      positions++;
      newAI = new AI(newGrid);
      result = newAI.search(depth, alpha, bestScore, positions, cutoffs);
      positions = result.positions;
      cutoffs = result.cutoffs;

      if (result.score < bestScore) {
        bestScore = result.score;
      }
      if (bestScore < alpha) {
        cutoffs++;
        return { move: null, score: alpha, positions: positions, cutoffs: cutoffs };
      }
    }
  }

  return { move: bestMove, score: bestScore, positions: positions, cutoffs: cutoffs };
}

// performs a search and returns the best move
AI.prototype.getBest = function() {
  return this.iterativeDeep();
}

// performs iterative deepening over the alpha-beta search
AI.prototype.iterativeDeep = function() {
  var start = (new Date()).getTime();
  var depth = 0;
  var best;
  do {
    var newBest = this.search(depth, -10000, 10000, 0 ,0);
    if (newBest.move == -1) {
      break;
    } else {
      best = newBest;
    }
    depth++;
  } while ( (new Date()).getTime() - start < minSearchTime);
  return best
}

AI.prototype.translate = function(move) {
 return {
    0: 'up',
    1: 'right',
    2: 'down',
    3: 'left'
  }[move];
}

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'''''''''''''''''''''''СТАТИЧЕСКАЯ ФУНКЦИЯ ОЦЕНКИ''''''''''''''''''''''''
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'Функция статической оценки игрового поля
'Position - матрица 4 на 4 с плитками на ней
Private Function StaticEvaluation(Position As Variant) As Double

    Dim Smoothness As Double 'Плавность
    Dim Monotonicity As Double 'Монотонность
    Dim EmptyCount As Double 'Свободное пространство
    Dim MaxValue As Long 'Максимальное значение

    'Вес каждой составляющей
    Const SmoothWeight = 0.1
    Const MonoWeight = 1
    Const EmptyWeight = 2.7
    Const MaxWeight = 1
    
    Dim k As Long 'Перебор в цикле
    Dim i As Long 'Перебор строк
    Dim j  As Long 'Перебор столбцов
    Dim x As Long 'Перебор строк
    Dim y As Long 'Перебор столбцов

    'Плавность
    Dim Value As Double 'Значение текущей ячейки в рамках избранной метрики
    'Значение следущей за текущей ячейки в рамках избранной метрики
    Dim TargetValue As Double 
    Smoothness = 0 'Пока плавность не подсчитана
    For i = 1 To 4 'Перебираем по строкам игровое поле
        For j = 1 To 4 'Перебираем по столбцам игровое поле
            If Position(i, j) > 0 Then 'Если непустая ячейка
                Value = Log(Position(i, j)) / Log(2)
                If i < 4 Then 'Если внизу от ячейки есть ещё место
                    For x = i + 1 To 4 'Посмотрим вниз от ячейки
                        If Position(x, j) > 0 Then 'Ближайшее непустое поле снизу
                            'Значение в избранной метрике
                            TargetValue = Log(Position(x, j)) / Log(2) 
                            'Разница, характеризующая плавность
                            Smoothness = Abs(Value - TargetValue) 
                            'После ближайшего пустого поля ячейки не нужны
                            Exit For 
                        End If
                    Next
                End If
                If j < 4 Then 'Если внизу от ячейки есть ещё место
                    For y = j + 1 To 4 'Посмотрим вправо от ячейки
                        If Position(i, y) > 0 Then 'Ближайшее непустое поле справа
                            'Значение в избранной метрике
                            TargetValue = Log(Position(i, y)) / Log(2) 
                            'Разница, характеризующая плавность
                            Smoothness = Abs(Value - TargetValue) 
                            'Вслед за ближайшим пустым полем ячейки не нужны
                            Exit For 
                        End If
                    Next
                End If
            End If
        Next
    Next
    
    'Монотонность
    Dim arrTotals(1 To 4) As Double 'Счёт монотонности для каждого направления
    Dim Current As Long 'Номер текущей ячейки
    Dim Next_ As Long 'Номер следующей непустой ячейки после текущей
    Dim CurrentValue As Double 'Значение текущей ячейки в выбранной метрике
    Dim NextValue As Double 'Значение следующей за текущей ячейки в выбранной метрике
    
    Monotonicity = 0 'Монотонность пока не вычислили
    
    'Обнулим массив монотонности по всем направлениям
    For k = 1 To 4
        arrTotals(k) = 0
    Next
    'Монотонность сверху-вниз и снизу-вверх
    For x = 1 To 4 'Перебираем по строкам
        Current = 1 'В строке начинаем с первой ячейки
        'Следующая за текущей (в данный момент первой в строке) ячейкой
        Next_ = Current + 1 
        Do While Next_ <= 4 'Пока следующая ячейка в пределах игрового поля
            'Следующую за текущей ячейку ищем непустую
            '(между ней и текущей могут быть пустые клетки)
            Do While Next_ <= 4 'Пока следующая ячейка в пределах игрового поля
                If Position(x, Next_) = 0 Then 'Если пустая ячейка в ряду
                    Next_ = Next_ + 1 'Переходим к следующей
                Else 'Если НЕ-пустая ячейка в ряду
                    Exit Do 'Нашли то, что искали, прерываем цикл
                End If
            Loop
            'Если вышли за пределы игрового поля то шаг назад
            If Next_ > 4 Then Next_ = 4 
            'Значения для текущей и следующей непустой ячейки в выбранной метрике
            If Position(x, Current) > 0 Then
                CurrentValue = Log(Position(x, Current)) / Log(2)
            Else
                CurrentValue = 0
            End If
'            MsgBox "Position[" & x & ", " & Next_ & "]=" & Position(x, Next_)
            If Position(x, Next_) > 0 Then
                NextValue = Log(Position(x, Next_)) / Log(2)
            Else
                NextValue = 0
            End If
            If CurrentValue > NextValue Then 'Наблюдается убывание сверху вниз?
                arrTotals(Up) = arrTotals(Up) + NextValue - CurrentValue
            ElseIf NextValue > CurrentValue Then 'Наблюдается убывание снизу вверх?
                arrTotals(Down) = arrTotals(Down) + CurrentValue - NextValue
            End If
            Current = Next_ 'Следующая непустая за текущей становится сама текущей
            Next_ = Next_ + 1 'Следующая за новой текущей
        Loop
    Next
    'К монотонности привосокупляем большее значение из сверху-вниз и снизу-вверх
    Monotonicity = IIf(arrTotals(Up) >= arrTotals(Down), _
                   Monotonicity + arrTotals(Up), _
                   Monotonicity + arrTotals(Down))

    'Монотонность слева-направо и справа-налево
    For y = 1 To 4 'Перебираем по столбцам
        Current = 1 'В столбце начинаем с первой ячейки
        'Следующая за текущей (в данный момент первой в столбце) ячейкой
        Next_ = Current + 1 
        Do While Next_ <= 4 'Пока следующая ячейка в пределах игрового поля
            'Следующую за текущей ячейку ищем непустую
            '(между ней и текущей могут быть пустые клетки)
            Do While Next_ <= 4 'Пока следующая ячейка в пределах игрового поля
                If Position(Next_, y) = 0 Then 'Если пустая ячейка в ряду
                    Next_ = Next_ + 1 'Переходим к следующей
                Else 'Если НЕ-пустая ячейка в ряду
                    Exit Do 'Нашли то, что искали, прерываем цикл
                End If
            Loop
            'Если вышли за пределы игрового поля то шаг назад
            If Next_ > 4 Then Next_ = 4 
            'Значения для текущей и следующей непустой ячейки в выбранной метрике
            If Position(Current, y) > 0 Then
                CurrentValue = Log(Position(Current, y)) / Log(2)
            Else
                CurrentValue = 0
            End If
            If Position(Next_, y) > 0 Then
                NextValue = Log(Position(Next_, y)) / Log(2)
            Else
                NextValue = 0
            End If
            If CurrentValue > NextValue Then 'Наблюдается убывание сверху вниз?
                arrTotals(Left) = arrTotals(Left) + NextValue - CurrentValue
            ElseIf NextValue > CurrentValue Then 'Наблюдается убывание снизу вверх?
                arrTotals(Right) = arrTotals(Right) + CurrentValue - NextValue
            End If
            Current = Next_ 'Следующая непустая за текущей становится сама текущей
            Next_ = Next_ + 1 'Следующая за новой текущей
        Loop
    Next
    'К монотонности привосокупляем большее значение из справа-налево и слева-направо
    Monotonicity = IIf(arrTotals(Left) >= arrTotals(Right), _
                   Monotonicity + arrTotals(Left), _
                   Monotonicity + arrTotals(Right))

    'Свободное пространство и максимальная плитка
    EmptyCount = 0 'Пока не подсчитали количество свободных ячеек
    MaxValue = 0 'Пока неизвестно максимальное значение
    For i = 1 To 4 'Перебираем по строкам игровое поле
        For j = 1 To 4 'Перебираем по столбцам игровое поле
            If Position(i, j) = 0 Then 'Если пустая ячейка...
                '... то подсчитываем свободное пространство
                EmptyCount = EmptyCount + 1 
            'Если непустая и больше текущего максимума...
            ElseIf Position(i, j) > MaxValue Then 
                MaxValue = Position(i, j) '... то уточняем максимум
            End If
        Next
    Next
    
    'Итоговое значение функции
    StaticEvaluation = Smoothness * SmoothWeight + _
                       Monotonicity * MonoWeight + _
                       Log_Base_Arg(EmptyCount) * EmptyWeight + _
                       MaxValue * MaxWeight

End Function

function Grid(size) {
  this.size = size;
  this.startTiles   = 2;

  this.cells = [];

  this.build();
  this.playerTurn = true;
}

// pre-allocate these objects (for speed)
Grid.prototype.indexes = [];
for (var x=0; x<4; x++) {
  Grid.prototype.indexes.push([]);
  for (var y=0; y<4; y++) {
    Grid.prototype.indexes[x].push( {x:x, y:y} );
  }
}

// Build a grid of the specified size
Grid.prototype.build = function () {
  for (var x = 0; x < this.size; x++) {
    var row = this.cells[x] = [];

    for (var y = 0; y < this.size; y++) {
      row.push(null);
    }
  }
};


// Find the first available random position
Grid.prototype.randomAvailableCell = function () {
  var cells = this.availableCells();

  if (cells.length) {
    return cells[Math.floor(Math.random() * cells.length)];
  }
};

Grid.prototype.availableCells = function () {
  var cells = [];
  var self = this;

  this.eachCell(function (x, y, tile) {
    if (!tile) {
      //cells.push(self.indexes[x][y]);
      cells.push( {x:x, y:y} );
    }
  });

  return cells;
};

// Call callback for every cell
Grid.prototype.eachCell = function (callback) {
  for (var x = 0; x < this.size; x++) {
    for (var y = 0; y < this.size; y++) {
      callback(x, y, this.cells[x][y]);
    }
  }
};

// Check if there are any cells available
Grid.prototype.cellsAvailable = function () {
  return !!this.availableCells().length;
};

// Check if the specified cell is taken
Grid.prototype.cellAvailable = function (cell) {
  return !this.cellOccupied(cell);
};

Grid.prototype.cellOccupied = function (cell) {
  return !!this.cellContent(cell);
};

Grid.prototype.cellContent = function (cell) {
  if (this.withinBounds(cell)) {
    return this.cells[cell.x][cell.y];
  } else {
    return null;
  }
};

// Inserts a tile at its position
Grid.prototype.insertTile = function (tile) {
  this.cells[tile.x][tile.y] = tile;
};

Grid.prototype.removeTile = function (tile) {
  this.cells[tile.x][tile.y] = null;
};

Grid.prototype.withinBounds = function (position) {
  return position.x >= 0 && position.x < this.size &&
         position.y >= 0 && position.y < this.size;
};

Grid.prototype.clone = function() {
  newGrid = new Grid(this.size);
  newGrid.playerTurn = this.playerTurn;
  for (var x = 0; x < this.size; x++) {
    for (var y = 0; y < this.size; y++) {
      if (this.cells[x][y]) {
        newGrid.insertTile(this.cells[x][y].clone());
      }
    }
  }
  return newGrid;
};

// Set up the initial tiles to start the game with
Grid.prototype.addStartTiles = function () {
  for (var i=0; i<this.startTiles; i++) {
    this.addRandomTile();
  }
};

// Adds a tile in a random position
Grid.prototype.addRandomTile = function () {
  if (this.cellsAvailable()) {
    var value = Math.random() < 0.9 ? 2 : 4;
    //var value = Math.random() < 0.9 ? 256 : 512;
    var tile = new Tile(this.randomAvailableCell(), value);

    this.insertTile(tile);
  }
};

// Save all tile positions and remove merger info
Grid.prototype.prepareTiles = function () {
  this.eachCell(function (x, y, tile) {
    if (tile) {
      tile.mergedFrom = null;
      tile.savePosition();
    }
  });
};

// Move a tile and its representation
Grid.prototype.moveTile = function (tile, cell) {
  this.cells[tile.x][tile.y] = null;
  this.cells[cell.x][cell.y] = tile;
  tile.updatePosition(cell);
};


Grid.prototype.vectors = {
  0: { x: 0,  y: -1 }, // up
  1: { x: 1,  y: 0 },  // right
  2: { x: 0,  y: 1 },  // down
  3: { x: -1, y: 0 }   // left
}

// Get the vector representing the chosen direction
Grid.prototype.getVector = function (direction) {
  // Vectors representing tile movement
  return this.vectors[direction];
};

// Move tiles on the grid in the specified direction
// returns true if move was successful
Grid.prototype.move = function (direction) {
  // 0: up, 1: right, 2:down, 3: left
  var self = this;

  var cell, tile;

  var vector     = this.getVector(direction);
  var traversals = this.buildTraversals(vector);
  var moved      = false;
  var score      = 0;
  var won        = false;

  // Save the current tile positions and remove merger information
  this.prepareTiles();

  // Traverse the grid in the right direction and move tiles
  traversals.x.forEach(function (x) {
    traversals.y.forEach(function (y) {
      cell = self.indexes[x][y];
      tile = self.cellContent(cell);

      if (tile) {
        //if (debug) {
          //console.log('tile @', x, y);
        //}
        var positions = self.findFarthestPosition(cell, vector);
        var next      = self.cellContent(positions.next);

        // Only one merger per row traversal?
        if (next && next.value === tile.value && !next.mergedFrom) {
          var merged = new Tile(positions.next, tile.value * 2);
          merged.mergedFrom = [tile, next];

          self.insertTile(merged);
          self.removeTile(tile);

          // Converge the two tiles' positions
          tile.updatePosition(positions.next);

          // Update the score
          score += merged.value;

          // The mighty 2048 tile
          if (merged.value === 2048) {
            won = true;
          }
        } else {
          //if (debug) {
            //console.log(cell);
            //console.log(tile);
          //}
          self.moveTile(tile, positions.farthest);
        }

        if (!self.positionsEqual(cell, tile)) {
          self.playerTurn = false;
          //console.log('setting player turn to ', self.playerTurn);
          moved = true; // The tile moved from its original cell!
        }
      }
    });
  });

  //console.log('returning, playerturn is', self.playerTurn);
  //if (!moved) {
    //console.log('cell', cell);
    //console.log('tile', tile);
    //console.log('direction', direction);
    //console.log(this.toString());
  //}
  return {moved: moved, score: score, won: won};
};

Grid.prototype.computerMove = function() {
  this.addRandomTile();
  this.playerTurn = true;
}

// Build a list of positions to traverse in the right order
Grid.prototype.buildTraversals = function (vector) {
  var traversals = { x: [], y: [] };

  for (var pos = 0; pos < this.size; pos++) {
    traversals.x.push(pos);
    traversals.y.push(pos);
  }

  // Always traverse from the farthest cell in the chosen direction
  if (vector.x === 1) traversals.x = traversals.x.reverse();
  if (vector.y === 1) traversals.y = traversals.y.reverse();

  return traversals;
};

Grid.prototype.findFarthestPosition = function (cell, vector) {
  var previous;

  // Progress towards the vector direction until an obstacle is found
  do {
    previous = cell;
    cell     = { x: previous.x + vector.x, y: previous.y + vector.y };
  } while (this.withinBounds(cell) &&
           this.cellAvailable(cell));

  return {
    farthest: previous,
    next: cell // Used to check if a merge is required
  };
};

Grid.prototype.movesAvailable = function () {
  return this.cellsAvailable() || this.tileMatchesAvailable();
};

// Check for available matches between tiles (more expensive check)
// returns the number of matches
Grid.prototype.tileMatchesAvailable = function () {
  var self = this;

  //var matches = 0;

  var tile;

  for (var x = 0; x < this.size; x++) {
    for (var y = 0; y < this.size; y++) {
      tile = this.cellContent({ x: x, y: y });

      if (tile) {
        for (var direction = 0; direction < 4; direction++) {
          var vector = self.getVector(direction);
          var cell   = { x: x + vector.x, y: y + vector.y };

          var other  = self.cellContent(cell);

          if (other && other.value === tile.value) {
            return true; //matches++; // These two tiles can be merged
          }
        }
      }
    }
  }

  //console.log(matches);
  return false; //matches;
};

Grid.prototype.positionsEqual = function (first, second) {
  return first.x === second.x && first.y === second.y;
};

Grid.prototype.toString = function() {
  string = '';
  for (var i=0; i<4; i++) {
    for (var j=0; j<4; j++) {
      if (this.cells[j][i]) {
        string += this.cells[j][i].value + ' ';
      } else {
        string += '_ ';
      }
    }
    string += 'n';
  }
  return string;
}

// counts the number of isolated groups. 
Grid.prototype.islands = function() {
  var self = this;
  var mark = function(x, y, value) {
    if (x >= 0 && x <= 3 && y >= 0 && y <= 3 &&
        self.cells[x][y] &&
        self.cells[x][y].value == value &&
        !self.cells[x][y].marked ) {
      self.cells[x][y].marked = true;
      
      for (direction in [0,1,2,3]) {
        var vector = self.getVector(direction);
        mark(x + vector.x, y + vector.y, value);
      }
    }
  }

  var islands = 0;

  for (var x=0; x<4; x++) {
    for (var y=0; y<4; y++) {
      if (this.cells[x][y]) {
        this.cells[x][y].marked = false
      }
    }
  }
  for (var x=0; x<4; x++) {
    for (var y=0; y<4; y++) {
      if (this.cells[x][y] &&
          !this.cells[x][y].marked) {
        islands++;
        mark(x, y , this.cells[x][y].value);
      }
    }
  }
  
  return islands;
}


// measures how smooth the grid is (as if the values of the pieces
// were interpreted as elevations). Sums of the pairwise difference
// between neighboring tiles (in log space, so it represents the
// number of merges that need to happen before they can merge). 
// Note that the pieces can be distant
Grid.prototype.smoothness = function() {
  var smoothness = 0;
  for (var x=0; x<4; x++) {
    for (var y=0; y<4; y++) {
      if ( this.cellOccupied( this.indexes[x][y] )) {
        var value = Math.log(this.cellContent( this.indexes[x][y] ).value) / Math.log(2);
        for (var direction=1; direction<=2; direction++) {
          var vector = this.getVector(direction);
          var targetCell = this.findFarthestPosition(this.indexes[x][y], vector).next;

          if (this.cellOccupied(targetCell)) {
            var target = this.cellContent(targetCell);
            var targetValue = Math.log(target.value) / Math.log(2);
            smoothness -= Math.abs(value - targetValue);
          }
        }
      }
    }
  }
  return smoothness;
}

Grid.prototype.monotonicity = function() {
  var self = this;
  var marked = [];
  var queued = [];
  var highestValue = 0;
  var highestCell = {x:0, y:0};
  for (var x=0; x<4; x++) {
    marked.push([]);
    queued.push([]);
    for (var y=0; y<4; y++) {
      marked[x].push(false);
      queued[x].push(false);
      if (this.cells[x][y] &&
          this.cells[x][y].value > highestValue) {
        highestValue = this.cells[x][y].value;
        highestCell.x = x;
        highestCell.y = y;
      }
    }
  }

  increases = 0;
  cellQueue = [highestCell];
  queued[highestCell.x][highestCell.y] = true;
  markList = [highestCell];
  markAfter = 1; // only mark after all queued moves are done, as if searching in parallel

  var markAndScore = function(cell) {
    markList.push(cell);
    var value;
    if (self.cellOccupied(cell)) {
      value = Math.log(self.cellContent(cell).value) / Math.log(2);
    } else {
      value = 0;
    }
    for (direction in [0,1,2,3]) {
      var vector = self.getVector(direction);
      var target = { x: cell.x + vector.x, y: cell.y+vector.y }
      if (self.withinBounds(target) && !marked[target.x][target.y]) {
        if ( self.cellOccupied(target) ) {
          targetValue = Math.log(self.cellContent(target).value ) / Math.log(2);
          if ( targetValue > value ) {
            //console.log(cell, value, target, targetValue);
            increases += targetValue - value;
          }
        } 
        if (!queued[target.x][target.y]) {
          cellQueue.push(target);
          queued[target.x][target.y] = true;
        }
      }
    }
    if (markAfter == 0) {
      while (markList.length > 0) {
        var cel = markList.pop();
        marked[cel.x][cel.y] = true;
      }
      markAfter = cellQueue.length;
    }
  }

  while (cellQueue.length > 0) {
    markAfter--;
    markAndScore(cellQueue.shift())
  }

  return -increases;
}

// measures how monotonic the grid is. This means the values of the tiles are strictly increasing
// or decreasing in both the left/right and up/down directions
Grid.prototype.monotonicity2 = function() {
  // scores for all four directions
  var totals = [0, 0, 0, 0];

  // up/down direction
  for (var x=0; x<4; x++) {
    var current = 0;
    var next = current+1;
    while ( next<4 ) {
      while ( next<4 && !this.cellOccupied( this.indexes[x][next] )) {
        next++;
      }
      if (next>=4) { next--; }
      var currentValue = this.cellOccupied({x:x, y:current}) ?
        Math.log(this.cellContent( this.indexes[x][current] ).value) / Math.log(2) :
        0;
      var nextValue = this.cellOccupied({x:x, y:next}) ?
        Math.log(this.cellContent( this.indexes[x][next] ).value) / Math.log(2) :
        0;
      if (currentValue > nextValue) {
        totals[0] += nextValue - currentValue;
      } else if (nextValue > currentValue) {
        totals[1] += currentValue - nextValue;
      }
      current = next;
      next++;
    }
  }

  // left/right direction
  for (var y=0; y<4; y++) {
    var current = 0;
    var next = current+1;
    while ( next<4 ) {
      while ( next<4 && !this.cellOccupied( this.indexes[next][y] )) {
        next++;
      }
      if (next>=4) { next--; }
      var currentValue = this.cellOccupied({x:current, y:y}) ?
        Math.log(this.cellContent( this.indexes[current][y] ).value) / Math.log(2) :
        0;
      var nextValue = this.cellOccupied({x:next, y:y}) ?
        Math.log(this.cellContent( this.indexes[next][y] ).value) / Math.log(2) :
        0;
      if (currentValue > nextValue) {
        totals[2] += nextValue - currentValue;
      } else if (nextValue > currentValue) {
        totals[3] += currentValue - nextValue;
      }
      current = next;
      next++;
    }
  }

  return Math.max(totals[0], totals[1]) + Math.max(totals[2], totals[3]);
}

Grid.prototype.maxValue = function() {
  var max = 0;
  for (var x=0; x<4; x++) {
    for (var y=0; y<4; y++) {
      if (this.cellOccupied(this.indexes[x][y])) {
        var value = this.cellContent(this.indexes[x][y]).value;
        if (value > max) {
          max = value;
        }
      }
    }
  }

  return Math.log(max) / Math.log(2);
}

// WIP. trying to favor top-heavy distributions (force consolidation of higher value tiles)
/*
Grid.prototype.valueSum = function() {
  var valueCount = [];
  for (var i=0; i<11; i++) {
    valueCount.push(0);
  }

  for (var x=0; x<4; x++) {
    for (var y=0; y<4; y++) {
      if (this.cellOccupied(this.indexes[x][y])) {
        valueCount[Math.log(this.cellContent(this.indexes[x][y]).value) / Math.log(2)]++;
      }
    }
  }

  var sum = 0;
  for (var i=1; i<11; i++) {
    sum += valueCount[i] * Math.pow(2, i) + i;
  }

  return sum;
}
*/

// check for win
Grid.prototype.isWin = function() {
  var self = this;
  for (var x=0; x<4; x++) {
    for (var y=0; y<4; y++) {
      if (self.cellOccupied(this.indexes[x][y])) {
        if (self.cellContent(this.indexes[x][y]).value == 2048) {
          return true;
        }
      }
    }
  }
  return false;
}

//Grid.prototype.zobristTable = {}
//for
//Grid.prototype.hash = function() {
//}