Google
 

Сайт Андрея Иванова

Андрей Иванов - все секреты шашек и шашистов

Login





 


 Забыли пароль?
 или новый пользователь? Зарегистрируйся!

Кто с нами

Пользователей:  На сайте
Пользователей:  Пользователей: 0
Гостей:  Гостей: 454
Всего:  Всего: 454
Пользователей:  Зарегистрированные
No members connected


Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
Автор Сообщение
alemo
6 Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 07:16 PM



Зарегистрирован: Апр 04, 2003
Сообщений: 6926

Михаил, насморка нет, просто обычно перед тем, как послать сообщение, я его проверяю и исправляю, а в этот раз поспешил. Как вы могли сообразить - буквы "л" и "д" у меня на клавиатуре рядом.

Программисты русских шашек и сами поограммы для меня сегодня отнюдь не на одно лицо. После почти 2-х летнего тусования на этой сайт, я уже отличаю Вас и Сергея, и Тундру от PLUS 600 Very Happy

А кстати, не могли бы вы мне сказать, почему к сгенерированным БД у Вас, да и у Сергея кажется тоже, такое особое отношение ? Чем они, кроме способа построения, отличаются от "ручных" баз данных ? Все чекерсные программы начинали в своё время с ручного ввода. Вот Сергей пишит, что у него 23,б00 позиций, введённых вручную. Это отлично и является великолепной стартовой площадкой для следующего качественного скачка - прогон программы по этой базе, её улучшение и развитие, как по вертикали (увеличение длины вариантов), так и по горизонтали - увеличение числа ветвей и возможных продолжений.

Сейчас я ожидаю ответа от Эда с пирамидами. Он очень большой любитель чисел и статистики, и думаю ответ скоро будет.

Поймите, моё желание не подколоть программистов русских шашек, поймать на чём-то, или доказать (упрекнуть) в отставании от чекерсных программистов. Я просто хочу поделиться с вами опытом и то, что я знаю о чекерсных программах, и надеюсь эта информация вам поможет.

Совершенно очевидно, что поскольку у вас, как впрочем и у Мартина с другим Эдом, нет доступа к такой машине, которая есть у Эда Трайса, то дебютная библиотека вам необходима. Могу только предсказать, что та программа в русские шашки, которая первая сделает прорыв в этом направлении - захватит неоспоримое первенство, пока остальные её не догонят, качественно улучшив дебютные библиотеки.

А. Моисеев
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
MiG
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 06:43 PM



Зарегистрирован: Сен 12, 2002
Сообщений: 391

Цитата:
у меня каждая позиция содержит один ход


Сергей, а сейчас я не совсем Вас понял. Разве не существует дебютных позиций с несколькими возможными ходами? Question

С уважением,
МиГ.
 
 Профиль пользователя отправить личное сообщение Послать e-mail  
Ответить с цитатой Наверх
MiG
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 06:30 PM



Зарегистрирован: Сен 12, 2002
Сообщений: 391

Алекс, Вы спутали меня (Михаила Глизерина, разработчика программы TORNADO) с Сергеем Старцевым (разработчик PLUS 600) Smile Или Вы представляете для себя всех российских разработчиков в виде этакой "коллективной физиономии" ((с) Василий Уткин) Smile ?

Цитата:
у бедых 7 ... ответов и все они дегадьны...


Алекс, у Вас насморк? Smile (Извините за шутку)

С уважением,
МиГ.
 
 Профиль пользователя отправить личное сообщение Послать e-mail  
Ответить с цитатой Наверх
alemo
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 06:12 PM



Зарегистрирован: Апр 04, 2003
Сообщений: 6926

Михаил, Вы меня чуть-чуть опередили ! Я как раз пол часа назад послал Эду ещё один вопрос насчёт парочки пирамид в чекерс: одна пирамида эндшпильная, по числу позиций, а вторая пирамида - по числу ходов (легальных). Я имею в виду 7-49-... ну и так далее. Вот тогда и проверим медицинский факт и получим подтверждение (или ...). К сожалению я не уверен на 100%, что у Эда есть данные по второй пирамиде.

Вы говорите о коэффициенте ветвления ... А мы что, уже добились ясности с "количеством ветвей" ?

Кроме того надо бы ещё подумать и о "качестве" легальных ходов. Поясню на простом примере. После начальных ходов cd4 de5 у бедых 7 возможных ответов и все они дегадьны и в чекерс и в русские шашки, но в русские шашки такие ходы как ab4 или dc5 должны быть отброшены, а в чекекрс все 7 ходов возможны, не проигравают и ведут к 7 разным дебютам. Продолжать ?

Возможность бить назад и удары "одну отдать - две взять", как в примере с dc5, количество ветвей уменьшают.

А. Моисеев
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 05:55 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1323
Откуда : Москва
MiG писал(а):
Сергей, а какое количество позиций (не ходов!) именно в дебютной библиотеке PLUS 600. Под ДБ я в данном случае имею ввиду теоретические позиции, введенные человеком.

Так как библиотеки дебютов и миттельшпилей, сгенерированные программой, уже несколько другое.

С уважением,
МиГ.

Да, разумеется, сгенерированные это совсем другое - но именно так в чекерсе и получают БД по миллиону ходов.
Руками у меня введено 23 758 позиций. Не очень понимаю суть примечания в скобках - у меня каждая позиция содержит один ход.

С уважением,
Сергей Старцев
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 05:49 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1323
Откуда : Москва
Есть простой "медицинский" факт - в среднем число возможных легальных ходов (или употребляя более корректный термин - коэффициент ветвления) в чекерсе меньше, чем в русских шашках. Факт потому, что я могу сравнивать эти значения для одного и того же своего движка в разных играх.
Конечно, есть конкретные позиции, где число возможных ходов по правилм чекерса будет больше, но обратных позиций ГОРАЗДО больше.
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
alemo
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 03:50 PM



