Думающий народ здесь есть?

← →
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]

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

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

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

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

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

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, либо беребор в глубь (т.е. просмотр следующего уровня).
В целом если немного подстроить то комп с компом играет бессконечно. Я - лично всегда проигрываю(если хорошо настроенна и не использовать известных тебе провалов в интелекте компа, но значит плохо настроил функцию) (считался крутым игроком - в свое время).
Если добавить перебор на неск. ходов. то думаю человек не выигрыет никогда.

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

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