Ответ
 
Опции темы
Старый 30.05.2006, 07:45      #1
N0rd
Модератор
[Epic]
[Legion]
Пользователь Mozilla Firefox
 
Аватар для N0rd
 
Регистрация: 08.04.2006
Возраст: 31
Сообщений: 3,104
Пользователь играет в Call Of Duty 2Пользователь играет в Call Of Duty 4
По умолчанию Алгоритм игры рендзю

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

З.Ы. А алгоритм туповатый какой то, ходит наугад , ну слава богу хоть работает .
N0rd вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 30.05.2006, 11:19      #2
Frosty
Местный
Пользователь Mozilla Firefox
 
Аватар для Frosty
 
Регистрация: 02.04.2006
Возраст: 27
Сообщений: 2,582
По умолчанию

Алгоритма не знаю, но я открыл для себя чето новое: оказывается та хрень которой мы мудились целый год называется рендзю!
Frosty вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 30.05.2006, 12:51      #3
N0rd
Модератор
[Epic]
[Legion]
Пользователь Mozilla Firefox
 
Аватар для N0rd
 
Регистрация: 08.04.2006
Возраст: 31
Сообщений: 3,104
Пользователь играет в Call Of Duty 2Пользователь играет в Call Of Duty 4
По умолчанию

Я нашел не очень сложный алгоритм(некоторые из них, тянут на магистранскую работу ) и написал прогу за пару часов, уместилась в ~ 310 строк(в полном варианте думаю около 400 будет).Теперь только проверку добавить и усе .
N0rd вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 30.05.2006, 13:56      #4
Alice Mizer
Пользователь
 
Аватар для Alice Mizer
 
Регистрация: 24.05.2006
Сообщений: 269
Пользователь играет в Call Of Duty 2
По умолчанию

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

[7th legion]

Последний раз редактировалось Alice Mizer; 30.05.2006 в 19:19.
Alice Mizer вне форума Пол: Женщина   Ответить с цитированием Вверх
Старый 30.05.2006, 17:59      #5
Pavel Boyko
Пользователь
 
Аватар для Pavel Boyko
 
Регистрация: 22.04.2006
Адрес: Птз
Сообщений: 128
Пользователь играет в Call Of Duty 2
По умолчанию

Nord! Так не сказал, на каком языке алгоритм катал.
С++, Delphi?
__________________
Борись! А то
Pavel Boyko вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 30.05.2006, 18:34      #6
Кролль
Firefox User
Пользователь Mozilla Firefox
 
Аватар для Кролль
 
Регистрация: 07.04.2006
Адрес: Греческий полис ПетроЗаВодкуС
Сообщений: 1,296
Пользователь играет в Call Of Duty 2
По умолчанию

Цитата: Pavel Boyko
Nord! Так не сказал, на каком языке алгоритм катал.
С++, Delphi?
Господи! Ничего, что я тут рядом стою?! Может, мне отойти?
__________________
Эволюция, Феликс! До Schweppes надо дорасти!(с) Гепард из рекламы =)
Подневольный солдат.|||

Последний раз редактировалось Кролль; 30.05.2006 в 18:34.
Кролль вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 30.05.2006, 19:15      #7
Frosty
Местный
Пользователь Mozilla Firefox
 
Аватар для Frosty
 
Регистрация: 02.04.2006
Возраст: 27
Сообщений: 2,582
По умолчанию

Цитата: Кролль
Господи! Ничего, что я тут рядом стою?! Может, мне отойти?
Это ты о чем?
Frosty вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 30.05.2006, 19:19      #8
Alice Mizer
Пользователь
 
Аватар для Alice Mizer
 
Регистрация: 24.05.2006
Сообщений: 269
Пользователь играет в Call Of Duty 2
По умолчанию

Pavel Boyko а какая разница-то?
__________________
Первым делом мы испортим самолеты!

[7th legion]
Alice Mizer вне форума Пол: Женщина   Ответить с цитированием Вверх
Старый 30.05.2006, 20:18      #9
Kotor
Местный
[BATTLE]TEAM
Пользователь Mozilla Firefox
 
Аватар для Kotor
 
Регистрация: 28.03.2006
Адрес: henkou.onego.ru
Сообщений: 969
По умолчанию

Цитата: Frosty
Это ты о чем?
видимо о том что выделил в цитате))))
Kotor вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 30.05.2006, 21:45      #10
N0rd
Модератор
[Epic]
[Legion]
Пользователь Mozilla Firefox
 
Аватар для N0rd
 
Регистрация: 08.04.2006
Возраст: 31
Сообщений: 3,104
Пользователь играет в Call Of Duty 2Пользователь играет в Call Of Duty 4
По умолчанию

Цитата: 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 стороны для каждой клетки в которую сделан ход.
Тему можно считать закрытой .
N0rd вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 30.05.2006, 23:59      #11
Alice Mizer
Пользователь
 
Аватар для Alice Mizer
 
Регистрация: 24.05.2006
Сообщений: 269
Пользователь играет в Call Of Duty 2
По умолчанию

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