Зарегистрирован: Апр 04, 2003
Сообщений: 6926

Эд Трайс является, с моей точки зрения очень оригинальной и неординарной личностью с громадным интеллектом. В частности, у него очень острый язык и он никогда не лезет за словом в карман в споре и не очень беспокоится о "политической корректности" его аргументов. Я послал ему ещй один вопрос насчёт 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 9x9 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 1x1 trade. As long as there is one path that can be chosen to avoid a 4x4 position, the program CANNOT announce a database draw. But, if all of them lead to 4x4 results, the result can be announced.

Even with 18 pieces on the board, 9x9, it is almost impossible to avoid EVERY 5x5 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 5x5 would be to get yourself in deep trouble, like deliberately losing a piece to keep it as a 6x5. 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.

==============================================================
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Alkand
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 03:30 PM



Зарегистрирован: Июль 16, 2002
Сообщений: 3635
Откуда : Москва
Да, я действительно забыл про "мозаичные позиции".
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
alemo
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 03:22 PM



Зарегистрирован: Апр 04, 2003
Сообщений: 6926

Саша, ты забыл "мозаичные позиции", которых нет в русских шашках. В этом смысле отсутствие боя назад расширяет число позиций, да и легальных ходов, а не сужает. Да и с дамками всё не совсем понятно. В русских шашках дальнобойность дамки количество ходов отнюдь не увеличивает, так как "бить обязательно" и массу чекерсных позиций здесь выпадает. В чекерс есть целый класс миттельшпильных позиций, с 1-2-3 дамками и массой простых с каждой стороны.

С числом позиций проще ... Если взять горсть белых и чёрных шашек и высыпать их на доску - то такая позиция будет легальной и возможной и в чекерс и в русские шашки, просто в силу самих правил.

А. Моисеев
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Alkand
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 02:39 PM



Зарегистрирован: Июль 16, 2002
Сообщений: 3635
Откуда : Москва
alemo писал(а):
Насчёт "сложности" игр ... Эд увязывает это с чмслом возможных легальных ходов. Если мы согласимся с его критерием, то должны признать - что игры по сложности равны, поскольку количество ходов и общее число позиций одинаково.

Все по тексту понял, кроме... этого вывода Laughing Razz Эд ведь не напрасно написал про легальные ходы. То есть, если допустить, что в чекерсе будет легальным взятие назад и дамка будет "длинной", то тогда количество возможных ходов в этих двух играх совпадет. Very Happy Но, постойте! Постойте! Это ж будут уже ... русские шашки Shocked
А если серьезно, то Эд подтвердил мое предположение, высказанное где-то в этом топике, что наличие бОльшего числа вариантов и ветвлений (за счет размена назад) приводит к усложнению оценки, счета и выбора вариантов. То есть к усложнению самой игры.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
MiG
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 02:37 PM



Зарегистрирован: Сен 12, 2002
Сообщений: 391

2. Превышает, и в терминах чекерсных шашистов превышает намного.

Сергей, а какое количество позиций (не ходов!) именно в дебютной библиотеке PLUS 600. Под ДБ я в данном случае имею ввиду теоретические позиции, введенные человеком.

Так как библиотеки дебютов и миттельшпилей, сгенерированные программой, уже несколько другое.

С уважением,
МиГ.
 
 Профиль пользователя отправить личное сообщение Послать e-mail  
Ответить с цитатой Наверх
alemo
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 01:50 PM



Зарегистрирован: Апр 04, 2003
Сообщений: 6926

На основании вопросов, которые здесь появились, я послал имэйл Эду Трайсу (автору 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 19x19 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
===========================================================

Насчёт "сложности" игр ... Эд увязывает это с чмслом возможных легальных ходов. Если мы согласимся с его критерием, то должны признать - что игры пл сложности равны, поскольку количество ходов и общее число позиций одинаково.

А. Моисеев
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 11:16 AM



Зарегистрирован: Дек 24, 2002
Сообщений: 1323
Откуда : Москва
MiG писал(а):
Сейчас, если не ошибаюсь, самая большая ДБ у PLUS 600. Но и там вроде бы число позиций не превышает 20.000.

1. Именно так
2. Превышает, и в терминах чекерсных шашистов превышает намного.
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Alkand
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 10:42 AM



Зарегистрирован: Июль 16, 2002
Сообщений: 3635
Откуда : Москва
Цитата:
Его библитотека дебютов небольшая и включает всего 120.000 позиций (у других программ это число больше миллиона)

А можно чайнику от программирования подключиться? Embarassed
Для справки - прогнал базы, что были под рукой, на глубину 50 ходов (100 полуходов) -
русские - около 58.000, всего позиций 1.119.382
чекерс - около 18.000, всего позиций 505.822

А вот, о чем это может свидетельствовать, не знаю. Это ведь не библиотеки дебютов, а базы человеческих партий. Тут сказывается и наличие повторяемых вариантов, и средняя продолжительность партий.

Кстати, хорошо бы определиться, о каком количестве ходов (или шашек на доске) мы говорим, упоминая выражение - дебют. Question
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
sancoder
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 10:29 AM



Зарегистрирован: Дек 26, 2003
Сообщений: 115

Михаил: в гугле слово chinook Smile
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Показать:     
Перейти к:  
Время в формате GMT + 3
Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
PNphpBB2 © 2003-2007 
 
Page created in 0.792522907257 seconds.