Google
 

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

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

Login





 


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

Кто с нами

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


Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
Автор Сообщение
sancoder
Тема сообщения:   СообщениеОтправлено: Июнь 26, 2004 - 01:12 PM



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

Александр, ну я же ваши ответы читаю....
А вы мои? Речь идет не о игре в базе, а о игре до ЭБ. То, что игра в ЭБ была пройдена (несколько лет назад) - верю. То, что из позиции с 12 шашками на доске он точно определит ничью - НЕТ! НЕ ВЕРЮ.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Июнь 26, 2004 - 12:36 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1327
Откуда : Москва
Greb писал(а):
Symix писал(а):

U menya drugoye otnosheniye

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

Я тоже абсолютно с этим согласен. Решение шашечной задачи интересно только программистам, игрокам от этого толку очень мало Smile.
На эту тему я уже высказывался, и своей позиции пока не менял и не собираюсь. Также я по прежнему открыт для всех пожеланий пользователей.
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Июнь 26, 2004 - 12:33 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1327
Откуда : Москва
alemo писал(а):

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

А. Моисеев

А я так и не считаю. Этот фактор достаточно одинаков в этих двух играх. Нюансы есть, но проблемы похожие. Что точно могу сказать - так и там и там это намного сложнее, чем в шахматах...
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
alemo
Тема сообщения:   СообщениеОтправлено: Июнь 26, 2004 - 12:28 PM



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

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.

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

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

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



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

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


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

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

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

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



Зарегистрирован: Янв 16, 2004
Сообщений: 230
Откуда : г.Минск
Symix писал(а):

U menya drugoye otnosheniye

Согласен. Допустим, завтра Старцев скажет - моя программа просчитала все... белые начинают и выигрывают. Ну и что? Все равно Кандауров у меня выиграет (может). Это главное.
 
 Профиль пользователя отправить личное сообщение WWW  
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Июнь 26, 2004 - 06:41 AM



Зарегистрирован: Дек 24, 2002
Сообщений: 1327
Откуда : Москва
MiG писал(а):
Цитата:
у меня каждая позиция содержит один ход


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

Конечно существуют. Но если в позиции есть два хода, то это тоже самое, что хранить две позиции после этих ходов.
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Июнь 26, 2004 - 06:37 AM



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

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



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

Сергей, Вы всё абсолютно правильно поняли и догадались, к чему я клоню. Я принимаю и не собираюсь оспаривать (если серьёзные люди говорят - я им верю) факт на который тут ссылались насчёт более высокого В СРЕДНЕМ коэффициента разветвления в русские шашки. Вот мы и подобрались (?) к истине ! Именно за счёт дамок этот СРЕДНИЙ коэффициент и выше в русских шашках. Дамки всё вытянули !

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

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

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



Зарегистрирован: Авг 28, 2002
Сообщений: 352
Откуда : г.Харьков, Украина
Алемо (насчет коэффициента ветвления):
Речь - именно о числе разветвлений "в среднем", увеличение которого в русских за счет дамок Вы признаете.
Что касается случая 2, то как же он может повлиять на этот коэффициент?? - бьем назад, и все!!!... Very Happy Mr. Green Very Happy Mr. Green
----------------------------------
Сергей Педько
 
 Профиль пользователя отправить личное сообщение Послать e-mail  
Ответить с цитатой Наверх
alemo
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 09:04 PM



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

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

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

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

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

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

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



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

Plus 600: " ... наверное, не ясно выразился. Да, добились - и это не мои теоретические рассуждения, а факт - в чекерсе в среднем (именно в среднем!) коэффициент ветвления (число возможных ходов из позиции) меньше, чем в русских шашках "

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

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

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

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

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

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

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

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

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

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

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



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

Цитата:
Чем они, кроме способа построения, отличаются от "ручных" баз данных ?


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

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


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

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

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



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

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

К примеру, в Тундре есть поиск выигрыша и ничьи. И если при поиске ничьи программа находит ничью она говорит, что из этой позиции можно достичь ничьи; а если при поиске выигрыша программа говорит ничья, то это значит "выигрыш не достижим".
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Июнь 25, 2004 - 07:28 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1327
Откуда : Москва
alemo писал(а):

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

Я, наверное, не ясно выразился. Да, добились - и это не мои теоретические рассуждения, а факт - в чекерсе в среднем (именно в среднем!) коэффициент ветвления (число возможных ходов из позиции) меньше, чем в русских шашках.
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Показать:     
Перейти к:  
Время в формате GMT + 3
Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
PNphpBB2 © 2003-2007 
 
Page created in 0.531752109528 seconds.