Шашки в России

Шашечные программы - Программирование русских шашек и чекерса

Soccer - Июнь 16, 2004 - 12:32 PM
Тема сообщения: 2811
Программы (по крайней мере в чекерс) могут нормально играть и при 2-3 минутах на партию. На Yahoo 1 мин + 2-3сек на каждый ход прогерам вполне хватало, насколько я знаю.

Один раз в чекерс TOC был один прогер который спокойно всех сделал. (контроль где-то 2-3 мин.)



ЗЫ Я так понял что Gold Membership не обязателен?



с уважением,

Яков Лейкин[addsig]
alemo - Июнь 16, 2004 - 03:03 PM
Тема сообщения: 2813
Ошибка Алканда и небрежность, с которой он бросил : "не более 10 минут на партию" вполне понятна - программы по русским шашкам отстают в быстродействии и уступают в силе чекерсным программам лет на 5-6 (при интенсивной работе).



А. Моисеев[addsig]
Kavr - Июнь 16, 2004 - 11:05 PM
Тема сообщения: 2815
Quote:
Ошибка Алканда и небрежность, с которой он бросил : "не более 10 минут на партию" вполне понятна - программы по русским шашкам отстают в быстродействии и уступают в силе чекерсным программам лет на 5-6 (при интенсивной работе).



А. Моисеев





1.Чекерс в связи со спецификой правил, легче поддается компьютерному перебору и программированию соответственно. Алгоритм отвечающий за быстродействие перебора вариантов, используется и чекерсными и "русскими" программами один и тот же. Математики давненько не придумывали ничего нового в этом направлении. Разница в скорости (при ее наличии) обусловлена исключительно разницей в правилах игр. Что делать если чекерс более простая игра (во всяком случае для компьютера)? Сильнейшие программы, играющие в русские шашки на данный момент способны составить конкуренцию сильнейшим гроссмейстерам. Последние результаты это подтверждают, поэтому Ваше утверждение несколько некорректно и нуждалось по крайней мере в предварительной практической проверке. Вы попробовали, например, сыграть с одной из сильнейших программ? Может быть Вы приведете конкретные аргументы?



2.Кстати, в матче с коротким контролем у человека меньше шансов одолеть программу по сумме, но больше шансов выиграть одну-другую партию.



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



С уважением, Камынин Виталий.[addsig]
MiG - Июнь 17, 2004 - 02:48 AM
Тема сообщения: 2817
«...программы по русским шашкам отстают в быстродействии и уступают в силе чекерсным программам лет на 5-6 (при интенсивной работе)».



Уважаемый Александр, такое ммм... смелое заявление недурно бы ещё аргументировать, причем по трем пунктам отдельно:



1) «отстают в быстродействии»;

2) «уступают в силе»;

3) «лет на 5-6 (при интенсивной работе)».



Лично я полностью согласен с моим коллегой Виталием Камыниным.



Более того, я считаю, что если бы ведущие российские разработчики вдруг всерьез взялись за разработку программ, играющих в чекерс, то мы бы составили серьезную конкуренцию самым сильным западным чекерсным программам. Конечно, не в плане теории дебютов и миттельшпилей (здесь нужно время!), но в смысле игровых алгоритмов, эндшпильных баз и т. д.



С уважением,

Михаил Глизерин.[addsig]
Alkand - Июнь 17, 2004 - 08:17 AM
Тема сообщения: 2818
Quote:
Ошибка Алканда и небрежность, с которой он бросил : "не более 10 минут на партию" вполне понятна - программы по русским шашкам отстают в быстродействии и уступают в силе чекерсным программам лет на 5-6 (при интенсивной работе)



Сразу почувствовал себя убогим чайником, ничего не понимающим ни в шашках, ни в программах, ни в компьютерах ... Вот, что значит - жить в Америке! Сразу учишься все и вся видеть наскозь. И на лету ловить суть

Не знаю о какой ошибке речь. А прикинул, сколько мне нужно времени, чтобы консультироваться с программой, запущенной на другом компе. Нужно поставить позицию, нужно время самой программе, надо и оценить предлагаемый ход и прочесть, например, "best line", а не тупо транслировать ходы программы. Не забывайте о том, что почти наверняка нужно будет постоянно откатывать ходы в программе и продвигивать на ней партию, ведь "человеские" ходы соперников не будут совпадать с теми, что предлагает программа. Как это все успеть за 2-3 минуты, я не понимаю.

Иное дело, что программист видимо может написать интерфейс специально для игры в ВОГе и программа сама будет отправлять ходы на сервер ВОГа. Тогда этого не поймешь, да и экономия времени на отсутствии вмешательства человека будет.

А что касается сравнения сил программ в шашки, и высказываний на эту тему, то я отношусь к труду программистов (хороших продуктов) с уважением. А критерий "хорошести" - практика. Как можно отзываться о программах, которыми скорее всего даже и не пользовался [addsig]
alemo - Июнь 17, 2004 - 09:03 AM
Тема сообщения: 2820
Вот уж не ожидал, что моё невинное сообщение, а точнее сказать - просто констатация очевидных фактов, вызовет такой шквал возмущённых ответов. А заодно меня ещё и обвинили в том, чего я и не говорил. Например - о неуважении к трудам программистов. Но давайте по существу. Я в своём сообщении, говоря об отставании - имел в виду техническое отставание и тот факт, что программисты русских шашек начали позднее лет на 10. Заметьте на 10 (!), а сегодня они уже отстают только на 5-6 лет с моей точки зрения. И если будут продолжать работать, то и это отставание сократится. Ни о каком "умственном" отставании я кажется ничего не говорил.



Отвечаю по существу Михаилу Глизерину. Он пишет :



"Уважаемый Александр, такое ммм... смелое заявление недурно бы ещё аргументировать, причем по трем пунктам отдельно:



1) «отстают в быстродействии»;

2) «уступают в силе»;

3) «лет на 5-6 (при интенсивной работе)».



Лично я полностью согласен с моим коллегой Виталием Камыниным ..."



Отвечаю:



1) В чекерсных программах за 30 секунд при наличии мощнейшей оперативной памяти (2 ГБ и выше) программа просчитывает до 30 полуходов вперёд, при наличии "скромненькой" оперативной памяти, как на моём компе (512 КБ), программа за это же время "видит" на 20-22 полухода вперёд. У Вас быстрее ?



Только не говорите мне, что "мы люди умные, но бедные" и у нас нет таких мощностей. Нет так нет, значит работает медленне. Кстати и сам А. Кандауров, возможно не желая того, подтвердил насчёт быстродействия - что программе по русским шашкам на сегодняшний день надо не меньше 10 минут, чтобы сыграть (и использовать в нечестной игре) полноценную партию. Для чекерсных программ это число - 2.5-3 минуты



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



3) Михаил, я уже сказал ранее - это отставание было больше, когда Вы начинали, так что я бы на этот аргумент не обижался, а расценивал его как комплимент ! Что же произойдёт через 5-6 лет ? Тогда вы, программисты русских шашек, достигнете того же уровня, что и чекерсные программисты - полность разберётесь и с "человеком в русских шашках", и с самими русскими шашками.



