Матрица три на три, как быстро проверить, совпадают ли между собой элементы любого столбца\строки\диагонали?

Question

[Тарасов Константин]

Пишу программу для игры в крестики нолики, как проверить, что кто-то выстроил 3 элемента в ряд и игра выиграна? Единственное что приходит в голову - отдельно сравнивать на равенство каждый столбец\строку\диагональ, но это борода, может подскажете чего поумнее?

Answer 1

[Ndochp]

ИМХО для поля произвольной расмерности надо проверять не поле, а ход. Так как число выигрыщных комбинаций с ростом поля будет расти очень плохо. Думаю надо проверять каждый ход, не привел ли он к победе.
То есть после каждого хода проверяем последовательно
1. длина диагонали крестиков вверхвправо + внизвлево+1
2. длина диагонали крестиков вверхвлево+внизвправо+1
3. длина диагонали крестиков вправо+влево+1
4. длина диагонали крестиков вниз+вверх + 1
Если хотя бы одно направление больше целевого значения (на неограниченном поле вроде 5 в ряд играют), то игрок победил.

Comments

[Тарасов Константин]

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

[Тарасов Константин]

Вообще, изначальная цель написания этой игры - это написать еще и ИИ к ней, а как он будет выглядеть для случайных полей я не представляю)

[Ndochp]

Так же. Плясать от структур, а не поля. Ну или анализировать на предмет удачности идеи установки клетки в радиусе двух длинн выигрышной комбинации от существующих помеченных полей и границ поля. Реально все правильные ходы будут расположены ближе. Грубо говоря, считаем для каждой клетки вектор, за сколько ходов мы сможем выиграть партию при постановке крестика в нее для каждого направления. И за сколько ходов это направление может быть заблокировано. а дальше стараемся построить выигрышную комбинацию (типа 1 ход до победы, два хода на блокирование, 3 раза по 2 хода до победы, и тд)

Answer 2

[Тимур]

Если я правильно понял предлагаемый lumierecyril вариант, то он не вполне рабочий . Представьте что крестик стоит на клетках с индексами 0, 5, 8. По идее если поставить крестик на индекс 4 , игрок выиграл. Но в данном случае это не так. При конкатенации индексов с крестиками мы получим 0, 4, 5 так как согласно предложенной логике мы пробегаем по клеткам последовательно и собираем варианты из трехзначных цифр. Мой вариант - каждый раз собирать строку из индексов , содержащих крестик(или нолик в зависмости от игрока) . Затем имея массив выигрышных комбинаций , проверять имеется ли каждая цифра комбинации в конкатенированной строке индексов с крестиками(работать со String) . Если есть все три совпадения, то игрок выиграл. Есть еще вариант - пробежаться два раза циклом с вложенным циклом по игровому полю, накапливая результаты каждый раз в два списка по условиям - совпадение по горизонтали, по диагонали слева, затем по вертикали и по диагонали справа. Если хоть один список имеет длину равную количеству клеток стороны игрового поля, то игрок выиграл.

Comments

[Тарасов Константин]

@lumierecyril Спасибо за идею с множествами, в итоге код сократился в разы. В итоге сделал так:

private final ArrayList<Set<Integer>> WINNING_COMBS = new ArrayList<Set<Integer>>();

в этом хранятся в виде множеств все выигрышные комбинации. Ну а вот весь код отвечающий за поиск выигрышных комбинаций:

ArrayList<Integer> player1Marks = new ArrayList<Integer>();
        ArrayList<Integer> player2Marks = new ArrayList<Integer>();
        for (int i = 0; i < board.length; i++) {
            switch (board[i]) {
                case PLAYER_1: player1Marks.add(i); break;
                case PLAYER_2: player2Marks.add(i); break;
            }
        }
        for (Set winComb : WINNING_COMBS) {
            if (player1Marks.containsAll(winComb)) {
                return GameState.PLAYER_1_WIN;
            } else if (player2Marks.containsAll(winComb)) {
                return GameState.PLAYER_2_WIN;
            }
        }

[Тарасов Константин]

@lumierecyril сейчас оно для 3х3, но думаю масштабировать можно сколько душе угодно) нужно только заносить дополнительные комбинации.
На деле пока нечем пробовать, так как самый начальный этап) прямо сейчас вот делаю что бы ходы по очереди игроки делали. Если надо будет отпишусь)
Проблема в том, что для больших полей правила игры чаще всего предписывают составить ряд из 3 крестиков, даже когда поле 10х10, а вот тут уже неизвестно как быть, будет через чур много комбинаций.