Алгоритм игры рендзю

[N0rd]

Как мне известно, многие из форумчан являются студентами матфака, хотел попросить у вас помощи(да и у всех кто занимается програмированием).Вообщем по предмету комбинаторные алгоритмы мне задали написать игру рендзю : крестики - нолики на доске произвольного размера, пять в ряд.Большую часть программы написал(реализовал алгоритм на основе оценочной функции), проблема появилась в самом конце : как проверять на выигрышь одного из игроков?В обычных к-н это легко, простым перебором, благо поле не большое, а как быть с полем большого размера?
Надеюсь на помощь, в пятницу надо как то сдавать программу.

З.Ы. А алгоритм туповатый какой то, ходит наугад , ну слава богу хоть работает .

[Frosty]

Алгоритма не знаю, но я открыл для себя чето новое: оказывается та хрень которой мы мудились целый год называется рендзю!

[N0rd]

Я нашел не очень сложный алгоритм(некоторые из них, тянут на магистранскую работу ) и написал прогу за пару часов, уместилась в ~ 310 строк(в полном варианте думаю около 400 будет).Теперь только проверку добавить и усе .

[Alice Mizer]

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

[Pavel Boyko]

Nord! Так не сказал, на каком языке алгоритм катал.
С++, Delphi?

[Кролль]

Цитата: Pavel Boyko Nord! Так не сказал, на каком языке алгоритм катал. С++, Delphi?

Господи! Ничего, что я тут рядом стою?! Может, мне отойти?

[Frosty]

Цитата: Кролль Господи! Ничего, что я тут рядом стою?! Может, мне отойти?

Это ты о чем?

[Alice Mizer]

Pavel Boyko а какая разница-то?

[Kotor]

Цитата: Frosty Это ты о чем?

видимо о том что выделил в цитате))))

[N0rd]

Цитата: Alice Mizer Хорошо Просто при очередном ходе проверять не входит ли он в пятерку подряд поставленных символов, содержащих новый элемент. Оценка же у тебя пересчитывает не все поле а только зону нового символа, надеюсь? Расскажи какой алгоритм использовал можно в личку если не лень а я посмотрю что можно сделать

Вот в чем состоит реализованный мной алгоритм :
"Итак с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атегия, но я ее не нашел."
(ц)Алголист
Оценка высчитывается для каждой клетки, далее ход делается в самую "важную" клетку.
С проверкой на победу мне уже подсказали, оказалось это самое легкое , даж не знаю как сам не додумался(наверно сказывается постоянное невысыпание - вчера сутки не спал ).Надо просто рассмотреть каждую клетку с поставленным крестиком/ноликом на наличие ряда из 5 таких фишек.Т.е. рассмотреть надо 4 стороны для каждой клетки в которую сделан ход.
Тему можно считать закрытой .

[Alice Mizer]

Ну и ужасный алгоритм. Я вынесу сразу твою программу. Можно взять потом побаловаться?

[N0rd]

Ага, ужасный то ужасный, но времени нет думать над чем то более лучшим.В пятницу последний срок сдачи.Ходы он делает наугад , так что там выносить то нечего, хотя если его улучшить(как написано выше), то возможно получится что то стоящее.

З.Ы. to Alice Mizer
Из профиля : Чем занимаетесь:
Работа - дизайнер
Програмированием тож увлекаешься ?

[Alice Mizer]

Дизайнер не цветочки рисовать, а делать большие проекты, с вычислениями. Там в ход всякие встроенные псевдоязыки идут. Да и само программирование пробовала. Я увлекаюсь разного рода играми, ведь компьютер - мой лучший друг. Не помню как называется игра вроде Колобот. Так там на чем-то похожем на Си нужно програмировать юнитов! Научилась! Но я сам Си знаю оч плохо, учили только Паскалю (ну то есть дельфи, он хоть под окошками работает) и Basic (не смейся, с него многи начинали наверно).
Ну так вот, увлекаюсь разного рода играми. В крестики нолики на компьютере столько играла, что знаю много хороших ходов.. они просто не поддаются таким алгоритмам, там придется рассматривать кучи специальных вариантов и еще много много всего...
Из того что связано с компом пожалуй совсем не шарю в интернете и ХТМЛ с Явой=( Хочу Яве научиться=)))

[Moralis]

Цитата: Alice Mizer ведь компьютер - мой лучший друг.

Вах! Зачем же так?

[VictorS]

Alice Mizer, сложилось ощущение что понятия Java и JavaScript для тебя одно и то же. Хочу предостеречь от этого жуткого заблуждения. Java выучить, зная C++ и ООП - дело пары дней. Реально любой язык учится за пару недель.
HTML - Это не программирование, а разметка текста и ни чего интересного в этом нет. Жуткое занятие, надоедает быстро. Можно кое-что на JavaScript/VBScript запрограммить для красивости или интерактивности. Последнее время распространение активно получает Ajax и подобные технологии. Они активно используют динамическую подгрузку данных с помощью JavaScript.
Так что задача разобраться в интеренете, хтмл и ява очень многосторонняя и требет уточнения.

[Inxo]

пользуясь случаем... нету ли у 3 и выше курса книжки "Сетевые операционны системы"? )

[VictorS]

Inxo, кажется была в электронном виде. И кажется даже на филесе была.

Нашел, только здесь на форуме архивчик не прикрепить.

[Alice Mizer]

В смысле я плохо шарю в том что связано с нетом, с хтмл, и с Явой.
Victors Яве я хотела бы научиться именно языку, а не Яваскрипт.
Я отлично знаю что такое ХТМЛ но не знаю почти тегов. Тот же ББкод и то больше мне известен - на форумах он часто как более простая аналогия ХТМЛ для постов...
Ну а в интернете - вообще не понимаю как все устроено, и как передается =)) Вооот.

[Frosty]

Цитата: Alice Mizer Но я сам Си знаю оч плохо

Опечатка? Или нет

[N0rd]

Цитата: Frosty Опечатка? Или нет

Речь вроде идет о языке .