Просмотр полной версии : Алгоритм игры рендзю
Как мне известно, многие из форумчан являются студентами матфака, хотел попросить у вас помощи(да и у всех кто занимается програмированием).Вообщем по предмету комбинаторные алгоритмы мне задали написать игру рендзю : крестики - нолики на доске произвольного размера, пять в ряд.Большую часть программы написал(реализовал алгоритм на основе оценочной функции), проблема появилась в самом конце : как проверять на выигрышь одного из игроков?В обычных к-н это легко, простым перебором, благо поле не большое, а как быть с полем большого размера?
Надеюсь на помощь, в пятницу надо как то сдавать программу.
З.Ы. А алгоритм туповатый какой то, ходит наугад:) , ну слава богу хоть работает:) .
Алгоритма не знаю, но я открыл для себя чето новое: оказывается та хрень которой мы мудились целый год называется рендзю!
Я нашел не очень сложный алгоритм(некоторые из них, тянут на магистранскую работу:) ) и написал прогу за пару часов, уместилась в ~ 310 строк(в полном варианте думаю около 400 будет).Теперь только проверку добавить и усе:) .
Alice Mizer
30.05.2006, 13:56
Хорошо :rolleyes:
Просто при очередном ходе проверять не входит ли он в пятерку подряд поставленных символов, содержащих новый элемент.
Оценка же у тебя пересчитывает не все поле а только зону нового символа, надеюсь? Расскажи какой алгоритм использовал можно в личку если не лень а я посмотрю что можно сделать ^_^
Pavel Boyko
30.05.2006, 17:59
Nord! Так не сказал, на каком языке алгоритм катал.
С++, Delphi?
Nord! Так не сказал, на каком языке алгоритм катал.
С++, Delphi?
Господи! Ничего, что я тут рядом стою?! Может, мне отойти?
Господи! Ничего, что я тут рядом стою?! Может, мне отойти?
Это ты о чем?
Alice Mizer
30.05.2006, 19:19
Pavel Boyko а какая разница-то? :lol:
Это ты о чем?
видимо о том что выделил в цитате:)))))
Хорошо :rolleyes:
Просто при очередном ходе проверять не входит ли он в пятерку подряд поставленных символов, содержащих новый элемент.
Оценка же у тебя пересчитывает не все поле а только зону нового символа, надеюсь? Расскажи какой алгоритм использовал можно в личку если не лень а я посмотрю что можно сделать ^_^
Вот в чем состоит реализованный мной алгоритм :
"Итак сyть оценочной фyнкции - оценить насколько выгодно нам поставить в даннyю точкy свою фишкy. Очевидно нам бывает выгодно это сделать либо для создания своего длинного pяда, либо для блокиpования длинного pяда пpотивника.
Также следyет yчесть, что бывает выгоднее пpодолжить/заблокиpовать большое количество не очень длинных pядов, вместо одного длинного.
Фишка, поставленная в даннyю пyстyю клеткy может одновpеменно yчаствовать в пpодолжении до 8 pядов (2 гоpизонтальных, 2 веpтикальных и 4 диагональных).
Считаем, что мы поставили фишкy в данное место. Тогда можно сосчитать длинны каждого из наших pядов, включающих этy фишкy.
Введем коэф. M = sum(Ki). Где Ki - коэф. важности i-го pяда. Т.к. напpавление pяда нам безpазлично, то Ki зависит только от длинны pяда.
Для пpостоты можно взять Ki=3*длинна pяда.
Полyченный коэф. М - оценка той выгоды, котоpyю мы полyчим, поставив в даннyю клеткy свою фишкy.
Далее пpедположим, что мы не поставили в даннyю клеткy фишкy, и соответственно это сделал пpотивник.
Аналогично считаем коэф. N - оценка выгоды, полyчаемой пpотивником.
Сложив М и N с некими оценочными коэф. полyчим окончательнyю оценкy: F = M + Q*N.
Чисел я не помню, поэтомy с вычислением Ki стоит поигpаться, возможно его стоит заменить степенной фyнкцием (но с небольшим основанием!).
Коэф. Q - показатель агpессивности алгоpитма, если он больше 1 - алгоpитм сидит в глyхой обоpоне; меньше 1 - алгоpитм пытается захватить инициативy.
По моемy мнению, Q следyет бpать меньше 1.
Из фич, yсложняющих жизнь пpотивникy, можно добавить фактоp слyчайности, для ваpиантов хода с pавными, или близкими, оценочными фyнкциями.
Теоpетически пpотив такого алгоpитма может сyществовать выигpышная стpатегия, но я ее не нашел."
(ц)Алголист
Оценка высчитывается для каждой клетки, далее ход делается в самую "важную" клетку.
С проверкой на победу мне уже подсказали, оказалось это самое легкое:) , даж не знаю как сам не додумался(наверно сказывается постоянное невысыпание - вчера сутки не спал:wacko: ).Надо просто рассмотреть каждую клетку с поставленным крестиком/ноликом на наличие ряда из 5 таких фишек.Т.е. рассмотреть надо 4 стороны для каждой клетки в которую сделан ход.
Тему можно считать закрытой:) .
Alice Mizer
30.05.2006, 23:59
Ну и ужасный алгоритм. Я вынесу сразу твою программу. Можно взять потом побаловаться?
Ага, ужасный то ужасный, но времени нет думать над чем то более лучшим.В пятницу последний срок сдачи.Ходы он делает наугад:) , так что там выносить то нечего, хотя если его улучшить(как написано выше), то возможно получится что то стоящее.
З.Ы. to Alice Mizer
Из профиля : Чем занимаетесь:
Работа - дизайнер
Програмированием тож увлекаешься:) ?
Alice Mizer
31.05.2006, 01:06
Дизайнер не цветочки рисовать, а делать большие проекты, с вычислениями. Там в ход всякие встроенные псевдоязыки идут. Да и само программирование пробовала. Я увлекаюсь разного рода играми, ведь компьютер - мой лучший друг. Не помню как называется игра вроде Колобот. Так там на чем-то похожем на Си нужно програмировать юнитов! Научилась! Но я сам Си знаю оч плохо, учили только Паскалю (ну то есть дельфи, он хоть под окошками работает) и Basic (не смейся, с него многи начинали наверно).
Ну так вот, увлекаюсь разного рода играми. В крестики нолики на компьютере столько играла, что знаю много хороших ходов.. они просто не поддаются таким алгоритмам, там придется рассматривать кучи специальных вариантов и еще много много всего...
Из того что связано с компом пожалуй совсем не шарю в интернете и ХТМЛ с Явой=( Хочу Яве научиться=)))
ведь компьютер - мой лучший друг.
Вах! Зачем же так?
Alice Mizer, сложилось ощущение что понятия Java и JavaScript для тебя одно и то же. Хочу предостеречь от этого жуткого заблуждения. :) Java выучить, зная C++ и ООП - дело пары дней. :) Реально любой язык учится за пару недель.
HTML - Это не программирование, а разметка текста и ни чего интересного в этом нет. Жуткое занятие, надоедает быстро. Можно кое-что на JavaScript/VBScript запрограммить для красивости или интерактивности. Последнее время распространение активно получает Ajax и подобные технологии. Они активно используют динамическую подгрузку данных с помощью JavaScript.
Так что задача разобраться в интеренете, хтмл и ява очень многосторонняя и требет уточнения. ;)
пользуясь случаем... нету ли у 3 и выше курса книжки "Сетевые операционны системы"? )
Inxo, кажется была в электронном виде. И кажется даже на филесе была.
Нашел, только здесь на форуме архивчик не прикрепить. :)
Alice Mizer
31.05.2006, 01:52
В смысле я плохо шарю в том что связано с нетом, с хтмл, и с Явой.
Victors Яве я хотела бы научиться именно языку, а не Яваскрипт.
Я отлично знаю что такое ХТМЛ но не знаю почти тегов. Тот же ББкод и то больше мне известен - на форумах он часто как более простая аналогия ХТМЛ для постов...
Ну а в интернете - вообще не понимаю как все устроено, и как передается =)) Вооот.
Но я сам Си знаю оч плохо
Опечатка? Или нет:huh:
Опечатка? Или нет:huh:
Речь вроде идет о языке;) .
Опечатка? Или нет:huh:
тожа начали закрадываться смутные сомнения ? :duma:
Alice Mizer
31.05.2006, 15:36
ЛОЛ=)))
По-моем у было бы странно написать "сама [язык] Си" или "сама [язык] Паскаль"
Не сдавали экзамен по русскому языку дети? :lol:
N0rd, ну как, сдал свой алгоритм?
Да, все проги по комбалгам сданы:) , завтра зачет по операционным системам:( , 80 вопросов надо подготовить:wacko: .
СЕТЕВЫМ операционкам? Пономареву? Если да, то мелочи. :) Халявнее зачета я не видел. :) Не помню почему, но мне вспоминается что я почему-то сдавал на пересдаче. Хотя точно сдавал ровно 1 раз и без малейших проблем.
Завтра пересдача:) , к четвергу я не успел прочитать все вопросы, и попались как раз те которых не знал:) , халява то халява, но когда присутствовал примерно на 10% лекций, придется всю книгу прочитать(а енто около 500 страниц:wacko: ). Но ничего, вся ночь впереди:), время готовиться есть:) .
vBulletin® v3.8.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd. Перевод: zCarot