Вход | Регистрация

Форумы на Кубань.Ру


О жизни... ::

Метки:

ОФФ : Алгоритм шахмат...

Ø
Я
   Партизан
27.01.06 - 13:47
Когда-то давно , будучи школьником , занимался шахматами - возили нас в 1986 году в Чехославакию на турнир , были там в какой-то лаборатории - уже и не помню точно , но там был шахматный компьютер , вроде говорили "сильный для того времени" - но играл он на уровне 2-3 разряда , обыграли его без труда. Сейчас на любом развале с компьютерными дисками можно купить программу , например Chessmaster , с которой играть на максимальном уровне практически нет никаких шансов , 1 партию вроде из 50-60 выиграл (перехаживать пришлось много раз). Давно уже интересно , слышал кто-то или читал может быть , что за алгоритм используется для шахматной программы , как постороен ? Читал где-то здесь , что NS написал свои собственные шахматы - интересно было -бы услышать , насколько сильно играет программа и что за алгоритм был использован ?
 
  AdBlock убивает бесплатный контент
   GarryZ
1 - 27.01.06 - 14:01
Скачай с "Клуба профессионалов 1С" эти шахматы, поиграй и оцени уровень. А если еще и макроязыком 7.7. владеешь, то можешь и алгоритм посмотреть - ert файл открытый.
   Дурочка 1С
2 - 27.01.06 - 14:05
Алгоритм один - перебор возможных ходов и оценка позиции. Выбирается ход с максимальным коэффициентом усиления позиции ...
   Партизан
3 - 27.01.06 - 14:08
(1)Спасибо , сейчас поищу
   NS
4 - 27.01.06 - 14:17
Шахматы писались очень давно, и криво написаны.
Алгоритмы -
NegaScout,
Метод пустого хода,
Продления на отходах от шаха,
Форсированный вариант (только взятия)
Хеш таблица (только лучшие ходы, нет хеша перекрестных позиций),
Сортировка ходов.
Оценка - матирал + Положения (централизация) фигур.
Дебютная библиотека.
...
Есно программа играет полностью по правилам ФИДЕ (правила рокировок, взятие на проходе, правило пятидесяти ходов, троектратное повторение позиции)
Сила игры программы - второй разряд.
Скачать можно тут -
http://itland.ru/rep/index.php?id=339
   NS
5 - 27.01.06 - 14:19
Сила игры невысока из-за низкого быстродействия встроенного языка 1С (в тысячи раз медленней, чем компиляторы С++)
   Djkxfhf
6 - 27.01.06 - 14:22
приятнее быть единственным и лучшим написавшим на 1С, чем "кем-то" из написавших на с++
   NS
7 - 27.01.06 - 14:29
(6) Будет и версия на С++, так как хочется посоревноваться.
Только есно не хочется начинать с последней лиги - так что будет выложена только при достижении определенной силы игры.
 В России - шесть играющих шахматных программ (под WinBoard, UCI, и участвуют в соревнованиях), из них две, несмотря на чудовищную разницу в быстродействии языков играют слабее моей...
   Партизан
8 - 27.01.06 - 14:30
В клуб профессоналов пока не добраться - сервер пергружен.
(2) В общем , я думаю , это всем понятно. Но если подойти конкретно , то начинаются вопросы.
Что значит оценить позицию ? Как ее будет оценивать машина ? Например , есть в шахматах , как всем известно , общая стратегия (это все грубо , ясно , что не всегда это верно - но в общем)- захватывай пешками центр , ставь фигуры активно , ладьями захватывай открытые линии , конем занимай форпосты , пешки ставь на клетки не по цвету слона (если слон остался один), не ослабляй позицию короля (без нужды не ходи пешками от короля , если сделана рокировка) и т.д. и т.п. - но вот просчитали на 10 ходов , например , - и как оценить ? Ведь часто бывает такое , что у тебя открытая линия , ты владеешь центром , фигуры у тебя вроде активные - а позиция у тебя проигранная....
   Wasya
