Как я упоминал в своем предыдущем сообщении в блоге, я реализовывал непревзойденную компьютерную игру в Java Tic Tac Toe.

Я хотел проверить, работает ли мой минимаксный алгоритм. Для этого я интегрировал новый класс UnbeatableComputer в свой игровой процесс.

К сожалению, хотя мои тесты были зелеными, все еще шло наперекосяк. Иногда мой непобедимый игрок играл так, как я ожидал, и либо выигрывал у меня, либо играл вничью. Тем не менее, были некоторые состояния игры, когда компьютер не выбрал лучший ход, не сумев заблокировать мой выигрышный ход. Что-то пошло не так.

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

@Test
public void blocksADifferentWin() {
    UnbeatableComputer unbeatableComputer = new UnbeatableComputer(O);
    Board board = new Board(3, asList(
            EMPTY, EMPTY, O,
            EMPTY, X, X,
            EMPTY, EMPTY, EMPTY));
    assertThat(unbeatableComputer.findBestMove(board, true, -1), is(3));
}

Я понял, что каждый раз возвращал последний сыгранный ход, но не засчитывал ход, а возвращал самый результативный ход. Это означало, что ход, сыгранный «непобедимым» компьютером, не всегда был точным.

Чтобы попытаться заставить мою игру работать правильно, я снова ввел в начале оператор подсчета очков. Независимо от того, был ли у меня оператор if или нет, мне нужно было отслеживать наиболее результативное состояние игры в зависимости от сыгранного хода.

Я создал хэш с именем bestMoves, и если текущий ход набрал 1 или 0 баллов, я вставил ход как ключ, а оценку — как значение внутри карты.

class UnbeatableComputer implements Player {
  private Mark mark;
  public HashMap bestMoves;
  public UnbeatableComputer(Mark mark) {
    this.mark = mark;
    this.bestMoves = new HashMap();
  }
  if (score == 1 || score == 0) {
    bestMoves.put(move, score);
  }

Мой план состоял в том, чтобы найти самый высокий балл на карте, а затем вернуть ход, соответствующий этому счету.

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

Я создал переменную экземпляра с именем BestMoves и передал в нее текущий ход и счет для ключей и значений.

public int getBestMove() {
  for (Map.Entry<Integer, Integer> entry : bestMoves.entrySet()) {
    if (entry.getValue() == 1) {
      return entry.getKey();
    }
  }
}

Я хотел перебрать значения и найти значение, равное 1 или 0. Затем я хотел вернуть ход, соответствующий этому счету. Если состояние игры выдает только 0 очков, оно не соответствует условию (entry.getValue() == 1) или возвращает правильный ход.

Я попытался поиграть с этим и добавить еще одно условие, чтобы вернуть счет, если он равен 0, но это не помогло. Например, что, если первая оценка была равна 0, а следующая — 1? Мы рано вернемся к 0 и не доберемся до второго счета, что означает, что наивысший балл и соответствующий ключ (перемещение) не возвращаются.

public int getBestMove() {
  for (Map.Entry<Integer, Integer> entry : bestMoves.entrySet()) {
    if (entry.getValue() == 1) {
        return entry.getKey();
    } else {
        return entry.getKey();
    }
  }
}

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

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

Главный урок, который я усвоил, заключался в том, что манипулирование хэш-картами в Java — запутанный и долгий процесс. С более простой структурой данных было бы легче работать.