Минимакс — способ, которым игровые программы выбирают ходы: предположите, что оба игрока играют идеально, оцените каждую законченную партию и поднимите оценки вверх по дереву игры. Игрок, чей ход, выбирает потомка с наибольшей для себя оценкой.
Доска — строка из 9 символов, читаемая по строкам (индексы 0-8), из "X", "O" или "." для пустой клетки. X всегда ходит первым, поэтому ход X, когда у обоих одинаковое число отметок, иначе ход O.
Оценивайте законченную партию с точки зрения игрока, чей ход: +1 за победу, 0 за ничью, -1 за поражение. Верните пустую клетку, ход в которую имеет лучшую минимаксную оценку; если таких несколько, верните наименьший индекс.
Реализуйте best_move(board).
Входные данные
board: Допустимая позиция, в которой ещё никто не выиграл и есть хотя бы одна пустая клетка.
Выходные данные
Верните индекс (0-8) лучшего хода.
Ограничения
board состоит ровно из 9 символов, каждый — X, O или .
Позиция может возникнуть в реальной партии, никто не выиграл, и есть хотя бы одна пустая клетка
Примеры
Ввод:
board = "XX.OO...."
Ожидаемый вывод:
expected = 2Ввод:
std::string board = "XX.OO....";
Ожидаемый вывод:
long long expected = 2;Ввод:
string board = "XX.OO....";
Ожидаемый вывод:
long expected = 2;Пояснение
У X и O по две отметки, значит, ходит X. Ход в 2 завершает верхнюю строку и сразу выигрывает (+1).
Ввод:
board = "X..OO...X"
Ожидаемый вывод:
expected = 5Ввод:
std::string board = "X..OO...X";
Ожидаемый вывод:
long long expected = 5;Ввод:
string board = "X..OO...X";
Ожидаемый вывод:
long expected = 5;Пояснение
Ходит X. O угрожает завершить среднюю строку в клетке 5. Любой другой ход позволяет O выиграть (-1), а блок в 5 ведёт к ничьей (0), поэтому ответ — 5.
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.