Ответы в темах
-
Сообщения
-
Plus 600: » … наверное, не ясно выразился. Да, добились — и это не мои теоретические рассуждения, а факт — в чекерсе в среднем (именно в среднем!) коэффициент ветвления (число возможных ходов из позиции) меньше, чем в русских шашках «
Похоже, я пропустил что-то очень существенное. Где, когда и кем доказан этот факт ? Простые «житейские» соображения этого не подтверждают. Если мы поставим на доске любую позицию без дамок, то возможны два варианта:
1. В безударных позициях и позициях с боем только вперёд (до дамок) число разветвлений (легальных ходов) будет одинаково и в чекерс и в русские шашки.
2. В позициях с боем назад в русских шашках бой и будет легальным ходом, ну а в чекерс — ЛЮБОЙ другой ход (значительно больше одного) будет легальным !
Где ошибка в моих рассуждениях ? Если же вы хотите сюда добавить дамочные ходы, тогда — да!, конечно. С поля d4 дамка в русских шашках может сделать 13 легальных ходов (без боя), а в чекерс только 4. Если же учесть, что все статистики по БД, особенно эндшпильным, учтитавают дамки, то это очень сильно влияет и меняет СРЕДНЕЕ число разветвлений. Тут я спорить не буду.
============================================================
Sancoder : » … если программист в последнем письме (разговор о ничье из ЭБ) написал то, что он думает, и упрощений не делал, то здесь он отстает от нас (по крайней мере от Тундры), причем сильно»
Не уверен. Они (чекерсные программисты, включая Эда) через это прошли несколько лет назад. Они тогда тоже очень усиленно работали над алгоритмами и улучшали их. Пытались найти лучший ход уже в БД (не все ничьи равны!) ну и так далее … Но в конце концов все (ВСЕ!) чекерсные программисты пришли к выводу, что путь этот если и не тупиковый, то бесперктивный, и усиление баз данных достигает нужного результата значительно быстрее и эффективнее.
Даже если я и соглашусь с Вами, что ваш подход (алгоритмический ?) заслуживает внимания, то и в этом случае всё равно — существует какой то необходимый минимум размера БД, без которого серьёзного прогресса быть не может. Может быть 100,000 — 200,000 позиций …
Если Вы стремитесь заставить программу играть, как человек, то она никогда и не будет играть лучше человека !
Это похоже на рассуждения некоторых игроков, которые я часто слышу — «мне теория не нужна. У меня и так есть расчёт и интуиция!»
А. Моисеев
Михаил, насморка нет, просто обычно перед тем, как послать сообщение, я его проверяю и исправляю, а в этот раз поспешил. Как вы могли сообразить — буквы «л» и «д» у меня на клавиатуре рядом.
Программисты русских шашек и сами поограммы для меня сегодня отнюдь не на одно лицо. После почти 2-х летнего тусования на этой сайт, я уже отличаю Вас и Сергея, и Тундру от PLUS 600
А кстати, не могли бы вы мне сказать, почему к сгенерированным БД у Вас, да и у Сергея кажется тоже, такое особое отношение ? Чем они, кроме способа построения, отличаются от «ручных» баз данных ? Все чекерсные программы начинали в своё время с ручного ввода. Вот Сергей пишит, что у него 23,б00 позиций, введённых вручную. Это отлично и является великолепной стартовой площадкой для следующего качественного скачка — прогон программы по этой базе, её улучшение и развитие, как по вертикали (увеличение длины вариантов), так и по горизонтали — увеличение числа ветвей и возможных продолжений.
Сейчас я ожидаю ответа от Эда с пирамидами. Он очень большой любитель чисел и статистики, и думаю ответ скоро будет.
Поймите, моё желание не подколоть программистов русских шашек, поймать на чём-то, или доказать (упрекнуть) в отставании от чекерсных программистов. Я просто хочу поделиться с вами опытом и то, что я знаю о чекерсных программах, и надеюсь эта информация вам поможет.
Совершенно очевидно, что поскольку у вас, как впрочем и у Мартина с другим Эдом, нет доступа к такой машине, которая есть у Эда Трайса, то дебютная библиотека вам необходима. Могу только предсказать, что та программа в русские шашки, которая первая сделает прорыв в этом направлении — захватит неоспоримое первенство, пока остальные её не догонят, качественно улучшив дебютные библиотеки.
А. Моисеев
Михаил, Вы меня чуть-чуть опередили ! Я как раз пол часа назад послал Эду ещё один вопрос насчёт парочки пирамид в чекерс: одна пирамида эндшпильная, по числу позиций, а вторая пирамида — по числу ходов (легальных). Я имею в виду 7-49-… ну и так далее. Вот тогда и проверим медицинский факт и получим подтверждение (или …). К сожалению я не уверен на 100%, что у Эда есть данные по второй пирамиде.
Вы говорите о коэффициенте ветвления … А мы что, уже добились ясности с «количеством ветвей» ?
Кроме того надо бы ещё подумать и о «качестве» легальных ходов. Поясню на простом примере. После начальных ходов cd4 de5 у бедых 7 возможных ответов и все они дегадьны и в чекерс и в русские шашки, но в русские шашки такие ходы как ab4 или dc5 должны быть отброшены, а в чекекрс все 7 ходов возможны, не проигравают и ведут к 7 разным дебютам. Продолжать ?
Возможность бить назад и удары «одну отдать — две взять», как в примере с dc5, количество ветвей уменьшают.
А. Моисеев
Эд Трайс является, с моей точки зрения очень оригинальной и неординарной личностью с громадным интеллектом. В частности, у него очень острый язык и он никогда не лезет за словом в карман в споре и не очень беспокоится о «политической корректности» его аргументов. Я послал ему ещй один вопрос насчёт 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.==============================================================
Саша, ты забыл «мозаичные позиции», которых нет в русских шашках. В этом смысле отсутствие боя назад расширяет число позиций, да и легальных ходов, а не сужает. Да и с дамками всё не совсем понятно. В русских шашках дальнобойность дамки количество ходов отнюдь не увеличивает, так как «бить обязательно» и массу чекерсных позиций здесь выпадает. В чекерс есть целый класс миттельшпильных позиций, с 1-2-3 дамками и массой простых с каждой стороны.
С числом позиций проще … Если взять горсть белых и чёрных шашек и высыпать их на доску — то такая позиция будет легальной и возможной и в чекерс и в русские шашки, просто в силу самих правил.
А. Моисеев
На основании вопросов, которые здесь появились, я послал имэйл Эду Трайсу (автору WCC), и ниже привожу целиком его ответ на английском без всяких купюр с моей стороны. Судите сами …
==========================================================
In a message dated 6/25/04 9:34:09 AM, omela@juno.com writes:
<< 1) I said on Russian site that WCC searches 4,000,000 (four million)
positions per second.
Can you prove this and/or add any comments on this number ? Martin
Fiertz and Ed Gilbert
stated, that this number is meaningless, because having a large
opening and ending databases
is lowering this speed. >>Alex,
You have to understand, this 4 million positions per second is on a large
system with 128 GB of RAM and most of the 10-piece database loaded into a RAM
buffer and a full 2 GB for hash tables.If I disable the endgame databases, that is, turn them all off, the speed is
about 5.8 million positions per second. I can load the entire 8-piece and
9-piece databases into RAM, and the speed will remain about the same since I can
fit them all into RAM easily. That is, 5.8 million positions per second is what
I observe with the 8- and 9-piece databases activated without the 10-piece
turned on.The databases only slow down the progam when you do not have enough RAM to
load them all.<< 2) I said that WCC opening book includes about 120,000 positions. I
remember one time
you referred to this number. Can you prove this ? >>WCC Nuclear does not have an opening book. I found no position that it could
not play properly with a 30-second search using the higher speed machine and
the 10-piece databases. It can play the Doctor line where it throws away a
checker to preserve the draw after only 17 seconds. It announce a database draw
for the Black Widow in some of the tougher variations if I let it search for
about 1 minute.The last version of WCC that was sold had an opening book that I worked on,
and it had 156,000 positions.<< 3) Programmers in Russian checkers were impressed by WCC speed and asked
me details about configuration of you machine (s). >>Again, the speed I mentioned was not on a personal computer, but a very
expensive workstation running Unix Tru64 OS. The license for the operating system
was probably more than what some people pay for their computers! (slight
exaggeration to make a point: these are expensive systems down at the University).<< The rumors says - that the Russian checkers has more depth, or, in other
words — number of searched positions is higher, than in checkers. >>One term that programmers used to measure the complexity of a particular
game is the «branching factor». The means, on average, in an average position
from a game, how many legal moves are there?If there are more legal moves in Russian Checkers than regular checkers,
than it is true that Russian Checkers would be a harder game.Take the board game called Go. It is played on a 19×19 grid, and on each turn
you place one «stone». How many choices for the first player’s first move? 19
x 19 = 361. The second player’s first move? 360. The first player’s second
move? 359, etc.So how hard is this game? 361 x 360 x 359 x 358 x 357 … x 1 which is
basically 361 factorial, which is much bigger than the number of atomic particles in
the universe!Go is the hardest game there is out there.
—Ed
===========================================================Насчёт «сложности» игр … Эд увязывает это с чмслом возможных легальных ходов. Если мы согласимся с его критерием, то должны признать — что игры пл сложности равны, поскольку количество ходов и общее число позиций одинаково.
А. Моисеев
Сегодня поговорил ещй с одним программистом — автором программы WCC (World Checkers Champion). Он сказал, что быстродействие его программы — 4 миллиона позиций в секунду, но у него очень мощная машина (если вас интересуют подробности насчёт конфигурации — дайте знать, могу уточнить). Это очень оригинальный программист и человек. Он сказал например, что ему чихать на библиотеку дебютов, так как программа, имея 10-фигурную эндшпильную базу данных и мощнейшую машину — может всё решить сама, без всякой дебютной библиотеки !
Он в частности утверждает, что в позициях с 18 шашками программа за 30 секунд видит всё до конца (!), то есть до эндшпильной базы данных. Его библитотека дебютов небольшая и включает всего 120.000 позиций (у других программ это число больше миллиона).
А. Моисеев
Извините, забыл упомянуть, что умывальник в любой дешёвой гостинице в Америке вседа есть, но чаще всего отдельно от туалета — в коридоре с небольшим столиком для бритья и умывания, и мылом (отдельно от мыла в душе). В номерах для курящих всегда есть пепельница.
А. Моисеев
В Америке любая дешёвая гостиница включает в себя двухместную кровать, стол, кресло, туалет, душ, шкафчик, тумбочку и почти всегда телевизор. Само собой бесплатно в любом номере в любой гостинице всегда есть Библия и телефонный справочник. Часто за эту же цену в дешёвой гостинице ($25-$35) предлагают и лёгкий бесплатный завтрак — булочки, кофе, сок, молоко, чипсы. Ну и само собой — постель меняют каждый день. А в душе всегда мыло и шампунь. Это так сказать стандартный, минимальный набор услуг, предлагаемый каждым захудалым мотелем.
А что такое — «плохая гостиница в Питере» ?
А. Моисеев
Нет, так не пойдёт, ведь соревнования и звания всё-таки по шашкам. Так что Пете Иванову, чтобы получть это почётное звание, также, как и всем другим гроссмейстерам в своё время (например — Алканд … или Щёголев … или Шварцман … ) — надо стать чемпионом страны по шашкам в своей возрастной категории и набрать хотя бы 2,5 очка из 9 — а то какой же из него гроссмейстер.
В тоже самое время в вашей идее есть рациональное зерно. Вес может рассматриваться как отдельная категория людей, играющих в шашки. То есть надо провести чемпионат страны по шашкам между толстыми (или тонкими), и их ранжировать — присваивать титулы и звания по итогам турниров.
Ну скажем — международный гроссмейстер по шашкам в весовой категории до 100 килограмм (это моя категория).
АЛЕМО
Кто такой Мистер .ru ?
1. Возраст — 35-37 лет, может быть около 40.
2. Проживает скорее всего в Питере.
3. Мастер спорта в стоклетки.
4. Семейное положение — женат, но не очень удачно, или разведён.
5. Образование — высшее.
6. Национальность — скорее всего русский
7. Членом Коммунистической партии не был.
8. Мог присутствовать в Адлере (тогда поиск сужается), но не обязательно.
9. Выпивал в молодости и не до конца завязал на сегодняшний день, хотя пьёт меньше.
Надеюсь моя информация облегчит ваши поиски.
А. Моисеев
Согласен с AS — на сплав не похоже и не верится. Николай молодец и сыграл истинно по американски — слабо, но честно !
А. Моисеев[addsig]
Насчёт турниров … Согласен с доводом Алканда, что чекерс — для избранных, не всем дано
, так что идея многоборья не проходит. Тем не менее, всё-таки, чтобы «жизнь малиной не казалась», предлагаю следующее : из планирующихся 25 турниров, сделать 2 в чекерс, 2 в поддавки, 1 в итальянские, а остальные 20 разделить пополам (по 10) между русскими и стоклетками. Можно конечно это разбавить и парочкой турнров по бразильским шашкам, если есть энтузиасты.Общий зачёт можно сделать как в Олимпиадах: 3 очка за 1-е место, 2 — за второе и 1 — за третье в любом турнире, по итогам лучших 10-12-15 турниров (эта цифра требует уточнения).
А. Моисеев[addsig]
Мне тут ещё один любопытный аргумент пришёл в голову. Вот Америку здесь обвиняли в том, что она сделала что-то не так, а потом извинялась. Во первых это как-то не соответствует тому «комплексу полноценности», о котором здесь говорили ранее. А во вторых, вот Россия хоть раз в истории всерьёз за что нибудь, когда-нибудь, перед кем нибудь извинялась ? Или не в чем ? Хотя бы перед Литвой … или перед своим народом. Коммунизм так и не был осуждён и наказан в России, а значит покаяние ещё впереди.
А. Моисеев[addsig]