4. Ну и последнее. Вы пишете:



"Более того, я считаю, что если бы ведущие российские разработчики вдруг всерьез взялись за разработку программ, играющих в чекерс, то мы бы составили серьезную конкуренцию самым сильным западным чекерсным программам. Конечно, не в плане теории дебютов и миттельшпилей (здесь нужно время!), но в смысле игровых алгоритмов, эндшпильных баз и т. д."



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



5. А что там говорил Камынии ? Он что, утверждал, что программы по русским шашкам обогнали на сегодняшний день чекерсные программы ? А большего я и не утверждал. С многими другими доводами, приведёнными Камининым, я в принципе согласен и говорил об этом в моём интервью на ТАВЛЕЯХ. И ещё раз могу повторить - обгон этот не за счёт "интеллектуальной убогости", а в силу объективных обстоятельств.



=======================================================



"Экспресс ответ А. Кандаурову. Ошибка твоя состояла в том, что ты написал, что контроль времени 10 минут на партию в Интернете будет достаточно, чтобы бороться с нечестной игрой. Для программ в русские шашки может быть и достаточно, но не для чекерсных программ ! Для того, чтобы использовать (честно или нечестно) программу по чекерс для быстрой игры в Интернете, мне надо следующее :



1) Стартовать загрузку программы на моём ПК до начала партии (это занимает 1-2 минуты). Мне не надо отдельного компа, чтобы использовать программу.



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



3) При некоторой сноровке это занимает около 5-6 секунд, и если считать среднюю продолжительность партии около 25 ходов, то всего надо 2.5-3 минуты. Если же позиция серьёзная, и надо погонять шашки "туда-назад" и посмотреть, как играет программа в разных случаях, то и это на каждый прогон отнимет не более 20-30 секунд.



4) Цитирую : "Я уверен, что просто заткнули бы за пояс. Даже дети во всем мире знают, откуда родом все лучшие в мире программисты"



Ну этот пассаж напоминает мне аргументы Непослушного, типа - "это и ежу понятно". Отвечу его же словами - "полнейшая фигня!"



5) Саша, я согласен с твоим аргументом, что с программами в русские шашки на сегодняшний день всё это проделать за 2-3 минуты невозможно. Так кто же из нас катит бочку на программы по русским шашкам ??? Твой довод - самый лучший аргумент, подтверждающий правильность моих слов !



С уважением,



А. Моисеев[addsig]
sancoder - Июнь 17, 2004 - 09:43 AM
Тема сообщения: 2821
Quote:


1) Стартовать загрузку программы на моём ПК до начала партии (это занимает 1-2 минуты). Мне не надо отдельного компа, чтобы использовать программу.

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






Александр, это же просто ... невидение дальше своего носа.

Вы бы хоть тему эту почитали....

Ясно сказано, что на ВОГе при переключении в другую программу - включается сигнал.



И еще по поводу скорости:

вот если вы в шахматный форум зайдете и скажете, что в чекерсе программы считают на 30 полуходов за 2 мин, а в шахматах - всего на 13-14 полуходов, и, следовательно они отстают на 20 лет. Что вам там скажут? [addsig]
alemo - Июнь 17, 2004 - 10:35 AM
Тема сообщения: 2822
"И еще по поводу скорости:

вот если вы в шахматный форум зайдете и скажете, что в чекерсе программы считают на 30 полуходов за 2 мин, а в шахматах - всего на 13-14 полуходов, и, следовательно они отстают на 20 лет. Что вам там скажут?"



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



Кстати, вы сделали характерную ошибку - чекерсные программы могут считать на 30 полуходов за 30 секунд, а не за 2 минуты. Программы эти писали очень сильные и профессиональные программисты, и далеко не сразу они вышли на этот уровень. Дело здесь не в "простоте или сложности игры", как многие пытаются представить.



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



