Крестики-нолики

[Arigato]

Мини-максный поиск - это из теории игр. В кратце метод основан на том, что строится игровое дерево (дерево всех возможных ходов), затем делается оценка каждого хода и выбирается ход с максимальной оценкой. Построение ведётся с предположением о том, что противник будет играть по оптимальной стратегии.
Компьютер ориентируется на самую неблагоприятную обстановку и выбирает стратегию с минимальным риском.
Такие алгоритмы используются чаще в играх с полной информацией (шашки, шахматы, крестики-нолики и т.д.).
Кое-что есть тут:
http://www.aigroup.narod.ru/search1r.htm

[Sazary]

Arigato Спасибо! Попробую разобраться..

[Sazary]

Просьба оценить мой первый опыт работы с Delphi. Крестики-нолики 10x10. ))
Как мне показалось, наиболее оптимальное значение агрессивности 0,5.

[Sasha_Smirnov]

Первый опыт удался!
Даже удивили меня, что Delphi — это не только средство «помощи» студентам!!!
А каковы трудозатраты?

[Sazary]

Sasha_Smirnov Спасибо )

А каковы трудозатраты?

Не могу сказать, что большие..
Игру делал где-то сутки (полные).. Большая часть времени ушла на отладку.
Как показалось, Делфи довольно легок в освоении.

[Arigato]

Сообщение от Sazary

Просьба оценить мой первый опыт работы с Delphi. Крестики-нолики 10x10. ))
Как мне показалось, наиболее оптимальное значение агрессивности 0,5.

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

[Sazary]

Arigato

А чего без исходников?

Просто там бардак, т.к. писал для себя ) Прикладываю.

Там осталось много тестовых кусков. В основном, в их названиях (переменных, объектов) присутствует слово "test".
Когда программа была готова где-то наполовину, вдруг узнал, что в StrtingGrid сначала пишется номер столбца (Col), а потом строки(Row), а не наоборот.. Поэтому некоторые комменты могут быть неточными (например, относительно направления просмотра). Это меня и так сильно запутало, и я не уже не стал исправлять )

Компьютер часто тупит, судя по всему, он не видит границу поля и думает, что сможет походить за пределы игрового поля.

С этим были проблемы, но, вроде как, они были решены.
Возможно, дело в методе поиска хода. Программа для каждой ячейки считает длины ряда по всем направлениям (8) сначала для себя, а потом для игрока. Для каждой длины считается значение коэффициента. Коэффициенты компьютера и игрока суммируются (получаются два значения - M и N) и вычисляется конечное значение по формуле result := M + Q*N (где Q - значение агрессивности компьютера).

Arigato кстати, вам отдельное спасибо за ваш пример крестиков-ноликов.. Почерпнул оттуда кое-какие идеи.

[ROD]

Ничего себе, тема оказалсь актуальна)))

Благодарю за критику, будет свободное время - постараюсь исправить.

Что касается 11 неправильных ходов, у меня алгоритм "АИ" (да, в данном случае именно в ковычках) прост: функция рандома выбирает столбец и строку, а далее действует общий и для игрока и для компа алгоритм проверки допустимости хода - если он недопустим, то пишется ообщение об ошибке и ход делается снова.

Просто мне неизвестен алгоритм для таких случаев, а в голову ничего умнее не пришло.

Вот версия 1.1 (исходники ее)

Правда она совсем не рациональная, это мой первый опыт создания чего-то своего (надоели всякие лабы, типа "ряд тейлора" или "сортировка строк матрицы")

P.S.

Вопрос про определение победы.

Как ее определить, у меня простым перебором всех вариантов победы (благо в поле 3х3 их всего 8), а если это дело не подругом сделать, что бы алгоритм был более компактный, как это можно сделать?

[Sazary]

ROD
Про определение победы..Описываю, как сделано у меня:
для каждой ячейки нужно проверить 4 направления: горизонталь, вертикаль и 2 диагонали (вправо вверх и вправо вниз).
Например, есть поле MxN, а длина ряда - D. Направления, в которых точно не может быть ряда нужной длины отбрасываются..
Например, цикл для проверки горизонтали будет выглядеть как-то так:

for(i=0;i<M;i++)
for(j=0;i<=N-D;i++)
  {
   fl := true; //изначально считаем, что ряд нужной длины есть
   for(k=j+1;k<N;k++)
     if (mass[i,k]!=mass[i,k-1]) 
       {  fl:=false;
           break; }
    if (fl) return 1; //возвращаем код победы
   }

Примерно так.. Этот алгоритм я использовал в своих крестиках-ноликах (постом выше).

[kamikadze67]

Сообщение от Sazary

Просьба оценить мой первый опыт работы с Delphi. Крестики-нолики 10x10. ))
Как мне показалось, наиболее оптимальное значение агрессивности 0,5.

Возникли ошибки с изменением уровня агрессивности, играл на уровне 1: за крестики без труда удается выиграть, за нолики в принципе тоже