- В этой теме 69 ответов, 12 участников, последнее обновление 10 лет, 11 месяцев назад сделано
.
-
Сообщения
-
Насчёт «сложности» игр … Эд увязывает это с чмслом возможных легальных ходов. Если мы согласимся с его критерием, то должны признать — что игры по сложности равны, поскольку количество ходов и общее число позиций одинаково.
Все по тексту понял, кроме… этого вывода 😆
Эд ведь не напрасно написал про легальные ходы. То есть, если допустить, что в чекерсе будет легальным взятие назад и дамка будет «длинной», то тогда количество возможных ходов в этих двух играх совпадет. 
Но, постойте! Постойте! Это ж будут уже … русские шашки 😯
А если серьезно, то Эд подтвердил мое предположение, высказанное где-то в этом топике, что наличие бОльшего числа вариантов и ветвлений (за счет размена назад) приводит к усложнению оценки, счета и выбора вариантов. То есть к усложнению самой игры.Саша, ты забыл «мозаичные позиции», которых нет в русских шашках. В этом смысле отсутствие боя назад расширяет число позиций, да и легальных ходов, а не сужает. Да и с дамками всё не совсем понятно. В русских шашках дальнобойность дамки количество ходов отнюдь не увеличивает, так как «бить обязательно» и массу чекерсных позиций здесь выпадает. В чекерс есть целый класс миттельшпильных позиций, с 1-2-3 дамками и массой простых с каждой стороны.
С числом позиций проще … Если взять горсть белых и чёрных шашек и высыпать их на доску — то такая позиция будет легальной и возможной и в чекерс и в русские шашки, просто в силу самих правил.
А. Моисеев
Эд Трайс является, с моей точки зрения очень оригинальной и неординарной личностью с громадным интеллектом. В частности, у него очень острый язык и он никогда не лезет за словом в карман в споре и не очень беспокоится о «политической корректности» его аргументов. Я послал ему ещй один вопрос насчёт 18 шашек и 30 секунд, о которых я упоминал и ответ пришёл почти немедленно (по-видимому вопрос и тема показались ему любопытными и интереными). Отве его настолько интересный, что я опять решил «вывалить» его здесь целиком.
======================================================================
In a message dated 6/25/04 9:43:27 AM, omela@juno.com writes:
<< Based on our phone converstion from yesterday, i said on Russian site, that in position with 18 pieces, WCC can see during 30 seconds to the end - when it hits into ending database. Can you also prove this number and add your comments here ? >>
I have gone through most of the 3-move deck to observe how WCC Nuclear would play the game. I have many personal notes that I had written down over a 3 month period. I took down the notes because, in December, if I do not have funding to continue using the systems down at the university, the hard drives will be erased. I applied for funding from sources such as the National Science Foundation, but I may not be eligible until next March, at which time it will be too late. I am working on a temporary solution, but now, back to your question.
From my notes I see that, ON AVERAGE, when the material enters into 9×9 with all checkers present, WCC Nuclear announces a DATABASE DRAW within 30 seconds. Sometimes it is much sooner (like in the Single Corner it can announce a draw with 22 pieces on the board after 27 seconds fo search.)
A DATABASE DRAW is a special condition. You see, when WCC hits its database and the position is a draw, I return the value 0 for the position in its database. When I call the evaluation function for a non-database position, say when there are 12 pieces on the board, if the evaluation comes back «0» by chance, I change it to +2. That means the score of «0» can only come from the databases.
When a score of «0» from the distant future is passed down the tree to the
root move, there is only one reason for this. Every leaf node in the game tree, with all of the branches and millions of paths to the leaves, must have a database score attached to it. This means every path from the initial position has been searched to a depth sufficient to return a valid database score.Consider a simple example.
Let’s say you have an 8-piece database, but you have 5 checkers against 5 checkers on the board. It is possible for an 8-piece database to announce a draw? Sure, it has to search and evaluate every possible 1×1 trade. As long as there is one path that can be chosen to avoid a 4×4 position, the program CANNOT announce a database draw. But, if all of them lead to 4×4 results, the result can be announced.
Even with 18 pieces on the board, 9×9, it is almost impossible to avoid EVERY 5×5 position that can be reached (there are 8.5 trillion of them) after as little as 30 seconds of search, which would be about 120 million positions. The program only has to find 4 swaps, then it is in the database.
The only way to avoid the 5×5 would be to get yourself in deep trouble, like deliberately losing a piece to keep it as a 6×5. The program assumes you would not want to be down 300 points (a full checker) if you can find safe haven in the database (0).
For this reason, the program is capable of announcing draws from a great
distance.==============================================================
Есть простой «медицинский» факт — в среднем число возможных легальных ходов (или употребляя более корректный термин — коэффициент ветвления) в чекерсе меньше, чем в русских шашках. Факт потому, что я могу сравнивать эти значения для одного и того же своего движка в разных играх.
Конечно, есть конкретные позиции, где число возможных ходов по правилм чекерса будет больше, но обратных позиций ГОРАЗДО больше.Сергей, а какое количество позиций (не ходов!) именно в дебютной библиотеке PLUS 600. Под ДБ я в данном случае имею ввиду теоретические позиции, введенные человеком.
Так как библиотеки дебютов и миттельшпилей, сгенерированные программой, уже несколько другое.
С уважением,
МиГ.Да, разумеется, сгенерированные это совсем другое — но именно так в чекерсе и получают БД по миллиону ходов.
Руками у меня введено 23 758 позиций. Не очень понимаю суть примечания в скобках — у меня каждая позиция содержит один ход.С уважением,
Сергей СтарцевМихаил, Вы меня чуть-чуть опередили ! Я как раз пол часа назад послал Эду ещё один вопрос насчёт парочки пирамид в чекерс: одна пирамида эндшпильная, по числу позиций, а вторая пирамида — по числу ходов (легальных). Я имею в виду 7-49-… ну и так далее. Вот тогда и проверим медицинский факт и получим подтверждение (или …). К сожалению я не уверен на 100%, что у Эда есть данные по второй пирамиде.
Вы говорите о коэффициенте ветвления … А мы что, уже добились ясности с «количеством ветвей» ?
Кроме того надо бы ещё подумать и о «качестве» легальных ходов. Поясню на простом примере. После начальных ходов cd4 de5 у бедых 7 возможных ответов и все они дегадьны и в чекерс и в русские шашки, но в русские шашки такие ходы как ab4 или dc5 должны быть отброшены, а в чекекрс все 7 ходов возможны, не проигравают и ведут к 7 разным дебютам. Продолжать ?
Возможность бить назад и удары «одну отдать — две взять», как в примере с dc5, количество ветвей уменьшают.
А. Моисеев
Алекс, Вы спутали меня (Михаила Глизерина, разработчика программы TORNADO) с Сергеем Старцевым (разработчик PLUS 600)
Или Вы представляете для себя всех российских разработчиков в виде этакой «коллективной физиономии» ((с) Василий Уткин) ?у бедых 7 … ответов и все они дегадьны…
Алекс, у Вас насморк?
(Извините за шутку)С уважением,
МиГ.у меня каждая позиция содержит один ход
Сергей, а сейчас я не совсем Вас понял. Разве не существует дебютных позиций с несколькими возможными ходами?
:С уважением,
МиГ.Михаил, насморка нет, просто обычно перед тем, как послать сообщение, я его проверяю и исправляю, а в этот раз поспешил. Как вы могли сообразить — буквы «л» и «д» у меня на клавиатуре рядом.
Программисты русских шашек и сами поограммы для меня сегодня отнюдь не на одно лицо. После почти 2-х летнего тусования на этой сайт, я уже отличаю Вас и Сергея, и Тундру от PLUS 600
А кстати, не могли бы вы мне сказать, почему к сгенерированным БД у Вас, да и у Сергея кажется тоже, такое особое отношение ? Чем они, кроме способа построения, отличаются от «ручных» баз данных ? Все чекерсные программы начинали в своё время с ручного ввода. Вот Сергей пишит, что у него 23,б00 позиций, введённых вручную. Это отлично и является великолепной стартовой площадкой для следующего качественного скачка — прогон программы по этой базе, её улучшение и развитие, как по вертикали (увеличение длины вариантов), так и по горизонтали — увеличение числа ветвей и возможных продолжений.
Сейчас я ожидаю ответа от Эда с пирамидами. Он очень большой любитель чисел и статистики, и думаю ответ скоро будет.
Поймите, моё желание не подколоть программистов русских шашек, поймать на чём-то, или доказать (упрекнуть) в отставании от чекерсных программистов. Я просто хочу поделиться с вами опытом и то, что я знаю о чекерсных программах, и надеюсь эта информация вам поможет.
Совершенно очевидно, что поскольку у вас, как впрочем и у Мартина с другим Эдом, нет доступа к такой машине, которая есть у Эда Трайса, то дебютная библиотека вам необходима. Могу только предсказать, что та программа в русские шашки, которая первая сделает прорыв в этом направлении — захватит неоспоримое первенство, пока остальные её не догонят, качественно улучшив дебютные библиотеки.
А. Моисеев
Вы говорите о коэффициенте ветвления … А мы что, уже добились ясности с «количеством ветвей» ?
Я, наверное, не ясно выразился. Да, добились — и это не мои теоретические рассуждения, а факт — в чекерсе в среднем (именно в среднем!) коэффициент ветвления (число возможных ходов из позиции) меньше, чем в русских шашках.
Александр, я вам вот что скажу:
если программист в последнем письме (разговор о ничье из ЭБ) написал то, что он думает, и упрощений не делал, то здесь он отстает от нас (по крайней мере от Тундры), причем сильно.
Во-первых он ошибается, когда говорит что-то о 300 очках и что никто не пойдет на позицию 5 на 6. Неужели ударов в чекерсе не существует?
А во-вторых, понятие «ничья из ЭБ» имеет ограниченный (слишком) смысл без вот такого понятия «кто ее достигает».К примеру, в Тундре есть поиск выигрыша и ничьи. И если при поиске ничьи программа находит ничью она говорит, что из этой позиции можно достичь ничьи; а если при поиске выигрыша программа говорит ничья, то это значит «выигрыш не достижим».
Чем они, кроме способа построения, отличаются от «ручных» баз данных ?
Алекс, но это же очевидно… ДБ, введенная вручную, содержит и обобщает то, что было найдено человеком (без помощи или с помощью программ(ы)). В ДБ, сделанной программой, обобщается опыт этой самой программы
Кстати, и первое, и второе может быть не свободно от ошибок.Во-первых он ошибается, когда говорит что-то о 300 очках и что никто не пойдет на позицию 5 на 6. Неужели ударов в чекерсе не существует?
А во-вторых, понятие «ничья из ЭБ» имеет ограниченный (слишком) смысл без вот такого понятия «кто ее достигает».Мне кажется, что Эд Трайс все прекрасно знает
Просто, он написал несколько упрощенно. Так как далее уже детали, понятные далеко не всем (а скорее, почти никому ).Например, ещё нужно учитывать такой фактор, как «цена ничьей». А Эд, наверное, имел ввиду то, что никто не будет ухудшать позицию, если есть ничья по базе. Вот и все.
С уважением,
МиГ.Plus 600: » … наверное, не ясно выразился. Да, добились — и это не мои теоретические рассуждения, а факт — в чекерсе в среднем (именно в среднем!) коэффициент ветвления (число возможных ходов из позиции) меньше, чем в русских шашках «
Похоже, я пропустил что-то очень существенное. Где, когда и кем доказан этот факт ? Простые «житейские» соображения этого не подтверждают. Если мы поставим на доске любую позицию без дамок, то возможны два варианта:
1. В безударных позициях и позициях с боем только вперёд (до дамок) число разветвлений (легальных ходов) будет одинаково и в чекерс и в русские шашки.
2. В позициях с боем назад в русских шашках бой и будет легальным ходом, ну а в чекерс — ЛЮБОЙ другой ход (значительно больше одного) будет легальным !
Где ошибка в моих рассуждениях ? Если же вы хотите сюда добавить дамочные ходы, тогда — да!, конечно. С поля d4 дамка в русских шашках может сделать 13 легальных ходов (без боя), а в чекерс только 4. Если же учесть, что все статистики по БД, особенно эндшпильным, учтитавают дамки, то это очень сильно влияет и меняет СРЕДНЕЕ число разветвлений. Тут я спорить не буду.
============================================================
Sancoder : » … если программист в последнем письме (разговор о ничье из ЭБ) написал то, что он думает, и упрощений не делал, то здесь он отстает от нас (по крайней мере от Тундры), причем сильно»
Не уверен. Они (чекерсные программисты, включая Эда) через это прошли несколько лет назад. Они тогда тоже очень усиленно работали над алгоритмами и улучшали их. Пытались найти лучший ход уже в БД (не все ничьи равны!) ну и так далее … Но в конце концов все (ВСЕ!) чекерсные программисты пришли к выводу, что путь этот если и не тупиковый, то бесперктивный, и усиление баз данных достигает нужного результата значительно быстрее и эффективнее.
Даже если я и соглашусь с Вами, что ваш подход (алгоритмический ?) заслуживает внимания, то и в этом случае всё равно — существует какой то необходимый минимум размера БД, без которого серьёзного прогресса быть не может. Может быть 100,000 — 200,000 позиций …
Если Вы стремитесь заставить программу играть, как человек, то она никогда и не будет играть лучше человека !
Это похоже на рассуждения некоторых игроков, которые я часто слышу — «мне теория не нужна. У меня и так есть расчёт и интуиция!»
А. Моисеев
» Алекс, но это же очевидно… ДБ, введенная вручную, содержит и обобщает то, что было найдено человеком (без помощи или с помощью программ(ы)). В ДБ, сделанной программой, обобщается опыт этой самой программы Кстати, и первое, и второе может быть не свободно от ошибок … «
Михаил, мне кажется вы упрощённо понимаете идею генерации. Из ваших слов следует, что мы ставим начальную позицию 12х12 и программа «с чистого листа» начинает думать и генерировать свою теорию. Это не так ! Исходная теоретическая база данных всё равно опирается на человеческий опыт. Никто этого не отрицает и не миновал, и чекерсные программисты тоже. Вот Старцев пишет, что его дебютная библиотека вкючает 23,700 позиций. Отлично. Вот эта база и должна стать исходной для генерации, или скажем так — первого итерационного этапа генерации. Пусть программа «пройдёт» по всем позициям и проверит их все — нет ли где лучше или равноцноого хода, предлагаемого БД. Или простого ещё одного не проигрывающего хода. А впрочем можно и проигрывающего — ведь иногда надо знать и как выиграть. Допустим к каждой позиции в БД программа добавила всего один дополнительный ход (расширение по горизонтали). Вот вам и 47,500 позиций в БД ! Первая итерация. Ну и так далее.
А потом возьмите и продолжите «концы вариантов» на один ход (расширение по вертикали). В этом случае кстати возможна обратная коррекция всего дерева, если обнаружится, что какие-то варианты «с дыркой». И эта БД из 47,500 позиций уже не будет чисто человеческой.
А что делает человек, когда анализирует и готовит новинки ? То же самое ! Берёт позицию, анализирует и улучшает/добавляет новые ходы. Только в вашем случае (с программой) этот процесс будет на качественно ином уровне.
Всё это возможно только в одном случае — если вы доверяете своему алгоритму и готовы «отколоться» от человеческой теории. Это будет первый шажок.
А. Моисеев
- Для ответа в этой теме необходимо авторизоваться.