А. Моисеев[addsig]
Alkand - Июнь 17, 2004 - 08:43 PM
Тема сообщения: 2825
Обсуждение этой (да и многоих других) темы показало, что я совсем не занимаюсь модерированием форумов. И почти в любом топике полно (если не большая часть офф-топика. Делить и переносить посты тут невозможно, поэтому попробую перенести этот форум на другой движок. И тогда уже будет легче отделять "мух от котлет"

Quote:
" Кстати, вы сделали характерную ошибку - чекерсные программы могут считать на 30 полуходов за 30 секунд, а не за 2 минуты. Программы эти писали очень сильные и профессиональные программисты, и далеко не сразу они вышли на этот уровень. Дело здесь не в "простоте или сложности игры", как многие пытаются представить.



А вот это, на мой взгляд, неверный подход. Давайте-ка в студию ЧИСЛО позиций, рассмотренных программой за 30 секунд. И не надо "лечить" тут всех полуходами.

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

В русских же поначалу считается дерево для тех же вариантов, что и в чекерс. Но хода с третьего появляются размены назад, которые меняют весь рисунок, и вновь "растут деревья", на этот раз уже новые. И таких ситуаций немало. Так что путь до первого эндшпиля в русских идет серез ГОРАЗДО бОльшее число легальных позиций.

И сразу предупрежу, не нужно аргументов по поводу общего числа позиций в чекерсе и русских. Понятно, что просто число расстановок шашек двух цветов на 32 полях в этих играх совпадет.

А вот если программа перебирает только ЛЕГАЛЬНЫЕ позиции, то вот именно эти числа и нужно сравнивать. И чую я, что по этим показателям за шахматами не угнаться.

И еще мне кажется вот что - можно принять за критерий сложности (для программы и/или человека) той или иной игры, если сравнить производительность программ (близких к идеальной). Например, если чекерсная программа перебирает 10 млн позиций за 30 секунд на 30 полуходов, а программа в русские те же 10 млн. перебирает за 60 секунд и на 15 полуходов, то я бы сказал, что -

- чекерсная программа производительнее (быстрее) в два раза.

- но и "сложность" (а может и без кавычек) русских "в два раза" (только не смейтесь над таким "коэффициентом") выше. Потому что число разветвлений в этой игре больше. [addsig]
sancoder - Июнь 17, 2004 - 10:06 PM
Тема сообщения: 2826
Quote:
В чекерсных программах за 30 секунд при наличии мощнейшей оперативной памяти (2 ГБ и выше) программа просчитывает до 30 полуходов вперёд, при наличии "скромненькой" оперативной памяти, как на моём компе (512 КБ), программа за это же время "видит" на 20-22 полухода вперёд. У Вас быстрее ?





Вообще-то да, быстрее.

На 20 полуходов программа считает за 19 секунд на компьютере 3-х летней давности

[addsig]
alemo - Июнь 18, 2004 - 07:20 AM
Тема сообщения: 2828
АК ==> Често говоря, не я завязал этот спор, - я просто сказал, что чекерсные программы обгоняют программы в русские шашки на несколько лет, но и этот, казалось бы бесспорный факт вызвал сомнение. Придётся наверное мне поработать переводчиком и привлечь сюда самих чекерсных программистов, поскольку вопросики посыпались уж очень специальные и конкретные. Я помню на каких то чекерсных форумах программисты приводили эти числа. Будет вам число позиций. Заодно и выясним насчёт "разменов вперёд-назад" и разветвлений.



АЛЕМО [addsig]
Alkand - Июнь 18, 2004 - 07:35 AM
Тема сообщения: 2829
Quote:
АК ==> Често говоря, не я завязал этот спор, - я просто сказал, что чекерсные программы обгоняют программы в русские шашки на несколько лет, но и этот, казалось бы бесспорный факт вызвал сомнение.



Мне стало за державу обидно. Да и аргументов не было приведено.

А количество обработанных позиций разве не выводится чекерсными программами ? Ни одной из замечательных [addsig]
alemo - Июнь 18, 2004 - 09:23 AM
Тема сообщения: 2830
Выводится ... всеми замечательными ! Но уж коли речь пошла за державы будет лучше, если они (чекерсные программисты) сами приведут цифры. Не хочу работать испорченным телефоном И как я уже сказал - заодно разберёмся с числом позиций и "сложностью". Тебе за державу обидно, а мне - за игру !



АЛЕМО[addsig]
sancoder - Июнь 18, 2004 - 03:19 PM
Тема сообщения: 2835
Вот и закончились аргументы, которых не было ... [addsig]
alemo - Июнь 18, 2004 - 06:01 PM
Тема сообщения: 2838
Но я и не спорил и ничего не аргументировал, просто считал, что это и так очевидный факт, "понятный и ежу". Но коль скоро возникли сомнения и стали требовать серьёзные аргументы, то будут и аргументы. Со стороны моих оппонентов я тоже не слышал ничего серьёзнее, чем: "С чего Вы это взяли, докажите!" Докажем !



Наберитесь терпения, почаще заходите на этот сайт и следите за моими (alemo) сообщениями.



А. Моисеев[addsig]
sancoder - Июнь 18, 2004 - 06:18 PM
Тема сообщения: 2839
При минимальной оценочной функции из начальной позиции (Athlon XP 1600+ @1.4GHz. 512 MB RAM):

15 полуходов - 0,2 сек (0,8 млн поз.)

17 полуходов - 1,2 сек (3,2 млн поз.)

19 полуходов - 4,9 сек (13 млн поз.)

Скорость - 2,62 млн поз в сек



При максимальной оценочной функции:

15 полуходов - 3 сек (6 млн поз.)

17 полуходов - 8 сек (15 млн поз.)

19 полуходов - 19 сек (38 млн поз.)

Скорость - 1,9 млн поз в сек

[addsig]
sancoder - Июнь 18, 2004 - 06:30 PM
Тема сообщения: 2840
Есть еще нулевой режим оценочной функции (только выигрыш/проигрыш/ничья):



19 полуходов - 2,2 сек (6 млн поз)

Скорость - 2.7 млн поз в сек

[addsig]
Fenix - Июнь 18, 2004 - 06:37 PM
Тема сообщения: 2841
Quote:
Но я и не спорил и ничего не аргументировал, просто считал, что это и так очевидный факт, "понятный и ежу". Но коль скоро возникли сомнения и стали требовать серьёзные аргументы, то будут и аргументы. Со стороны моих оппонентов я тоже не слышал ничего серьёзнее, чем: "С чего Вы это взяли, докажите!" Докажем !



Наберитесь терпения, почаще заходите на этот сайт и следите за моими (alemo) сообщениями.





...Ну этот пассаж напоминает мне аргументы Непослушного, типа - "это и ежу понятно". Отвечу его же словами - "полнейшая фигня!"








Здравствуйте!

Судя по всему надо следить за "непослушным", а не за "alemo"...

Ведь так похожи стали речи...



С уважением, Петр.



P.S.

Впрочем, господа русаки (а заодно и стоклеточники), что вы понимаете в любви к чекерсу?...



[addsig]
MiG - Июнь 18, 2004 - 08:40 PM
Тема сообщения: 2842
А вот что выдает движок игровой программы TORNADO III:



Athlon XP 2500+ (~1837 MHz), L2 512 Kb

1,5 Gb RAM



ОФ - только материал



Глубина | Время | Позиций

----------------------------------------

17 полуходов | 1 сек. | 2,18 млн. поз.

19 полуходов | 2 сек. | 6,91 млн. поз.

21 полуход | 8 сек. | 26,82 млн. поз.

23 полухода | 31 сек. | 94,68 млн. поз.



Скорость = 3,03 млн. поз. в секунду.



Полная ОФ:



Глубина | Время | Позиций

----------------------------------------

15 полуходов | < 1 сек. | 2,25 млн. поз.

17 полуходов | 8 сек. | 17,88 млн. поз.

19 полуходов | 19 сек. | 43,16 млн. поз.

21 полуход | 61 сек. | 137,6 млн. поз.



Скорость = 2,25 млн. поз. в секунду.



С уважением,

Михаил Глизерин.[addsig]
alemo - Июнь 18, 2004 - 08:53 PM
Тема сообщения: 2843
Вся информация и вопросы переправлены чекерсным программистам (двоим). Надеюсь ответ будет быстро.



А. Моисеев[addsig]
alemo - Июнь 18, 2004 - 09:48 PM
Тема сообщения: 2845
Пришёл ответ от первого программиста. Он говорит, что в той конфигурации, которая у ТУРБО, быстродействие его программы будет 1.5 (полтора) миллиона позиций в секунду, но после этого он пишет, что так сравнивать нельзя, поскольку если программа имеет большую по размерам дебютную библиотеку и эндшпильную базу, то поиск и перебор, само собой будет медленнее. Он например сказал, что когда у его программы несколько лет назад былы намного меньшие по размеру эндшпильная и дебютая базы данных, скорость была выше !



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



Опять таки, чтобы не работать "испорченным телефоном", я привожу ниже его полный ответ на английском



============================================================

hi alex,



on such a computer, cake would run at 1.5 million positions/second maximum.

however, that is simply not interesting at all. the number of nodes/sec is no measure

of strength whatsoever. earlier versions of both cake and kingsrow search more

nodes/sec than the current versions, but are much weaker. the reason is simple:

the more knowledge you add to your evaluation, the slower your program gets

in n/s. but if the knowledge you added is sensible, it will be very useful.

another example is the endgame database: the larger the database, the slower

the program gets in n/s. but of course it gets stronger...



BTW (by the way), it would be very easy for me to write a program that runs at around 3 million n/s. but it would be painfully weak!



i can see no objective way of comparing the programs for the two games except this:

ask them how large their endgame databases and their opening books are. in our

form of checkers, these are in fact the key elements for the best programs. if you do

not have an 8-piece db, and do not have a 1-million-move opening book, you will

get destroyed by the programs that have that, more or less regardless of the basic

strength of the respective engines.



the data on depth vs time/nodes is useless, since this is very different in different

positions and probably totally incomparable between the two games anyway.



let me know what they have database and bookwise!



cheers

martin

========================================================



Как вы видите в конце он спрашивает про размер ваших баз данных (дебютной и эндшпильной). Будем продолжать разговор с ним ? От себя могу добавить, что программа эта (Сake) очень сильная, но не сильнейшая и не чемпион мира.



А. Моисеев

[addsig]
alemo - Июнь 18, 2004 - 10:47 PM
Тема сообщения: 2846
От второго программиста ответ был короче. Он получил также ответ и от первого программиста, который я поместил в предыдущем посте. Эд также, как и Мартин считает, что сравнение по силе программ в разные игры невозможно, а скорость само собой не имеет ничего общего с силой. Единственно, что можно сравнивать - размер баз данных: дебютных и эндшпильных. Оба чекерсных программиста сходятся в том, что размер баз данных является ключевым моментом, определяющим силу программ. На алгоритм они сильно не упирают.



От себя могу добавить, что на чекерсном форуме между собой у них были дебаты насчёт "сжатия-разжатия" баз данных, доступа и других технических моментов.



Как вы видите, ответ второго программиста был более сухой, и кроме того он попенял меня за моё острое высказывание и сказал, что, что не сомневается в том, что программисты русских шашек работают не меньше и не хуже, чем они и сравнение здесь ни к чему. Привожу здесь также его ответ на английском языке.



==========================================================



You cant tell anything about a program's strength by its search speed, or

search depths, so it is meaningless to try to compare those things. As

Martin said, opening books and endgame databases are two of the main

components of program strength, and maybe the only things that you can try

to compare between these two different games.



-- Ed

===========================================================



Как видите, меня лично в первую очередь интересует истина, а не амбиции. Думаю информации от Эда и Мартина достаточно, чтобы сделать какие-то выводы. Программа, автором которой является Эд, KingsRrow, более сильная и мощная с моей точки зрения.



Обе программы, KingsRow и Cake - некоммерческие и могут быть загружены бесплатно с эндшпильными (6 фигурная) и дебютными базами данных с вэб сайт. Само собой это не турнирные версии программ.



С уважением,



А. Моисеев[addsig]
alemo - Июнь 25, 2004 - 04:04 AM
Тема сообщения:
Сегодня поговорил ещй с одним программистом - автором программы WCC (World Checkers Champion). Он сказал, что быстродействие его программы - 4 миллиона позиций в секунду, но у него очень мощная машина (если вас интересуют подробности насчёт конфигурации - дайте знать, могу уточнить). Это очень оригинальный программист и человек. Он сказал например, что ему чихать на библиотеку дебютов, так как программа, имея 10-фигурную эндшпильную базу данных и мощнейшую машину - может всё решить сама, без всякой дебютной библиотеки !

Он в частности утверждает, что в позициях с 18 шашками программа за 30 секунд видит всё до конца (!), то есть до эндшпильной базы данных. Его библитотека дебютов небольшая и включает всего 120.000 позиций (у других программ это число больше миллиона).

А. Моисеев
Alkand - Июнь 25, 2004 - 07:13 AM
Тема сообщения:
[quote="alemo"] Он в частности утверждает, что в позициях с 18 шашками программа за 30 секунд видит всё до конца (!), то есть до эндшпильной базы данных. [/quote]
А любопытно, какой при этом диапазон полуходов? Так сказать средняя длина партии от позиции с 18 шашками до ЭБ 10-ки.
И какова та же дистанция от стартовой позиции до позиций с 18 шашками. Иными словами, как скоро ожидать "закрытия" игры для машины?
MiG - Июнь 25, 2004 - 10:17 AM
Тема сообщения:
«Его библитотека дебютов небольшая и включает всего 120.000 позиций (у других программ это число больше миллиона)»

Да уж... Следует признать, что в этом плане мы очень сильно отстали. И догоним ли? Сейчас, если не ошибаюсь, самая большая ДБ у PLUS 600. Но и там вроде бы число позиций не превышает 20.000. А тут маленькая ДБ содержит «всего-то» 120.000 позиций.

Конечно, интересно знать, на какой машине работает автор World Checkers Champion. Кстати, Алекс, не могли бы Вы привести здесь ссылки на сайты упоминаемых Вами программ?

С уважением,
МиГ.
sancoder - Июнь 25, 2004 - 12:29 PM
Тема сообщения:
Михаил: в гугле слово chinook Smile
Alkand - Июнь 25, 2004 - 12:42 PM
Тема сообщения:
Цитата:
Его библитотека дебютов небольшая и включает всего 120.000 позиций (у других программ это число больше миллиона)

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

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

Кстати, хорошо бы определиться, о каком количестве ходов (или шашек на доске) мы говорим, упоминая выражение - дебют. Question
plus600 - Июнь 25, 2004 - 01:16 PM
Тема сообщения:
MiG писал(а):
Сейчас, если не ошибаюсь, самая большая ДБ у PLUS 600. Но и там вроде бы число позиций не превышает 20.000.

1. Именно так
2. Превышает, и в терминах чекерсных шашистов превышает намного.
alemo - Июнь 25, 2004 - 03:50 PM
Тема сообщения:
На основании вопросов, которые здесь появились, я послал имэйл Эду Трайсу (автору 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
===========================================================

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

А. Моисеев
MiG - Июнь 25, 2004 - 04:37 PM
Тема сообщения:
2. Превышает, и в терминах чекерсных шашистов превышает намного.

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

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

С уважением,
МиГ.
Alkand - Июнь 25, 2004 - 04:39 PM
Тема сообщения:
alemo писал(а):
Насчёт "сложности" игр ... Эд увязывает это с чмслом возможных легальных ходов. Если мы согласимся с его критерием, то должны признать - что игры по сложности равны, поскольку количество ходов и общее число позиций одинаково.

Все по тексту понял, кроме... этого вывода Laughing Razz Эд ведь не напрасно написал про легальные ходы. То есть, если допустить, что в чекерсе будет легальным взятие назад и дамка будет "длинной", то тогда количество возможных ходов в этих двух играх совпадет. Very Happy Но, постойте! Постойте! Это ж будут уже ... русские шашки Shocked
А если серьезно, то Эд подтвердил мое предположение, высказанное где-то в этом топике, что наличие бОльшего числа вариантов и ветвлений (за счет размена назад) приводит к усложнению оценки, счета и выбора вариантов. То есть к усложнению самой игры.
alemo - Июнь 25, 2004 - 05:22 PM
Тема сообщения:
Саша, ты забыл "мозаичные позиции", которых нет в русских шашках. В этом смысле отсутствие боя назад расширяет число позиций, да и легальных ходов, а не сужает. Да и с дамками всё не совсем понятно. В русских шашках дальнобойность дамки количество ходов отнюдь не увеличивает, так как "бить обязательно" и массу чекерсных позиций здесь выпадает. В чекерс есть целый класс миттельшпильных позиций, с 1-2-3 дамками и массой простых с каждой стороны.

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

А. Моисеев
Alkand - Июнь 25, 2004 - 05:30 PM
Тема сообщения:
Да, я действительно забыл про "мозаичные позиции".
alemo - Июнь 25, 2004 - 05:50 PM
Тема сообщения:
Эд Трайс является, с моей точки зрения очень оригинальной и неординарной личностью с громадным интеллектом. В частности, у него очень острый язык и он никогда не лезет за словом в карман в споре и не очень беспокоится о "политической корректности" его аргументов. Я послал ему ещй один вопрос насчёт 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.

==============================================================
plus600 - Июнь 25, 2004 - 07:49 PM
Тема сообщения:
Есть простой "медицинский" факт - в среднем число возможных легальных ходов (или употребляя более корректный термин - коэффициент ветвления) в чекерсе меньше, чем в русских шашках. Факт потому, что я могу сравнивать эти значения для одного и того же своего движка в разных играх.
Конечно, есть конкретные позиции, где число возможных ходов по правилм чекерса будет больше, но обратных позиций ГОРАЗДО больше.
plus600 - Июнь 25, 2004 - 07:55 PM
Тема сообщения:
MiG писал(а):
Сергей, а какое количество позиций (не ходов!) именно в дебютной библиотеке PLUS 600. Под ДБ я в данном случае имею ввиду теоретические позиции, введенные человеком.

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

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

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

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

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

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

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

А. Моисеев
MiG - Июнь 25, 2004 - 08:30 PM
Тема сообщения:
Алекс, Вы спутали меня (Михаила Глизерина, разработчика программы TORNADO) с Сергеем Старцевым (разработчик PLUS 600) Smile Или Вы представляете для себя всех российских разработчиков в виде этакой "коллективной физиономии" ((с) Василий Уткин) Smile ?

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


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

С уважением,
МиГ.
MiG - Июнь 25, 2004 - 08:43 PM
Тема сообщения:
Цитата:
у меня каждая позиция содержит один ход


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

С уважением,
МиГ.
alemo - Июнь 25, 2004 - 09:16 PM
Тема сообщения:
Михаил, насморка нет, просто обычно перед тем, как послать сообщение, я его проверяю и исправляю, а в этот раз поспешил. Как вы могли сообразить - буквы "л" и "д" у меня на клавиатуре рядом.

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

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

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

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

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

А. Моисеев
plus600 - Июнь 25, 2004 - 09:28 PM
Тема сообщения:
alemo писал(а):

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

Я, наверное, не ясно выразился. Да, добились - и это не мои теоретические рассуждения, а факт - в чекерсе в среднем (именно в среднем!) коэффициент ветвления (число возможных ходов из позиции) меньше, чем в русских шашках.
sancoder - Июнь 25, 2004 - 09:35 PM
Тема сообщения:
Александр, я вам вот что скажу:
если программист в последнем письме (разговор о ничье из ЭБ) написал то, что он думает, и упрощений не делал, то здесь он отстает от нас (по крайней мере от Тундры), причем сильно.
Во-первых он ошибается, когда говорит что-то о 300 очках и что никто не пойдет на позицию 5 на 6. Неужели ударов в чекерсе не существует?
А во-вторых, понятие "ничья из ЭБ" имеет ограниченный (слишком) смысл без вот такого понятия "кто ее достигает".

К примеру, в Тундре есть поиск выигрыша и ничьи. И если при поиске ничьи программа находит ничью она говорит, что из этой позиции можно достичь ничьи; а если при поиске выигрыша программа говорит ничья, то это значит "выигрыш не достижим".
MiG - Июнь 25, 2004 - 10:31 PM
Тема сообщения:
Цитата:
Чем они, кроме способа построения, отличаются от "ручных" баз данных ?


Алекс, но это же очевидно... ДБ, введенная вручную, содержит и обобщает то, что было найдено человеком (без помощи или с помощью программ(ы)). В ДБ, сделанной программой, обобщается опыт этой самой программы Smile Кстати, и первое, и второе может быть не свободно от ошибок.

Цитата:
Во-первых он ошибается, когда говорит что-то о 300 очках и что никто не пойдет на позицию 5 на 6. Неужели ударов в чекерсе не существует?
А во-вторых, понятие "ничья из ЭБ" имеет ограниченный (слишком) смысл без вот такого понятия "кто ее достигает".


Мне кажется, что Эд Трайс все прекрасно знает Smile Просто, он написал несколько упрощенно. Так как далее уже детали, понятные далеко не всем (а скорее, почти никому Smile).

Например, ещё нужно учитывать такой фактор, как "цена ничьей". А Эд, наверное, имел ввиду то, что никто не будет ухудшать позицию, если есть ничья по базе. Вот и все.

С уважением,
МиГ.
alemo - Июнь 25, 2004 - 10:33 PM
Тема сообщения:
Plus 600: " ... наверное, не ясно выразился. Да, добились - и это не мои теоретические рассуждения, а факт - в чекерсе в среднем (именно в среднем!) коэффициент ветвления (число возможных ходов из позиции) меньше, чем в русских шашках "

Похоже, я пропустил что-то очень существенное. Где, когда и кем доказан этот факт ? Простые "житейские" соображения этого не подтверждают. Если мы поставим на доске любую позицию без дамок, то возможны два варианта:

1. В безударных позициях и позициях с боем только вперёд (до дамок) число разветвлений (легальных ходов) будет одинаково и в чекерс и в русские шашки.

2. В позициях с боем назад в русских шашках бой и будет легальным ходом, ну а в чекерс - ЛЮБОЙ другой ход (значительно больше одного) будет легальным !

Где ошибка в моих рассуждениях ? Если же вы хотите сюда добавить дамочные ходы, тогда - да!, конечно. С поля d4 дамка в русских шашках может сделать 13 легальных ходов (без боя), а в чекерс только 4. Если же учесть, что все статистики по БД, особенно эндшпильным, учтитавают дамки, то это очень сильно влияет и меняет СРЕДНЕЕ число разветвлений. Тут я спорить не буду.

============================================================

Sancoder : " ... если программист в последнем письме (разговор о ничье из ЭБ) написал то, что он думает, и упрощений не делал, то здесь он отстает от нас (по крайней мере от Тундры), причем сильно"

Не уверен. Они (чекерсные программисты, включая Эда) через это прошли несколько лет назад. Они тогда тоже очень усиленно работали над алгоритмами и улучшали их. Пытались найти лучший ход уже в БД (не все ничьи равны!) ну и так далее ... Но в конце концов все (ВСЕ!) чекерсные программисты пришли к выводу, что путь этот если и не тупиковый, то бесперктивный, и усиление баз данных достигает нужного результата значительно быстрее и эффективнее.

Даже если я и соглашусь с Вами, что ваш подход (алгоритмический ?) заслуживает внимания, то и в этом случае всё равно - существует какой то необходимый минимум размера БД, без которого серьёзного прогресса быть не может. Может быть 100,000 - 200,000 позиций ...

Если Вы стремитесь заставить программу играть, как человек, то она никогда и не будет играть лучше человека !

Это похоже на рассуждения некоторых игроков, которые я часто слышу - "мне теория не нужна. У меня и так есть расчёт и интуиция!"

А. Моисеев
alemo - Июнь 25, 2004 - 11:04 PM
Тема сообщения:
" Алекс, но это же очевидно... ДБ, введенная вручную, содержит и обобщает то, что было найдено человеком (без помощи или с помощью программ(ы)). В ДБ, сделанной программой, обобщается опыт этой самой программы Кстати, и первое, и второе может быть не свободно от ошибок ... "

Михаил, мне кажется вы упрощённо понимаете идею генерации. Из ваших слов следует, что мы ставим начальную позицию 12х12 и программа "с чистого листа" начинает думать и генерировать свою теорию. Это не так ! Исходная теоретическая база данных всё равно опирается на человеческий опыт. Никто этого не отрицает и не миновал, и чекерсные программисты тоже. Вот Старцев пишет, что его дебютная библиотека вкючает 23,700 позиций. Отлично. Вот эта база и должна стать исходной для генерации, или скажем так - первого итерационного этапа генерации. Пусть программа "пройдёт" по всем позициям и проверит их все - нет ли где лучше или равноцноого хода, предлагаемого БД. Или простого ещё одного не проигрывающего хода. А впрочем можно и проигрывающего - ведь иногда надо знать и как выиграть. Допустим к каждой позиции в БД программа добавила всего один дополнительный ход (расширение по горизонтали). Вот вам и 47,500 позиций в БД ! Первая итерация. Ну и так далее.

А потом возьмите и продолжите "концы вариантов" на один ход (расширение по вертикали). В этом случае кстати возможна обратная коррекция всего дерева, если обнаружится, что какие-то варианты "с дыркой". И эта БД из 47,500 позиций уже не будет чисто человеческой.

А что делает человек, когда анализирует и готовит новинки ? То же самое ! Берёт позицию, анализирует и улучшает/добавляет новые ходы. Только в вашем случае (с программой) этот процесс будет на качественно ином уровне.

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

А. Моисеев
Damon - Июнь 26, 2004 - 12:47 AM
Тема сообщения:
Алемо (насчет коэффициента ветвления):
Речь - именно о числе разветвлений "в среднем", увеличение которого в русских за счет дамок Вы признаете.
Что касается случая 2, то как же он может повлиять на этот коэффициент?? - бьем назад, и все!!!... Very Happy Mr. Green Very Happy Mr. Green
----------------------------------
Сергей Педько
alemo - Июнь 26, 2004 - 01:19 AM
Тема сообщения:
Сергей, Вы всё абсолютно правильно поняли и догадались, к чему я клоню. Я принимаю и не собираюсь оспаривать (если серьёзные люди говорят - я им верю) факт на который тут ссылались насчёт более высокого В СРЕДНЕМ коэффициента разветвления в русские шашки. Вот мы и подобрались (?) к истине ! Именно за счёт дамок этот СРЕДНИЙ коэффициент и выше в русских шашках. Дамки всё вытянули !

Только я боюсь, что эта истина не совсем та, которую некоторые наверное хотели бы услышать. В частности Алканд своими вопросами упорно подталкивал к мысли, что русские шашки - более сложная позиционная игра. А получили ... дамки. И то это влияет только на коэффициент, так как в затяжных эндшпилях в чекерс требуется намного больше ходов (читай позиций). Там, где дамке в русские шашки требуется 1 ход, в чекерс - 3-4 или больше. Так что в эндшплях в чекерс надо считать "дальше", а в русские шашки - "глубже". Согласны ?

Каков процент собственно эндшпилей в игре ? Пусть практики ответят мне. А если хотите - давайте вычислим отдельно коэффициент для эндшпилей и до дамок.

А. Моисеев
plus600 - Июнь 26, 2004 - 08:37 AM
Тема сообщения:
Александр!
Давайте еще раз отделим мух от котлет. Я говорил только о сравнении двух игр с точки зрения их программирования. С этой точки зрения совершенно не важно соотношения коэффициента ветвления в текущей позиции, для этого важно среднее его значение при проходе по дереву перебора из этой текущей позиции. Как пример, из начальной позиции в переборе дамки возникают очень быстро. И дерево перебора в черерсе почти всегда (исключения я допускаю, но не видел пока) будет содержать значительно меньше позиций, чем в русских шашках при одинаковой глубине перебора.
Да, концовки в чекерсе нужно считать дальше, но (опять же факт) именно в концовках отношение коэффициента ветвления еще больше увеличивается.
А чем доказан этот факт я уже писал - это сравнение чисел для одного и того же движка для этих игр.
Вообще, сложность для программирования переборных игр зависит только от двух параметров - коэффициента ветвления и сложности формализации оценочной функции. Поэтому и получается, что чекерс для программирования более простая игра, чем русские шашки.
Еще раз оговорюсь, что из этого совершенно не следут вывод о том, какая игра проще - это совсем другие критерии!!!

С уважением,
Сергей Старцев
plus600 - Июнь 26, 2004 - 08:41 AM
Тема сообщения:
MiG писал(а):
Цитата:
у меня каждая позиция содержит один ход


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

Конечно существуют. Но если в позиции есть два хода, то это тоже самое, что хранить две позиции после этих ходов.
Greb - Июнь 26, 2004 - 12:49 PM
Тема сообщения:
Symix писал(а):

U menya drugoye otnosheniye

Согласен. Допустим, завтра Старцев скажет - моя программа просчитала все... белые начинают и выигрывают. Ну и что? Все равно Кандауров у меня выиграет (может). Это главное.
MiG - Июнь 26, 2004 - 01:09 PM
Тема сообщения:
Цитата:
Согласен. Допустим, завтра Старцев скажет - моя программа просчитала все... белые начинают и выигрывают. Ну и что? Все равно Кандауров у меня выиграет (может). Это главное.


А вот это абсолютно неправильная постановка вопроса.Решение проблемы шашек и игра между людьми — суть разные вещи. Они, конечно, пересекаются между собой, но не так, как сказал Greb.

Также не совсем понимаю Symix`а. Современные игровые программы предоставляют достаточно возможностей не только для игры, но и для изучения шашек. Вот, например, эндшпильные базы предоставляют нам беспрецедентные возможности для анализа и изучения эндшпиля. Просто, не все ещё это понимают.

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

С уважением,
МиГ.
alemo - Июнь 26, 2004 - 02:28 PM
Тема сообщения:
plus600 писал(а):

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


Очень любопытно. То что вы пишите здорово перекликается с тем, что ответил мне Эд Трайс, когда я спросил его о сложности. Приведу здесь кусочек из его ответа:

==============================================================

<< 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 4x3 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 10x10 draughts, easily. But, since 10x10 draughts has kings that move like Bishops, checkers may have the greater decision complexity.

============================================================

Одно и тоже ! Не совсем только понятно со вторым критерием - почему вы считаете, что сложность формализации, или как Эд Трайс говорит - сложность решения, в русских шашках выше ?

А. Моисеев
plus600 - Июнь 26, 2004 - 02:33 PM
Тема сообщения:
alemo писал(а):

Одно и тоже ! Не совсем только понятно со вторым критерием - почему вы считаете, что сложность формализации, или как Эд Трайс говорит - сложность решения, в русских шашках выше ?

А. Моисеев

А я так и не считаю. Этот фактор достаточно одинаков в этих двух играх. Нюансы есть, но проблемы похожие. Что точно могу сказать - так и там и там это намного сложнее, чем в шахматах...
plus600 - Июнь 26, 2004 - 02:36 PM
Тема сообщения:
Greb писал(а):
Symix писал(а):

U menya drugoye otnosheniye

Согласен. Допустим, завтра Старцев скажет - моя программа просчитала все... белые начинают и выигрывают. Ну и что? Все равно Кандауров у меня выиграет (может). Это главное.

Я тоже абсолютно с этим согласен. Решение шашечной задачи интересно только программистам, игрокам от этого толку очень мало Smile.
На эту тему я уже высказывался, и своей позиции пока не менял и не собираюсь. Также я по прежнему открыт для всех пожеланий пользователей.
sancoder - Июнь 26, 2004 - 03:12 PM
Тема сообщения:
Александр, ну я же ваши ответы читаю....
А вы мои? Речь идет не о игре в базе, а о игре до ЭБ. То, что игра в ЭБ была пройдена (несколько лет назад) - верю. То, что из позиции с 12 шашками на доске он точно определит ничью - НЕТ! НЕ ВЕРЮ.
alemo - Июнь 26, 2004 - 03:33 PM
Тема сообщения:
Я ему (Эду Трайсу) - ВЕРЮ. Он же приводил в своём ответе конфигурацию машины (из университета), к которой он получил доступ. Это же не машина, а какой-то монстр. Эд сам писал, что это даже не персональный компьюьер, а workstation. RAM у него - 128 GB (гегабайт!) и всю свою эндшпильную (почти всю 10-фигурную), а впрочем уже и не совсем эндшпильную, базу он загружает в оперативную память.

Кроме того Эд указывал, что это не полный перебор, так как число всех позиций в 10-фигурной базе - 8.5 триллионов, а его программа перебирает только 120 миллионов (4млн/сек х 30 сек). Только программа не только перебирает за это время, но ещё и оценивает, принимает решение - так, что это возможно.

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

К примеру gf4 hg5 ... должна ли программа продолжать поиск и анализ в этом "варианте" до ЭБ или может остановиться ? Very Happy

А. Моисеев
sancoder - Июнь 26, 2004 - 03:57 PM
Тема сообщения:
Знаете, Александр, дело не в том, какая у кого машина, а в нарботках. В алгоритмических наработках. То, что я имел в виду, говоря про позицию с 12 шашками и невозможности точно определить ничью - ничуть не затрагивало скорости перебора и т.п. Смысл был в следующем: с такой оценкой как у него определить ничью с математической точностью НЕВОЗМОЖНО. Повторюсь, что я имел в виду _математическую_ строгость доказательства.
Я хочу сказать, что программа может выдать на экран оценку 0 при глубине X - и это не будет ничьей, т.к. на глубине X+1 программа может изменить оценку в любую сторону. А смысл нашего преимущества заключается в том, что Тундра говорит с абсолютной точностью, что если ничья, то ее достигают либо белые, либо черные (здесь я немного упрощаю).
plus600 - Июнь 26, 2004 - 07:37 PM
Тема сообщения:
Symix писал(а):

Sudya po dvum russkim programmam chto ya videl user interface (obcheniye s igrokom) namnogo otstaet ot perebora variantov

А, если не секрет, какие именно русские программы Вы видели?

С уважением,
Сергей Старцев
alemo - Июнь 27, 2004 - 04:07 PM
Тема сообщения:
К сожалению наш диспут уплыл куда-то в сторону, и заодно размножается и расползается на разные подтемы, как тараканы , в частности - обучающие программы, итп.

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

А. Моисеев
plus600 - Июнь 27, 2004 - 04:46 PM
Тема сообщения:
alemo писал(а):
Вопрос который меня очень интересовал - признают ли программисты русских шашек важность дебютных библотек, и планируют ли всерьёз работать в этом направлении по улучшению - генераторы теории или какой-то другой метод ?

Я полностью согласен и работаю в этом направлении.

С уважением,
Сергей Старцев
MiG - Июнь 27, 2004 - 07:09 PM
Тема сообщения:
Цитата:
Я полностью согласен


А я нет. В программировании русских шашек ещё отнюдь не исчерпана а) работа над алгоритмами, б) работа над эндшпильными базами. Вот когда движки в русские шашки будут легко делать перебор на 30 полуходов, иметь 10-и фигурные ЭБ, вот тогда посмотрим Smile

А покамест делать основной упор на ДБ и любые «Б» кроме ЭБ мне кажется несколько неправильным Smile

Цитата:
Что же касается интэрфэйса, я человек непритязательный и непрвередливый - играла бы программа, а с кнопками разберёмся.


О, это по нашему Smile

С уважением,
МиГ.
Alkand - Июнь 27, 2004 - 07:43 PM
Тема сообщения:
Цитата:
К сожалению наш диспут уплыл куда-то в сторону, и заодно размножается и расползается на разные подтемы, как тараканы , в частности - обучающие программы

Я отделил тему об обучающих программах. Прошу придерживаться тем топиков.
Цитата:
Я по прежнему считаю, что на сегодняшний день, когда 8-фигурная ЭБ практически закончена и с "алгоритмическими наработками" всё в порядке (?) , создание новых и серьёзное улучшение существующих дебютных библиотек выходит на первый план.

"Выходит-то хорошо, заходит плохо" (С) Laughing Оставим в стороне выводы, какая игра сложнее. Тем более, что мне кажется все останутся при своем. Здесь проблема в том, что из дебюта в русских "добить" до ЭБ сложнее. А без этого компьютерной оценки позиции в ДБ не получить. Как уже было сказано, в чекерсе меньше ветвлений, программе легче рассчитать и сделать конкретную оценку позиции. И дело тут не в мощности компьютеров или исскусстве программистов. Сколько там известных позиций в чекерс после 3,4 полуходов, в которых доказан выигрыш одной из сторон? Или доказана ничья, оттого, что есть всего лишт один путь ее достичь? А в русских сколько таких позиций? Разумеется говорим о равном количестве шашек.
1. ed4 de5 ab4 ba5 fe3
2. gh4 de5 hg3 (fg3) ed6
Что еще я забыл? Дополняйте.
Разумеется, при более форсированной игре (чекерс) значение ДБ повышается, но и работать в этом направлении легче.
Ну - ка возьмите позиции косячка и проиндексируйте ветви. И кого где поприятнее. А потом я вам покажу ошибки. А если я сделаю эту работу, наверняка найдется тот, кто укажет мои. Laughing
alemo - Июнь 28, 2004 - 02:58 AM
Тема сообщения:
Э нет батенька, так нечестно - "при равном количестве шашек". А как насчёт таких дебютов, как:

cd4 dc5 ef4
cd4 de5 dc5
cd4 de5 ab4
ab4 ba5 cd4
ab4 de5 bc5
ed4 de5 cb4

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

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

К примеру такой интересный факт: ab4 dc5 дебют является проигрышным для чёрных, а cb4 dc5, хотя и критический, но ничейный.

Только вот ... что все эти цифры подтверждают или опровергают ?

===========================================================

И ещё ... чекерсные дебютные библиотеки отнюдь "не добивают до ЭБ", иначе мы должны были бы признать, что "чекерс решены". Основой построения всех этих дебютных библиотек является алгоритм, или как его здесь называют - "алгоритмический движок", или - "алгоритмические наработки".

Я что-то не понимаю ... если программисты русских шашек доверяют своим алгоритмам, то почему они боятся "отцепиться" от человеческой теории и двинуться вперёд, используя свои алгоритмы для генерации "новой, нечеловеческой теории" ?

Кстати, начальные предпосылки для формирования теории у программистов русских шашек намного богаче, чем у чекерсных программистов ! Я имею в виду вашу базу данных по партиям, что-то около 70,000 партий. Это же настоящий клад ! Если каждая партия в среднем - 25 ходов, то это около полутора миллиона позиций ! Даже если исключить процент повторения, то и в этом случае мы имеем 200,000-300,000 позиций. Само собой, ко всем партиям, сыгранных человеком, надо относиться очень осторожно. Важно знать - кто, когда, где и с кем играл, и после скольких стаканов ! Тем не менее эта база данных (по партиям) могла бы стать исходной информацией для формирования дебютных библиотек. И взята она будет от человека.

А. Моисеев
alemo - Июнь 28, 2004 - 04:03 AM
Тема сообщения:
Сильно подозреваю, что и такие дебюты, как

ef4 fg5 fe5
ef4 bc5 fe5
ed4 fg5 dc5
ed4 hg5 de5
ed4 hg5 de3

или большая их часть будут проигрышными в русские шашки.

(К числу проигрышных в предыдущем посте я кстати забыл отнести и такие, как: gf4 dc5 fe5, cd4 hg5 dc5).

И почему Вы всё таки упорно игнорируете в русских шашках жеребьёвку 3-х полуходов как класс ? Rolling Eyes Это же океан ! Громадная (и неизученная) территория для фантазии и анализа. Здесь всем хватит работы и места на 20-30 лет - и романтикам, и теоретикам, и программистам !

А. Моисеев
Alkand - Июнь 28, 2004 - 07:44 AM
Тема сообщения:
alemo писал(а):
И почему Вы всё таки упорно игнорируете в русских шашках жеребьёвку 3-х полуходов как класс ? Rolling Eyes Это же океан ! Громадная (и неизученная) территория для фантазии и анализа. Здесь всем хватит работы и места на 20-30 лет - и романтикам, и теоретикам, и программистам ! А. Моисеев

Если я чего не путаю, мы вроде с 1984 по 1991 годы играли финалы СССР с жеребьевкой 4 полуходов. Razz Да и другие турниры - тоже.
А вот когда "порулить" русскими шашками пришел их огромный "почитатель" г-н. Климашев (ох, ну почему в бедной России РУССКИМИ ШАШКАМИ должен рулить украинский еврей Very Happy ), то он заявил, что это не есть русские шашки Shocked и жеребьевку в России "сняли с пробега".
plus600 - Июнь 28, 2004 - 12:37 PM
Тема сообщения:
alemo писал(а):

Я что-то не понимаю ... если программисты русских шашек доверяют своим алгоритмам, то почему они боятся "отцепиться" от человеческой теории и двинуться вперёд, используя свои алгоритмы для генерации "новой, нечеловеческой теории" ?

Не все боятся "отцепиться"...
Alkand - Июнь 28, 2004 - 04:06 PM
Тема сообщения:
alemo писал(а):
Приведу цифры. При жеребьёвке 3-х полуходов в чекерс, число дебютов, при равном количестве шашек - 174. Думаю кстати, что это будет тоже самое число (и позиции) и в русские шашки. Только вот ... что все эти цифры подтверждают или опровергают ?

Да, в русские примерно столько же.
Цитата:
Кстати, начальные предпосылки для формирования теории у программистов русских шашек намного богаче, чем у чекерсных программистов ! Я имею в виду вашу базу данных по партиям, что-то около 70,000 партий.

А где-то на форуме промелькнула еще одна идея. По созданию МБ, миттельшпильной базы. Взять базу партий выбрать позиции, например с 10 по 12 ходы, и отобрать наиболее часто встречающиеся в игре, например от 100 раз и больше. Конечно, кое-что из "шлифов" сюда не попадет, но ничего идеального на свете нет. И вот эти позиции можно считать для начала наиболее актуальными и их можно рассчитать до конца. Вероятно такие похиции могут быть ориентирами для программы при расчете вариантов. Question
alemo - Июнь 30, 2004 - 02:02 AM
Тема сообщения:
Эта идея промелькнула не на форуме (я был бы только очень рад этому), а в моём интервью на ТАВЛЕЯХ. Впрочем я рад, что даже и там полезная и интересная информация не ускользнула от твоего орлиного глаза.

Единственная разность в том, что тогда я говорил о МБД - миттельшпильной базе данных, поскольку ошибочно в тот момент полагал, что с дебютными библиотеками у программ в русские шашки всё в порядке. Поскольку это оказалось неверно, то в том моём предложении ограничение на количество шашек надо снять и вытаскивать надо все позиции с хорошим коэффициентом повторения. Только теперь это уже будет общая БД от начала партии.

АЛЕМО
Zheka - Окт 18, 2013 - 02:52 PM
Тема сообщения:
У меня вопрос к программистам шашечных программ.
Представим ситуацию-я играю матч с программой с контролем-1 час мне и 5 минут программе.Ход мой,я думаю минут 40.За это время программа досчитала позицию до эндшпильной базы и знает как ответить на мой каждый ход лучшим образом.тут я хожу и программа сначала начинает пересчитывать то что уже насчитала,но со своим урезанным контролем и через секунд 20 делает нелучший ход.
Так ли это или же программа учитывает все предыдущие расчеты?
И учитывают ли программы свои расчеты в матчах с коротким контролем друг против друга?
AlexanderS - Окт 20, 2013 - 05:22 AM
Тема сообщения:
Zheka писал(а):
У меня вопрос к программистам шашечных программ.
Представим ситуацию-я играю матч с программой с контролем-1 час мне и 5 минут программе.Ход мой,я думаю минут 40.За это время программа досчитала позицию до эндшпильной базы и знает как ответить на мой каждый ход лучшим образом.тут я хожу и программа сначала начинает пересчитывать то что уже насчитала,но со своим урезанным контролем и через секунд 20 делает нелучший ход.
Так ли это или же программа учитывает все предыдущие расчеты?
И учитывают ли программы свои расчеты в матчах с коротким контролем друг против друга?


Как правило программы за время соперника считают ответ не на все возможные ходы, а только на тот, который считают лучшим (по основному варианту, рассчитанному при обдумывании прошлого хода). То есть программа допустим ждет от Вас сильнейший (с ее точки зрения) ход cd4, досчитала до ЭБ а Вы - бац! - и делаете cb4, приходится считать заново и на этот раз уже мало времени чтобы досчитаться до ЭБ. Часть информации от предыдущего расчета возможно и используется, если хэш не очищался но если заметных перестановок нет это не сильно поможет.

Мне так вообще расчет за время соперника делать до сих пор лень, выигрыш не такой заметный получается. При равном контроле и допустим 50% угадывании лучшего хода реальный выигрыш уже не такой большой, этого недостаточно чтобы заметно усилить программу. А если считать ответы на все ходы, допустим их 5-7, то вообще смысла нет. Такое действительно может быть эффективно только при гандикапе. Но тогда и смысл гандикапа потеряется Smile
Время в формате GMT + 3
PNphpBB2 © 2003-2007