Крестики нолики Опции

[Vardes]

Пришло время курсовика....Необходимо написать игру крестики-нолики на поле размером 19X19 (возможность игры с ПК и с соперником ).Хотел проконсультироваться со знающими людьми, могет кто посоветует какой лучше алгоритм взять за основу, могет имеется какая-нить оценочная функция или что-то вроде того...

[Гость]

Рекурсивно рассматривай все возможные ходы, отсекая нежелательные для компьютера позиции. Формально, алгоритм вида:

Function getStep(pos:array[0..18] of array[0..18] of byte):integer; //возвращает ячейку, куда нужно походить, резултат хода при лучшем ходе игрока или другую информацию.

Если комп проиграл, то вернуть "Проиграно"
Если комп выиграл, то вернуть "Победа"
Если ничья, то вернуть "Ничья"

Для каждой пустой ячейки делать
поставить крестик в ячейку;
Для каждой пустой ячейки делать
поставить нолик в ячейку;
вызвать GetStep для полученной позиции и запомнить результат;
end;
Если все запомненные значения означают "проигрыш или ничью", то перейти к след. такту;
Ессли все запомненные значения означают "выигрыш", то ход найден.
end;

[volvo]

Дож, ты представляешь глубину рекурсии (даже при условии отсечения заведомо ненужных вариантов) и заторможенность программы?

Ты никогда не пробовал, например, работать с шахматными фигурами НЕ на доске 8*8, а, скажем, на доске 12*12? А тут все-же 19*19...

[Zxzc]

Я предлагаю вот такой алгоритм хода комп-ра:
Пояснение:
Опасно - имеется ситуация при которой следующий ход соперника будет выигрышным.
Комбинация - линия поля в которой содержатся твои фигуры и пустые клетки.
Фигура - крестик или нолик.
Строка - прямая непрерывная линия по горизонали, вертикали или диагонали.
Подходящее поле - поле в котором пересекаются наиболее удачные комбинации.
Итак,

Код

нач.
  ЕСЛИ не опасно то
   нач.
    Найти самую длинную комбинацию(ДЛ_комб);
     если комбинация существует то
       нач.
         Найти в ДЛ_комб подходящее поле;  //Рассматриваем строку ДЛ_комб
         Поставить фигуру;
         Передать ход;
        кон.
     иначе
        нач.
         Найти подходящее поле. //Рассматриваем всё поле
         Поставить фигуру;
         Передать ход;
        кон.
    кон.
   ИНАЧЕ
нач.
  Вычленить опасную строку;
  Найти в ней пустую клетку;
  Поставить туда фигуру;
  Передать ход;
кон.

[Zxzc]

ОК, Дальше - больше.
Интересно как найти подходящее поле?
Вот как я решил этот вопрос.
Введем новые, мои любимые , понятия:
Рейтинг - Количество твоих фигур в комбинациях, пересекающихся в этой клетке.
Выход - Строка содержащая рассматриваемую клетку, но не содержащая фигур противника.

1. Наиболее подходящей будет центральная клетка. В ней пересекаются 4 строки.
2. Угловая клетка на втором месте. Там - 3 строки.
3. В остальных клетках пересекаются по 2 строки.

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

Особые ситуации:
Если в какой-то комбинации обнаружилось n-1 фигур, то эта комбинация выигрышная и ставим туда фигуру (n-размер поля).
Если подходящая клетка так и не была обнаружена, то игра ведет к ничье или победе соперника.
В этом случае процедура может возвращать случайные значения либо "идти в защиту" - закрывать комбинации противника. Во 2 случае возможность выигрыша человека резко снижается. На этом можно основать 2 уровня сложности:простой и сложный.
Этой информации достаточно, чтобы самому написать алгоритм. Спрашивай, что не ясно.
P.S. Прошу проверить алгоритмы т.к. я только что их сочинил и не ручаюсь за правильность и оптимальность.

Сообщение отредактировано: Zxzc - 3.05.2006 4:47