Как я упоминал в своем предыдущем сообщении в блоге, я реализовывал непревзойденную компьютерную игру в 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 — запутанный и долгий процесс. С более простой структурой данных было бы легче работать.