Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Игры";
Текущий архив: 2003.02.06;
Скачать: [xml.tar.bz2];

Вниз

Думающий народ здесь есть?   Найти похожие ветки 

 
MinderM   (2002-07-28 22:03) [0]

Есть соображентя по поводу реализации ai к игре крестики нолики 15 на 15?!


 
Ich Hasse   (2002-07-28 22:30) [1]

Надо просто оценивать где сколько крестиков стоит, и куда ставить свои в зависимости от того есть вилки или нет, вот и все... (Я понимаю что из моих уст все звучит очень легко, но все же)


 
MinderM   (2002-07-29 22:21) [2]

Ich Hasse да все тривиально и просто... , но может подскажешь дельный алгоритм?


 
msalex   (2002-07-29 22:32) [3]

Ну если ai начинает играть первым - то ты случайным образом,
выбираеш куда поставить крестик или нолик, после хода человека,
оцениваеш ситуацию, как поставить чтоб не проиграть, а потом
уже куда поставить чтоб легче было выиграть.
Помоему всё просто:)


 
Ich Hasse   (2002-07-29 23:28) [4]

2 msalex Да это все так просто когда ты ничего не пишешь
2 MinderM Итак оцениваешь все отрезки по пять в каждом, смотришь если в к.л. месте их три то блокируешь их с RND стороны, если четыре, то с той с которой его не хватает, далле если нет таких линий больше двух, то нападаешь, Потом можно будет добавить так, чтобы он думал не RND ставил сторону, а оценивал, нодо-ли ему это, потом, когда одним крестом можно перекрыть 2 линии, Оценивать чвое состояние и т.д.


 
minderm   (2002-07-30 08:59) [5]

Ich Hasse я думал реализовать через рекурсию так чтобы просматривать на несколько ходов вперед. просто надо придумать процедуру оценки ситуации. к примеру эти три линии равны ХХ00Х и 0ХХ0Х и 0ХХХ0.


 
kos2000   (2002-08-24 03:59) [6]

Перебираешь варианты на определенное количество ходов,
затем оцениваешь позицию. Оценивать я думаю надо по количеству
свободных троек - ХХХ, Х ХХ , Х Х Х и т. д. Считешь разницу
между своими тройками и противника . Где разница больше ,
то и выбираешь.


 
Ev_genus   (2002-08-24 04:34) [7]

Нужно придумать качественную функцию для клетки. Самый простой метод это сколько своих фишек стоит по вертикали, горизонтали и диагонали (при условии что из них можно сложить последовательность). Также в функцию нужно включит просчёт мешающих ходов. Аналогично считаем полезные фишки противника.

Далее в таких алгоритмах, обычно впадают в рекурсию, пытаясь по этому же алгоритму подумать за соперника. Потом опять за себя и тд. Но крестики-нолики это не шахматы. Тут можно думать только о следующем ходе. Так перебрав все клетки находиш самую качественную.

Качественная функция должна возвращать число. Чем больше диапазон её значений тем правильнее будет думать комп.

Малость запоздал я с ответом :). Надеюсь поможет.

PS Сделаеш намыль мне её. Посмотрим сможет ли она меня обыграть.


 
kos200   (2002-08-24 06:11) [8]