9 - 27.01.06 - 14:36
http://1c.realnet.ru/cgi-bin/forum.cgi?ask=21923
NS не обижайся ты все равно круче всех, но это взгял с другой стороны
   NS
10 - 27.01.06 - 14:39
(8) Ссылка в (4)
Насчет оценки - самое главное - материальная составляющая (пешка -1, конь.слон - 2, ладья - 5, ферзь - 9)
На втором месте - положение фигур - для каждого вида фигур прописываем таблицу с оценкой для каждой клетки доски - например белый конь на "b1" ценится меньше, чем он-же на "e5". А король на "е1" - меньше, чем король на "g1".
 Потом - обязателен ФВ, а то ты оценишь позицию с лишней пешкой, когда очередь хода за соперником, а у тебя ферзь под боем...
 Насчет признаков оценки - согласно постулатам Стейница - Одни преимущества могут переходить в другие... Так что при большой глубине перебора - программа в расчетах просто переведет непонятное еёй преимущество - в понятное ;-))
 
  AdBlock убивает бесплатный контент
   Дурочка 1С
11 - 27.01.06 - 14:41
Как, как ... Числами! Как еще может оценивать позицию компьютер?
Вводишь правила:
пешка под боем -1
конь под боем -5
шах королю -20
...
напал на ферзя +50
поставил на связку +3
...
...
Итого стоимость позиции = ...
Делаешь ход, снова считаешь ...
Что тут может быть не понятного?
Вся разница в программах только в скорости железа и, самое главное, в оптимизации перебора ходов ...
   NS
12 - 27.01.06 - 14:45
(9) Посмотри мой диалог с автором ветки - посты (44,46,47,48)
Автор только к этим постам понял какова-же разница в быстродействии.
И что программа писалась не ради интерфейса и удобства - а на спор.
Поэтому и нет сохранения партий, листинга партии и т.д.
По условиям спора это было не нужно.
   MMF
13 - 27.01.06 - 14:46
все-таки современный путь развития компьютерной игры в шахматы - экстенсивный. Одна идея альфа-бетта отсечения и куча ее вариаций. В ГО так не выиграть. Плохо, что Ботвинник оказался просто болтуном, его идея траекторий привлекательно выглядела.
   NS
14 - 27.01.06 - 14:57
(13) Точно так-же программы играют и в ГО.
На данный момент достигнута сила ПОЧТИ ;-) первого дана.
 На данный момент - все сильнейшие программы в шахматы используют полный перебор, и все они на персоналках в матче - очень легко сделают ЛЮБОГО ШАХМАТИСТА.
 И идеи Ботвиника признаны бредовыми - вместо того, чтоб смотреть НЕ ВСЕ ХОДЫ, мы, после определенных ходов можем либо обрывать перебор по некоторым признакам, либо сокращать его - именно этот метод и используется (Для сокращения перебора используются ЧЕТЫРЕ метода - Футилити пурнинг, Хистори Пурнинг, Ребель Редукшн и метод пустого хода, принципиальное значение имеет только последний, именно он здорово повышает силу игры, и позволяет современным программам считать на 15 полуходов и дальше, даже в середине партии)
   NS
15 - 27.01.06 - 14:59
(13) +14
И очент наверно некрасиво не разбираясь в вопросе так категорично заявлять.
Да в ГО есть очень большая проблема, но заключается она в том, ЧТО АБСОЛЮТНО НЕПОНЯТНО, КАК ОЦЕНИВАТЬ ПОЗИЦИЮ!!!!
Программы не могут корректно во всех случаях даже посчитать очки в конечной позиции (когда закончилась партия).
   Партизан
16 - 27.01.06 - 15:04
(10) Спасибо большое , скачал по ссылке - смотрю.. Вообще-то не ожидал такое увидеть в 7.7...
Вообще , в эндшпиле король на "е1" будет сильнее , чем на "g1" в общем случае , и понятно , что можно придумать позицию , где конь на "b1" будет сильнее чем на "е5"..
(11) Что числами , это понятно без восклицательных знаков. Вполне просто возможно , что после всей оценки , белые , нарпимер , имея большую сумму при оценке хода имеют в то же время проигранную позицию..
(10)Интересно , предусмотрено ли в алгоритме что-то для решения этого ?
-----
Ухожу домой , очень все это интересно , т.к. 1/3 жизни прошла в шахматах , сам когда-то хотел писать шахматы на С++ , дома посомтрю использованный алгоритм - интересно...
   NS
17 - 27.01.06 - 15:09
(16) Оценка только по положению используется только в условиях низкого быстродействия.
 Насчет эндшпиля ты прав - у меня в программе - используется три набора оценок - для дебюта, миттельшпиля и эндшпиля, так что с пробежкой короля в центр в конце партии - у программы проблем нет. (ну и соответственно с матованием одинокого короля двумя слонами, королем и ладьей и т.д. - программа понимает, что нужно оттеснять короля соперника к краю и в угол - и соответственно оттесняет и матует), кстати есть прикол - программа - чемпион на доске 8х10 - этого делать не умеет ;-))
   NS
18 - 27.01.06 - 16:56
(16) Насчет (10) Если про перетекание - то да, сделано - перебор.
Для перебора используется Negascout/PVS - метод дерева нулевой ширины (модификация альфа-беты (метода ветвей и границ))
   Партизан
19 - 05.02.06 - 11:31
Что-то не было времени , - вот только более-менее осовободился.
(17,18) Сергей , когда смотрел твою программу - вспомнил про Леонардо да Винчи , он пытался в 16 веке построить и летательный аппарат , и водолазный костюм , и лодку подводную если память не изменяет и т.д. и т.п Т.е. используя минимум средств получить нечто. Такие люди и двигают вперед человечество.. Вообще , когда поднимал данную тему , хотелось получить вот какую информацию. Как устроен алгоритм оценки позиции шахматной программы играющей в силу 2-3 разряда примерно и так было ясно. Т.е. это программа , которая по сути ориентирована на анализ матования короля+материальные приобретения. Интересно было узнать , как построен алгоритм оценки позиции, играющий , например , в силу мастера спорта-гроссмейстера. Это тот уровень , где алгоритм должен быть наверное существенно дополнен - но как ? Ведь там как-то надо оценивать вещи трудно уловимые даже для сильного шахматиста. Ведь вообще всех вариантов машина перебрать не может - жизни не хватит. Пусть сильная программа , перебрала , предположим 10-20 ходов , на каком-то моменте надо оценивать позицию. Как это сделать ? Ведь можно иметь лишнюю пешку (и любой другой материал) - но иметь ПРОИГРАННУЮ позицию (я специально выделяю слово "проигранную" - не "плохую" , а именно "проигранную" , потому что если , например , просто в алгоритм заложить стандартную оценку - ну типа владение открытыми линиями , форпосты для коней, преимущество двух слонов , фигуры или пешки занимают центр , король хорошо прикрыт пешками или наоборот пешечное прикрытие короля ослаблено и т.д. и т.п. - то все эти стандартные плюсы могут быть у одной стороны т.е. машина оценит его позицию с чисто позиционной точки зрения как "хорошую", более лучшую , чем у противника, и материал у него может быть лишним , но позиция будет ПРОИГРАННОЙ ,). Сергей , не читал об этом что-нибудь ? Интересно , как собираешься совершенствовать алгоритм оценки позиции ?(вроде-ты писал где-то , что собираешься увеличивать силу игры программы)
   Партизан
20 - 06.02.06 - 09:08
(?)



Список тем форума

Форум Территория 1С

AdBlock убивает бесплатный контент   AdBlock убивает бесплатный контент
Компьютеры — прекрасное средство для решения проблем, которых до их появления не было.
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Ветка сдана в архив. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
AdBlock убивает бесплатный контент