Tic Tac Toe совершенный алгоритм AI: глубже в шаге «создать вилку»

Я уже читал много тем Tic Tac Toe на StackOverflow. И я нашел, что страtagsя в Википедии подходит для моего проекта презентации:

Игрок может играть идеально tic-tac-носок, если они выбирают движение с наивысшим приоритетом в следующей таблице [3].

1) Win: Если у вас есть два подряд, играйте третье, чтобы получить три подряд.

2) Блок: если противник имеет два подряд, сыграйте третье, чтобы заблокировать их.

3) Вилка: создайте возможность, где вы можете выиграть двумя способами.

4) Вилка блока оппонента:

Вариант 1. Создайте два подряд, чтобы заставить противника защищаться, если это не приводит к созданию вилки или выигрыша. Например, если «X» имеет угол, «O» имеет центр, а «X» имеет противоположный угол, «O» не должен играть в углу, чтобы выиграть. (Игра в углу в этом сценарии создает вилку для «X», чтобы выиграть.)

Вариант 2: Если есть конфигурация, в которой противник может разблокировать, заблокируйте эту вилку.

5) Центр: играть в центр.

6) Противоположный угол: если противник находится в углу, сыграйте противоположный угол.

7) Пустой угол: играйте в пустой угол.

8) Пустая сторона: играйте на пустой стороне.

Я последовал за этим шагом, и компьютер никогда не теряет. Однако способ, которым он атакует, не идеален. Потому что я понятия не имею, как сделать шаг 3. Вот что я делаю на шаге 3: сканируйте каждую ячейку, проверьте, не помещает ли токен в эту ячейку вилку, а затем положил ее туда.

private void step3() // Create Fork. { int[] dummyField = (int[])field.Clone(); // Try Level 1 Dummy for (int i = 0; i = 2) { nextCell = i; return; } dummyField[i] = 0; } } 

Пожалуйста, дайте мне несколько советов об этом шаге.

EDIT1: Вилка подсчета будет подсчитывать, сколько вилок у компьютера (токены компьютера равны 2, токены игроков равны 1, потому что я использовал этот метод для шага 4, так что для токена countFork функция countFork ).

EDIT2: Причина, по которой я говорю, что она не идеальна, – это то, что процессор (сначала идет первым, а его ячейки голубые, клетки человека – красные). введите описание изображения здесь Как вы можете видеть, если я помещаю в верхнюю ячейку, компьютер выигрывает. Но если я поставлю в правую ячейку, это галстук, хотя компьютер все равно может победить.

EDIT3: Не знаю, почему, но я прокомментировал шаг 3, и компьютер играет … отлично! Я очень удивлен! Вот моя функция countFork (мне нужно передать этот код в Alice, который не поддерживает 2-мерный массив, поэтому я использую getNumberFromXY для преобразования 2-мерного массива в 1-мерный):

 private int countFork(int[] field, int token) { int result = 0; // Vertical int cpuTokenCount; int spareCell; for (int x = 0; x < 3; x++) { cpuTokenCount = 0; spareCell = -1; for (int y = 0; y < 3; y++) { if (field[getNumberFromXY(x, y)] == token) cpuTokenCount++; else if (field[getNumberFromXY(x, y)] == 0) spareCell = getNumberFromXY(x, y); } if (cpuTokenCount == 2 && spareCell != -1) result++; } // Horizontal for (int y = 0; y < 3; y++) { cpuTokenCount = 0; spareCell = -1; for (int x = 0; x < 3; x++) { if (field[getNumberFromXY(x, y)] == token) cpuTokenCount++; else if (field[getNumberFromXY(x, y)] == 0) spareCell = getNumberFromXY(x, y); } if (cpuTokenCount == 2 && spareCell != -1) result++; } // Top-Left To Lower-Right Diagonal cpuTokenCount = 0; spareCell = -1; for (int i = 0; i < 3; i++) { if (field[getNumberFromXY(i, i)] == token) cpuTokenCount++; else if (field[getNumberFromXY(i, i)] == 0) spareCell = getNumberFromXY(i, i); } if (cpuTokenCount == 2 && spareCell != -1) result++; // Top-Right To Lower-Left Diagonal cpuTokenCount = 0; spareCell = -1; for (int i = 0; i < 3; i++) { if (field[getNumberFromXY(2 - i, i)] == token) cpuTokenCount++; else if (field[getNumberFromXY(2 - i, i)] == 0) spareCell = getNumberFromXY(2 - i, i); } if (cpuTokenCount == 2 && spareCell != -1) result++; return result; } 

EDIT4: исправить ошибку в соответствии с soandos и обновить код в EDIT 3, теперь он отлично работает!

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

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

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