Посидел тут, подумал. Пришли в голову такие соображения.
Надо завести пару массивов дополнительных, где держать для каждой свободной клетки
ее потенциальную ценность для твоей атаки и потенциальную опасность для атаки
соперника. Массив 15х15х4 - 15х15 координаты, 4 - оценки точки по вертикали,
горизонтали и диагоналям. То есть на эту клетку можно поставить твой например крестик
- тогда по диагонали например может образоваться свободная пара с другим крестиком
(вплотную, через один, через две и т.д. до 3 без ноликов противника, которые помешают
образоваться пятерке). Эта пара потенциально может перерости в пятерку, поэтому для тебя
оценка полезности этой свободной клетки возрастает - можно поставить в ячейку, которая
отвечает за направление оценку 1, если образуется тройка - 2 и т.д. Если линия
ограничена крестиком противника, оценка снижается на 1 например, если по этому направлению
ты уже в принципе не можешь построить пятерку то оценка минус 1. И так для всех направлений.
Потом суммируешь по всем направлениям - чем больше, тем эта клетка потенциально для тебя в
атаке интерестнее. То же для противника - чем оценка больше, тем для тебя эта клетка опаянее.
Перебираешь варианты хода на 3(тут ессно надо по скорости подбирать) затем для получившейся
позиции (ход например твой) считаешь форсированные варианты - когда у противника стоит четверка
и тебе ее затыкать надо, а противник опять четверку ... либо проиграешь, либо форсированный
вариант кончился.Если противник не атакует, считай можешь ли атаковать ты и тоже самое.
Получаешь позицию где явно атаковать или защищаться не надо и тут можно посчитать "умные"
ходы за обоих еще вариантов на 5 - отдельно для своей атаки - ставишь крестик на клетку с
максимальной оценкой по сумме для тебя и для защиты - ставишь на потенциально опасную клетку
соперника.Следующий ход противника - если образовался форсированный вариант его считать,
если нет то тоже два хода - атака и защита. И т.д.
В итоге получешь либо результат - победа или поражение и оцениваешь ветку соответственно
- либо позицию которую нужно оценить. Оцениваешь по разнице сумм оценок клеток на всем поле
- просто суммируешь все клетки в дополнительных массивах и разницу берешь между масивами.
Форсированные варианты вседа надо до конца просчитывать, если они есть, потому как победа
ВСЕГДА достигается с помощью форсированного варианта.
Вроде все.


 
Gandalf   (2002-08-24 13:53) [9]

Есть не только идея - но и реализация. Оценочная функция. Играет довольно неплохо. Идею взял из книги.
Форсайта - "Паскаль для всех".
Принцип такой - приблизительно. Берем пустую клетку. И смотрим ее ценность для себя и для противника (по всем 4. направлениям они суммируется). Например если это. 4 в ряд (своих). То стоимость 1. Если это 4 врага - то стоимость 2. Если это 3(своих) - то стоимость 3 и т.д. Если линейка разрывна. То стоимость ее увелич. на 1. (если разрыв в рассматриваемой точке то он не учитывается). Если блокированна с одной стороны стоимость увел. на 1. (кроме линии из 4). Если блокированна с обоих сторон - то уходит в бессконечность стоимость (кроме линей-ки из 4). Далее находим с самым маленьким рейтингом и так ходим. Если есть несколько равносильных - то либо Random, либо беребор в глубь (т.е. просмотр следующего уровня).
В целом если немного подстроить то комп с компом играет бессконечно. Я - лично всегда проигрываю(если хорошо настроенна и не использовать известных тебе провалов в интелекте компа, но значит плохо настроил функцию) (считался крутым игроком - в свое время).
Если добавить перебор на неск. ходов. то думаю человек не выигрыет никогда.

ЗЫ: для игры доказано - что у первого игрока приимущество, в идеале он не проигрывает.



Страницы: 1 вся ветка

Форум: "Игры";
Текущий архив: 2003.02.06;
Скачать: [xml.tar.bz2];

Наверх









Память: 0.6 MB
Время: 0.034 c
14-15825
Tux
2003-01-22 00:18
2003.02.06
Нормальный провайдер в Москве


1-15539
Dmitry Filippov
2003-01-28 13:34
2003.02.06
Компонент имеет свойство TStrings в DFM


9-15379
Nafander
2002-08-16 11:52
2003.02.06
Динамическое создание эфекта


1-15668
Step[B.M.]
2003-01-29 18:05
2003.02.06
Группа компонентов в одном имени


14-15876
Сергей Чурсин
2003-01-19 15:47
2003.02.06
Андрей Паршев. Почему Россия не Америка





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский