Главная › Форумы › Шашечные программы › Шашечные программы › Программирование русских шашек и чекерса
- В этой теме 69 ответов, 12 участников, последнее обновление 10 лет, 8 месяцев назад сделано
AlexanderS.
-
АвторСообщения
-
25.06.2004 в 23:47 #345699
Damon
УчастникАлемо (насчет коэффициента ветвления):
Речь — именно о числе разветвлений «в среднем», увеличение которого в русских за счет дамок Вы признаете.
Что касается случая 2, то как же он может повлиять на этот коэффициент?? — бьем назад, и все!!!…
Сергей Педько26.06.2004 в 00:19 #345700alemo
УчастникСергей, Вы всё абсолютно правильно поняли и догадались, к чему я клоню. Я принимаю и не собираюсь оспаривать (если серьёзные люди говорят — я им верю) факт на который тут ссылались насчёт более высокого В СРЕДНЕМ коэффициента разветвления в русские шашки. Вот мы и подобрались (?) к истине ! Именно за счёт дамок этот СРЕДНИЙ коэффициент и выше в русских шашках. Дамки всё вытянули !
Только я боюсь, что эта истина не совсем та, которую некоторые наверное хотели бы услышать. В частности Алканд своими вопросами упорно подталкивал к мысли, что русские шашки — более сложная позиционная игра. А получили … дамки. И то это влияет только на коэффициент, так как в затяжных эндшпилях в чекерс требуется намного больше ходов (читай позиций). Там, где дамке в русские шашки требуется 1 ход, в чекерс — 3-4 или больше. Так что в эндшплях в чекерс надо считать «дальше», а в русские шашки — «глубже». Согласны ?
Каков процент собственно эндшпилей в игре ? Пусть практики ответят мне. А если хотите — давайте вычислим отдельно коэффициент для эндшпилей и до дамок.
А. Моисеев
26.06.2004 в 07:37 #345701plus600
УчастникАлександр!
Давайте еще раз отделим мух от котлет. Я говорил только о сравнении двух игр с точки зрения их программирования. С этой точки зрения совершенно не важно соотношения коэффициента ветвления в текущей позиции, для этого важно среднее его значение при проходе по дереву перебора из этой текущей позиции. Как пример, из начальной позиции в переборе дамки возникают очень быстро. И дерево перебора в черерсе почти всегда (исключения я допускаю, но не видел пока) будет содержать значительно меньше позиций, чем в русских шашках при одинаковой глубине перебора.
Да, концовки в чекерсе нужно считать дальше, но (опять же факт) именно в концовках отношение коэффициента ветвления еще больше увеличивается.
А чем доказан этот факт я уже писал — это сравнение чисел для одного и того же движка для этих игр.
Вообще, сложность для программирования переборных игр зависит только от двух параметров — коэффициента ветвления и сложности формализации оценочной функции. Поэтому и получается, что чекерс для программирования более простая игра, чем русские шашки.
Еще раз оговорюсь, что из этого совершенно не следут вывод о том, какая игра проще — это совсем другие критерии!!!С уважением,
Сергей Старцев26.06.2004 в 07:41 #345702plus600
Участнику меня каждая позиция содержит один ход
Сергей, а сейчас я не совсем Вас понял. Разве не существует дебютных позиций с несколькими возможными ходами?
:
Конечно существуют. Но если в позиции есть два хода, то это тоже самое, что хранить две позиции после этих ходов.
26.06.2004 в 11:49 #345703Greb
УчастникU menya drugoye otnosheniye
Согласен. Допустим, завтра Старцев скажет — моя программа просчитала все… белые начинают и выигрывают. Ну и что? Все равно Кандауров у меня выиграет (может). Это главное.
26.06.2004 в 12:09 #345704MiG
УчастникСогласен. Допустим, завтра Старцев скажет — моя программа просчитала все… белые начинают и выигрывают. Ну и что? Все равно Кандауров у меня выиграет (может). Это главное.
А вот это абсолютно неправильная постановка вопроса.Решение проблемы шашек и игра между людьми — суть разные вещи. Они, конечно, пересекаются между собой, но не так, как сказал Greb.
Также не совсем понимаю Symix`а. Современные игровые программы предоставляют достаточно возможностей не только для игры, но и для изучения шашек. Вот, например, эндшпильные базы предоставляют нам беспрецедентные возможности для анализа и изучения эндшпиля. Просто, не все ещё это понимают.
Кроме этого, для изучения шашек существуют базы данных партий.
С уважением,
МиГ.26.06.2004 в 13:28 #345705alemo
УчастникВообще, сложность для программирования переборных игр зависит только от двух параметров — коэффициента ветвления и сложности формализации оценочной функции. Поэтому и получается, что чекерс для программирования более простая игра, чем русские шашки.
Очень любопытно. То что вы пишите здорово перекликается с тем, что ответил мне Эд Трайс, когда я спросил его о сложности. Приведу здесь кусочек из его ответа:
==============================================================
<< Do you think those two numbers can be use to compare "complexity" of two games, or this is impossible, and it's more like apples-oranges task
? >>There are a few things you have to consider:
1. Space complexity. The number of positions that need to be searched.3
2. Decision complexity. The abstract «difficulty» of making correct
decisions.As you saw when playing the 4×3 ending that was a win, the space complexity was small (only a few moves to consider for the winning side) but the decision complexity was high (it was hard to find the win many times, and so a draw was allowed.)
Some games have already been solved that have very high space complexity but low decision complexity. G0-Moku has 10^105th power positions, but it has been solved due to very low decision complexity. It is very easy to find the right path to continue.
Connect-Four has 10^14 positions and has been solved since 1989.
So, which game has a greater space complexity? Probably 10×10 draughts, easily. But, since 10×10 draughts has kings that move like Bishops, checkers may have the greater decision complexity.
============================================================
Одно и тоже ! Не совсем только понятно со вторым критерием — почему вы считаете, что сложность формализации, или как Эд Трайс говорит — сложность решения, в русских шашках выше ?
А. Моисеев
26.06.2004 в 13:33 #345706plus600
УчастникОдно и тоже ! Не совсем только понятно со вторым критерием — почему вы считаете, что сложность формализации, или как Эд Трайс говорит — сложность решения, в русских шашках выше ?
А. Моисеев
А я так и не считаю. Этот фактор достаточно одинаков в этих двух играх. Нюансы есть, но проблемы похожие. Что точно могу сказать — так и там и там это намного сложнее, чем в шахматах…
26.06.2004 в 13:36 #345707plus600
УчастникU menya drugoye otnosheniye
Согласен. Допустим, завтра Старцев скажет — моя программа просчитала все… белые начинают и выигрывают. Ну и что? Все равно Кандауров у меня выиграет (может). Это главное.
Я тоже абсолютно с этим согласен. Решение шашечной задачи интересно только программистам, игрокам от этого толку очень мало
.
На эту тему я уже высказывался, и своей позиции пока не менял и не собираюсь. Также я по прежнему открыт для всех пожеланий пользователей.26.06.2004 в 14:12 #345708sancoder
УчастникАлександр, ну я же ваши ответы читаю….
А вы мои? Речь идет не о игре в базе, а о игре до ЭБ. То, что игра в ЭБ была пройдена (несколько лет назад) — верю. То, что из позиции с 12 шашками на доске он точно определит ничью — НЕТ! НЕ ВЕРЮ.26.06.2004 в 14:33 #345709alemo
УчастникЯ ему (Эду Трайсу) — ВЕРЮ. Он же приводил в своём ответе конфигурацию машины (из университета), к которой он получил доступ. Это же не машина, а какой-то монстр. Эд сам писал, что это даже не персональный компьюьер, а workstation. RAM у него — 128 GB (гегабайт!) и всю свою эндшпильную (почти всю 10-фигурную), а впрочем уже и не совсем эндшпильную, базу он загружает в оперативную память.
Кроме того Эд указывал, что это не полный перебор, так как число всех позиций в 10-фигурной базе — 8.5 триллионов, а его программа перебирает только 120 миллионов (4млн/сек х 30 сек). Только программа не только перебирает за это время, но ещё и оценивает, принимает решение — так, что это возможно.
Вот если гроссмейстер смотрит на позицию и говорит — здесь есть только два хода, имеющие смысл — вы ему верите ? А почему же вы не верите программе, которая тоже делает какие-то отсечения ?
К примеру gf4 hg5 … должна ли программа продолжать поиск и анализ в этом «варианте» до ЭБ или может остановиться ?
А. Моисеев
26.06.2004 в 14:57 #345710sancoder
УчастникЗнаете, Александр, дело не в том, какая у кого машина, а в нарботках. В алгоритмических наработках. То, что я имел в виду, говоря про позицию с 12 шашками и невозможности точно определить ничью — ничуть не затрагивало скорости перебора и т.п. Смысл был в следующем: с такой оценкой как у него определить ничью с математической точностью НЕВОЗМОЖНО. Повторюсь, что я имел в виду _математическую_ строгость доказательства.
Я хочу сказать, что программа может выдать на экран оценку 0 при глубине X — и это не будет ничьей, т.к. на глубине X+1 программа может изменить оценку в любую сторону. А смысл нашего преимущества заключается в том, что Тундра говорит с абсолютной точностью, что если ничья, то ее достигают либо белые, либо черные (здесь я немного упрощаю).26.06.2004 в 18:37 #345711plus600
УчастникSudya po dvum russkim programmam chto ya videl user interface (obcheniye s igrokom) namnogo otstaet ot perebora variantov
А, если не секрет, какие именно русские программы Вы видели?
С уважением,
Сергей Старцев27.06.2004 в 15:07 #345712alemo
УчастникК сожалению наш диспут уплыл куда-то в сторону, и заодно размножается и расползается на разные подтемы, как тараканы , в частности — обучающие программы, итп.
Вопрос который меня очень интересовал — признают ли программисты русских шашек важность дебютных библотек, и планируют ли всерьёз работать в этом направлении по улучшению — генераторы теории или какой-то другой метод ? Я по прежнему считаю, что на сегодняшний день, когда 8-фигурная ЭБ практически закончена и с «алгоритмическими наработками» всё в порядке (?) , создание новых и серьёзное улучшение существующих дебютных библиотек выходит на первый план.
А. Моисеев
27.06.2004 в 15:46 #345713plus600
УчастникВопрос который меня очень интересовал — признают ли программисты русских шашек важность дебютных библотек, и планируют ли всерьёз работать в этом направлении по улучшению — генераторы теории или какой-то другой метод ?
Я полностью согласен и работаю в этом направлении.
С уважением,
Сергей Старцев -
АвторСообщения
- Для ответа в этой теме необходимо авторизоваться.