[7th legion]
Alice Mizer вне форума Пол: Женщина   Ответить с цитированием Вверх
Старый 31.05.2006, 00:09      #12
N0rd
Модератор
[Epic]
[Legion]
Пользователь Mozilla Firefox
 
Аватар для N0rd
 
Регистрация: 08.04.2006
Возраст: 31
Сообщений: 3,104
Пользователь играет в Call Of Duty 2Пользователь играет в Call Of Duty 4
По умолчанию

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

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

Последний раз редактировалось N0rd; 31.05.2006 в 00:09.
N0rd вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 31.05.2006, 01:06      #13
Alice Mizer
Пользователь
 
Аватар для Alice Mizer
 
Регистрация: 24.05.2006
Сообщений: 269
Пользователь играет в Call Of Duty 2
По умолчанию

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

[7th legion]
Alice Mizer вне форума Пол: Женщина   Ответить с цитированием Вверх
Старый 31.05.2006, 01:18      #14
Moralis
Местный
[Epic]
 
Аватар для Moralis
 
Регистрация: 03.04.2006
Сообщений: 2,818
По умолчанию

Цитата: Alice Mizer
ведь компьютер - мой лучший друг.
Вах! Зачем же так?
__________________
N0rd в стиме
Moralis вне форума   Ответить с цитированием Вверх
Старый 31.05.2006, 01:19      #15
VictorS
Местный
Пользователь Mozilla Firefox
 
Регистрация: 27.03.2006
Сообщений: 3,201
По умолчанию

Alice Mizer, сложилось ощущение что понятия Java и JavaScript для тебя одно и то же. Хочу предостеречь от этого жуткого заблуждения. Java выучить, зная C++ и ООП - дело пары дней. Реально любой язык учится за пару недель.
HTML - Это не программирование, а разметка текста и ни чего интересного в этом нет. Жуткое занятие, надоедает быстро. Можно кое-что на JavaScript/VBScript запрограммить для красивости или интерактивности. Последнее время распространение активно получает Ajax и подобные технологии. Они активно используют динамическую подгрузку данных с помощью JavaScript.
Так что задача разобраться в интеренете, хтмл и ява очень многосторонняя и требет уточнения.
VictorS вне форума   Ответить с цитированием Вверх
Старый 31.05.2006, 01:24      #16
Inxo
Местный
[Legion]
 
Аватар для Inxo
 
Регистрация: 20.03.2006
Адрес: 127.0.0.1
Сообщений: 710
По умолчанию

пользуясь случаем... нету ли у 3 и выше курса книжки "Сетевые операционны системы"? )
__________________
inxo.ru
Inxo вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 31.05.2006, 01:26      #17
VictorS
Местный
Пользователь Mozilla Firefox
 
Регистрация: 27.03.2006
Сообщений: 3,201
По умолчанию

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

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

Последний раз редактировалось VictorS; 31.05.2006 в 01:29.
VictorS вне форума   Ответить с цитированием Вверх
Старый 31.05.2006, 01:52      #18
Alice Mizer
Пользователь
 
Аватар для Alice Mizer
 
Регистрация: 24.05.2006
Сообщений: 269
Пользователь играет в Call Of Duty 2
По умолчанию

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

[7th legion]
Alice Mizer вне форума Пол: Женщина   Ответить с цитированием Вверх
Старый 31.05.2006, 14:16      #19
Frosty
Местный
Пользователь Mozilla Firefox
 
Аватар для Frosty
 
Регистрация: 02.04.2006
Возраст: 27
Сообщений: 2,582
По умолчанию

Цитата: Alice Mizer
Но я сам Си знаю оч плохо
Опечатка? Или нет
Frosty вне форума Пол: Мужчина   Ответить с цитированием Вверх
Старый 31.05.2006, 14:18      #20
N0rd
Модератор
[Epic]
[Legion]
Пользователь Mozilla Firefox
 
Аватар для N0rd
 
Регистрация: 08.04.2006
Возраст: 31
Сообщений: 3,104
Пользователь играет в Call Of Duty 2Пользователь играет в Call Of Duty 4
По умолчанию

Цитата: Frosty
Опечатка? Или нет
Речь вроде идет о языке .

Последний раз редактировалось N0rd; 31.05.2006 в 14:19.
N0rd вне форума Пол: Мужчина   Ответить с цитированием Вверх
Ответ


Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 
Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
S.T.A.L.K.E.R.: Shadow of Chernobyl a2z Action 1291 09.10.2011 20:00
Mirror's Edge d1sco Action 317 13.02.2010 19:17
COD2: Обновления, моды, патчи, полезные программы Vadim Call Of Duty 2 293 04.07.2009 15:11
ЧМ по хоккею 2009 BulkiN Спорт 314 14.05.2009 19:42
Xenus 2: Белое золото AcE Action 56 15.11.2008 14:04


Обратная связь
Текущее время: 17:45. Часовой пояс GMT +3.


Powered by vBulletin® Version 3.8.4
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd. Перевод: zCarot