| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритмы поиска решений в играх с двумя игроками |
| Автор: PROme 18.2.2004, 19:38 |
| Собственно все что по сабжу ИНТЕРЕСУЕТ |
| Автор: Mal Hack 18.2.2004, 20:58 |
| У нас ребята на практике баловались этим... По крайней мере реализововали нажатия не обычниым getch'ом, а читали сигналы с портов (они есть в стандартной библиотеки strings.h). Затем по этим значениям делаешь выбор того, что нужно сделать... |
| Автор: Fedor 19.2.2004, 08:12 |
| Ну, разные игры по-разному, но в основном компьютер пытается полным перебором найти возможные ходы юзера ивыбрать для себя наилучший. Чем больше глубина поиска, тем "умнее" компьютер. Но при этом он может думать ОЧЕНЬ большое количество времени... |
| Автор: val 19.2.2004, 12:55 |
| Чаще всего такие игрушки сводятся к исследованию какого-нибудь направленного графа. На этом графе, в зависимости от задачи, ищут кратчайшие пути, разрезы и т.д... |
| Автор: PROme 19.2.2004, 16:18 |
| Немного перенаправлю вопрос. Меня интересуют НЕ то как можно это сделать, а КОНКРЕТНЫЕ, известные алгоритмы, например как алгоритм Хаффмена в архивировании. |
| Автор: Fedor 20.2.2004, 08:32 |
| PROme ИМХО, такого не существует... Ведь тут все зависит от хода второго игрока. Его нельзя заранее предугадать. В некоторых типах игр можно заранее просчитать выиграшные позиции и ходить туда... А в других случаях можно сделать как-то еще по-другому... В третьих - только полный перебор. А в основном игра двух людей - это всега эвристика. |
| Автор: val 20.2.2004, 10:45 | ||
Согласен... Есть подходы к решению, но алгоритиов нет... |
| Автор: sergejzr 7.3.2004, 23:09 |
| Совершенно верно! Создаётся дерево ВСЕвозможных комбинаций и проишодит поиск. Как алгоритм используются bread-first search , depth-first search но в основном depth-first cut-off depth. Эти алгоритмы улучшаются http://www.xs4all.nl/~aske/Papers/aij-final.pdf.gz и http://algolist.manual.ru/games/alphabeta.php. Хотя к конкретным играм возможно существуют алгоритмы. |