Как установить счет для таблицы в Tic Tac Toe?

Question

У меня есть таблица и некоторые функции, такие как Generate_moves () и т. Д., Но для работы алгоритма minmax мне нужно установить оценку для таблиц, чтобы компьютер выбирал лучшую таблицу.

        public int Score()
        {
            if (Turn == "X")
            {
                if (gameWon("X")) return 100;
                if (gameWon("O")) return -100;
                if (gameDrawn()) return 0;

                return n - canWin("X");
            }

            if (Turn == "O")
            {
                if (gameWon("O")) return 100;
                if (gameWon("X")) return -100;
                if (gameDrawn()) return 0;

                return n - canWin("O");
            }

            return -1;
        }

My canWin(string) возвращает число, которое говорит мне, сколько X или O у меня есть в прямой или столбце, но я сомневаюсь, что было бы здорово установить счет для таблицы.

Если у меня есть таблица:

X - X
0 X 0
- - 0

оценка должна быть такой же, как

X - -
0 - X
0 0 X

и должна быть больше, чем

X - X
0 - -
- 0 -

ИЯ понятия не имею, как заставить функцию «Счет» сообщать мне разные оценки.Как я могу реализовать метод Score, чтобы сказать мне это?

Редактировать:

, если компьютер сначала с X, а я с O

X - -      X - -      X - -     X - -
- - -   -> 0 - -   -> 0 X -  -> 0 X -
- - -      - - -      - - -     - - 0

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

X - X
0 X -
- - 0

Answer 1

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

Даже такой простой алгоритм, как minmax, излишний - просто проверьте все возможные ходы грубой силой.На современном ПК это займет всего несколько миллисекунд.

Answer 2

Tic-Tac-Toe - относительно легкая игра для компьютеров, поскольку фактор ветвления и количество возможностей относительно невелики, поэтому: будет лучше создать простейший [для расчета] возможный эвристическая функция, и пусть minmax достигает самого глубокого уровня, листьев игрового дерева, которые все являются определенной победой / поражением / ничьей.

Если вы все еще ищете эвристику, вы можете использовать number of rows/cols/diagonals with exactly 2 "X"s and left square is empty

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

Answer 3

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

Решите крестики-нолики с помощью алгоритма MiniMax

Visualgos: крестики-нолики

Answer 4

Чтобы ответить на ваш второй вопрос:

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

Это задача минимаксного алгоритма. Он смотрит лучший ход из дерева игры. Для крестики-нолики вам не нужна очень сложная функция оценки, достаточно вернуть положительное или отрицательное значение , если игрок выиграл или 0 в противном случае. Если хотите, вы можете расширить его, оценив, сможет ли один игрок выиграть в следующем ходу . Более сложные функции оценки, которые вам нужны в играх с большим коэффициентом ветвления и где игровое дерево может стать намного глубже (не только 9 ходов).
Мой опыт ^* заключался в том, что продвижение на один уровень глубже в поиске по дереву игр дает лучшие результаты, чем не достижение этого уровня (в то же время) из-за более умной функции оценки. Нелегко отличить более глубокие поиски из-за простой оценки или не очень глубоких поисков из-за сложной оценки. Есть много других существенных улучшений алгоритма минимакса, которые являются многообещающими, не зацикливайтесь на сложной оценке, сначала подумайте:

• альфа-бета-обрезка
• Итеративное углубление
• Таблица транспонирования

После этого вы все еще можете улучшить функцию оценки. Несколько других соображений по поводу оценки: Может быть, лучше выполнить некоторую работу в функции makeMove, здесь нужно проверить только одну (вместо всех) строку, один столбец и одну или две диагонали. Затем, помимо текущей доски, сохраните информацию, полученную из этой проверки. Эта информация включает в себя, если это был выигрышный ход (установить счет) или если следующий ход от другого игрока является вынужденным (помните ход, который должен сделать следующий игрок, getMoves вернет только этот). И последнее, но не менее важное: если один столбец / строка и одна диагональ содержат вынужденный ход, игрок выигрывает в два хода (сохраните счет).

Удачи вам в оценке!

_{* Некоторое время назад я работал над функцией оценки Connect-Four-Game-Engine. Наилучшим подходом для оценки платы Connect-Four было проанализировать нечетные и четные угрозы, как описано в главе «Анализ угроз» articel Expert Play in Connect-Four от Джеймса Д. Аллена. Алгоритм анализирует основные и второстепенные угрозы. После удаления части анализа незначительной угрозы, альфа-бета-поиск работал лучше!}

Answer 5

Одна возможность ... Оценка = Количество оставшихся способов (строк, столбцов или диагоналей, которые еще можно заполнить до состояния победы), чтобы выиграть за x - Количество оставшихся способов выиграть за 0 для каждого состояния, которое не является листом.(конечное состояние) Для конечных состояний у вас есть только Score = 1, 0 или -1