|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
| saluki: но очень важны настройки того, как "отсекать". и тут крайне важна именно оценочная функция. рыба, как я понимаю, отсекает больше, чем другие программы, и вероятно - точнее. но добивается она этого за счет специфически шахматных решений, связанных с оценкой позиции, и едва ли применимых в других областях. |
Что значит "настройки того, как "отсекать"?
Я пока ознакомился с одной и предельно прозрачной настройкой - в примере от Мустица.
Да, оценочные функции у разных программ очевидно разные - соответственно отсекать они будут разное, но сама по себе "настройка того, как "отсекать" - совершенно одинаковая.
Насколько я сейчас это представляю, конечно, т.е. в меру моего невежества. |
|
|
| номер сообщения: 54-15-2183 |
|
|
|
|
| Edwards: оценочные функции у разных программ очевидно разные - соответственно отсекать они будут разное, но сама по себе "настройка того, как "отсекать" - совершенно одинаковая. |
Эдвардс, а нет ли противоречия выше - ведь ОФ это и есть "настройка того, как "отсекать"?  |
|
|
| номер сообщения: 54-15-2184 |
|
|
|
|
| Edwards: Что значит "настройки того, как "отсекать"? |
во-1, важно решить, с какого уровня расхождения оценки мы "перестаем смотреть" - мы же можем решить, что +1 достаточно, а можем и +0.1 удовлетворится.
во-2, мы можем определить что этот параметр "плавает" и зависит от числа фигур на доске, открытых линий, наличия коней в центре или на краю доски и так далее, далее, далее.
для "в-3" там остаются еще правила 3 кратного повторения, 50 ходов и даже всякий "произвол", типа требования с 8 фигур считать строго все до налимовской базы.
кстати, из-за ошибок настройки именно правила 50-и ходов рыбка в свое время эпохально слилась "Заппе". у нее было жесткое требование - избегать. и на 49 она на ровном месте сдала пешку и получила проиграно. |
|
|
| номер сообщения: 54-15-2185 |
|
|
|
|
Я тут нагуглил неплохую статью.
Кажется, по крайней мере, в качестве шахкомпьютерного ликбеза она вполне интересна - Алгоритмы шахматных программ |
|
|
| номер сообщения: 54-15-2186 |
|
|
|
|
Хайдук:
Эдвардс, а нет ли противоречия выше - ведь ОФ это и есть "настройка того, как "отсекать"? |
Нет, конечно.
ОФ - это ОФ. Она призвана не отсекать, а оценивать.
Оценка по ОФ уместна, актуальна для любой отдельно взятой позиции - т.е. тогда, когда никакой задачи отсечения вовсе не ставится. |
|
|
| номер сообщения: 54-15-2187 |
|
|
|
|
saluki: | Edwards: Что значит "настройки того, как "отсекать"? |
во-1, важно решить, с какого уровня расхождения оценки мы "перестаем смотреть" - мы же можем решить, что +1 достаточно, а можем и +0.1 удовлетворится.
|
Ну, нет, насколько я понимаю, тут решать нечего.
Если есть некий предел расчёта (он более или менее предопределяется имеющимся временем).
Обратимся к примеру Мустица. Пусть при 1.h3 g6 мы получили не +0.50, а все +4.99.
Тем не менее, это всё равно меньше, чем +5.00, полученные нами при расчёте 1.Bxh7+.
Таким образом, никакого смысла в том, чтобы смотреть остальные (помимо 1...g6) ответы на 1.h3 - нет. Нет, ибо и так уже ясно, что белые в варианте 1.h3 при данной глубине расчёта не получат ничего более, чем +4.99.
Тут всё очень жёстко.
Варианты возникают только, если та глубина, на которой мы получили +5.00 (и +4.99) - для нас не предельна.
saluki:
во-2, мы можем определить что этот параметр "плавает" и зависит от числа фигур на доске, открытых линий, наличия коней в центре или на краю доски и так далее, далее, далее.
|
Какой параметр плавает? |
|
|
| номер сообщения: 54-15-2188 |
|
|
|
|
Edwards: Я тут нагуглил неплохую статью.
Кажется, по крайней мере, в качестве шахкомпьютерного ликбеза она вполне интересна - Алгоритмы шахматных программ |
Спасибо, Эдвардс. "Просканировал" статью. Как я уже говорил, очень давно не занимался этими вопросами, но, кажется ничего принципиально не изменилось с тех пор. Только вот теперь статьи есть на эту тему. А когда я перестал этим заниматься, таких статей еще не было вовсе... Кажется, ничего плохого я сам не наговорил, по сравнению с этими статьями. Хотя, если бы знал, что они существуют, вообще ничего говорить не стал бы... Есть еще некоторые интересные воспоминания личного характера на эту тему. Может быть, расскажу, при случае... |
|
|
| номер сообщения: 54-15-2189 |
|
|
|
|
Edwards: Я тут нагуглил неплохую статью.
Кажется, по крайней мере, в качестве шахкомпьютерного ликбеза она вполне интересна - Алгоритмы шахматных программ |
В частности, там даётся более или менее внятное (хотя, по-моему, и несколько косноязычное  ) пояснение такой, судя по всему, важной эвристики как Null move. |
|
|
| номер сообщения: 54-15-2190 |
|
|
|
|
| Sad_Donkey: Есть еще некоторые интересные воспоминания личного характера на эту тему. Может быть, расскажу, при случае... |
Вы рассказывайте, Сэд. Интересно!
"Случай" - есть! Он называется - форум ChessPro
Как говорится - нет повода не выпить (не рассказать) Не сочтите, пожалуйста, за амикошонство, за вульгарность... |
|
|
| номер сообщения: 54-15-2191 |
|
|
|
|
Edwards: | Sad_Donkey: Есть еще некоторые интересные воспоминания личного характера на эту тему. Может быть, расскажу, при случае... |
Вы рассказывайте, Сэд. Интересно!
"Случай" - есть! Он называется - форум ChessPro
Как говорится - нет повода не выпить (не рассказать) Не сочтите, пожалуйста, за амикошонство, за вульгарность... |
Да, все нормально. Спасибо.
Сейчас "вывалю" все, что задержалось в памяти. Простите, если что-то повторю...
Ботвинник.
В начале 60-х он выступал на заседании Московского математического общества. Я учился на мех-мате, интересовался шахматами и, конечно, такого пропустить не мог. "Привел" на заседание М.М. его друг - Михаил Романович Шура-Бура, известный специалист в области выч. техники. Надо понимать, что времена были совсем другие. Культура и, тем более, массовая культура, связанная с компьютерами, программированием и выч. техникой, вообще, только зарождалась. Не было культуры программирования на языках высокого уровня, да и сами языки были "не очень"; не было многих последующих достижений в области теоретического программирования. Я тогда "в этом деле" не понимал ничего... М.М. рассказал об идее создать шахматную программу, которая моделирует мышление шахматиста во время игры. Ему казалось, что это не трудно. На примере своих партий из матча с М.Талем он объяснил, что шахматист во время игры рассчитывает на очень мало ходов. Все остальное - "общие соображения". Он не понимал, что все дело в этих "общих соображениях". И что моделировать "мышление шахматиста" (то есть человека) - задача гораздо более сложная, чем создание программы, играющей в шахматы. И поэтому решать задачу этого моделирования для создания шахматной программы как-то "не очень". Анализируя гораздо позже то, что говорил М.М., я прихожу к выводу, что он, на тот момент, в программировании не понимал ровным счетом ничего. Это его никак не порочит. В его тогдашнем возрасте осваивать "с нуля" новую не только для него сложную область весьма интеллектуальной научно-технической деятельности - дело невероятно трудное. Он в этом потом, конечно, преуспел, но базовых знаний, как я понимаю, ему никогда не хватало. Мне приходилось и позже встречаться с М.М. и немного общаться на эту тему. Приходилось общаться и с создателями "Каиссы".
Сейчас уже поздно. Я могу продолжить несколько погодя (?) |
|
|
| номер сообщения: 54-15-2192 |
|
|
|
|
Edwards: Я тут нагуглил неплохую статью.
Кажется, по крайней мере, в качестве шахкомпьютерного ликбеза она вполне интересна - Алгоритмы шахматных программ |
о, спасибо) информативно) |
|
|
| номер сообщения: 54-15-2193 |
|
|
|
|
....
После окончания мех-мата я стал работать программистом в ИТМиВТ (Институт Точной Механики и Вычислительный Техники), который в то время возлавлял академик Сергей Алексеевич Лебедев - выдающийся ученый и замечательный человек. В этом институте создавались лучшие отечественные "большие вычислительные машины". Как раз в момент моего поступления, в серию выходили БЭСМ-6 и еще одна машина, более специального назначения. Играл в шахматы, занимался организацией шахмат... Осваивал программирование. А программировали тогда "в кодах"! Программу писали на специальных бланках и ее изображение состояло из последовательности цифр (восьмеричных, в том случае), смысл которых был понятен только автору. И в этих условиях люди писали программы, которые успешно управляли запуском ракет!..
А М.М. продолжал работать над своей шахматной программой ("Пионер"), пытаясь реализовать свою идею. Так продолжалось многие годы. Я следил за успехами М.М. по сообщениям в прессе, а сам интересовался шахматными программами и из других источников. В какой-то момент стало известно, что группа программистов и алгоритмистов, работающих в ИТЭФ (Институт Теоретической и Экспериментальной Физики) тоже стала создавать шахматную программу ("Каисса"). О них и о ней я немного расскажу позже. Что касается М.М., то наши пути пересеклись в стенах ИТМиВТ, лет через пятнадцать после того упомянутого заседания Московского Математического Общества. М.М. тогда казалось (может быть, так и было, хотя и вряд ли), что ему для завершения работы не хватает вычислительного ресурса - хорошего современного компьютера. Как он говорил мне позже, ему предлагали закончить работу в Германии, обещая создать все условия для этого. Но он, будучи патриотом или по другим причинам, непременно хотел продолжить и завершить работу в Союзе. Поэтому он стал искать места, где производят лучшую отечественную вычислительную технику и, с неизбежностью, обратил свое внимание на ИТМиВТ, который в то время уже возглавлял В.С.Бурцев (человек тоже очень известный, особенно в определенных кругах; но совсем другой, во многих отношениях, по сравнению с С.А.Лебедевым). Они, М.М. и В.С. договорились о выступлении М.М. на методологическом семинаре в ИТМиВТ. Конечно, и как шахматист, и как программист, я не мог не принять участия в этом мероприятии, тем более, что меня попросили помочь в его организации.
И вот, в день назначенный, в обостылевших казенных стенах Института появился Шахматный Бог. Для меня - рядового шахматиста, как и для многочисленных любителей шахмат нашего института, это было чудом!.. Но у М.М. были сосем другие интересы, связанные с этим визитом. Хотя он, конечно, понимал, что ему не избежать разговора о шахматах, вообще, о матчах Карпова с Корчным. И привычно смирялся с этой перспективой... Продолжу |
|
|
| номер сообщения: 54-15-2194 |
|
|
|
|
Sad_Donkey: ....
А программировали тогда "в кодах"! Программу писали на специальных бланках и ее изображение состояло из последовательности цифр (восьмеричных, в том случае), смысл которых был понятен только автору. |
?
Вы говорите о кодах операций? |
|
|
| номер сообщения: 54-15-2195 |
|
|
|
|
LB: Sad_Donkey: ....
А программировали тогда "в кодах"! Программу писали на специальных бланках и ее изображение состояло из последовательности цифр (восьмеричных, в том случае), смысл которых был понятен только автору. |
?
Вы говорите о кодах операций? |
"В кодах", означает в цифровых кодах. Программа, при этом, состоит из последовательности инструкций ("команд"), которые изображаются набором цифр. Какова структура команд зависит от "системы команд", которая разрабатывается совместно с оборудованием, которое должно эти команды выполнять. В то время у компьютеров была фиксированная длина команды. Код команды (в нашем случае) состоял из пятнадцати восьмеричных цифр, первые три из которых были "кодом операции", следующие две - "адресом модификатора" (тоже "код"), а еще две пятерки цифр были, соответственно, кодом первого и второго адреса.
Например, для того, чтобы написать команду сложения двух чисел, которые находятся в памяти в адресах 10000 и 10001 надо было написать команду:
201 00 10000 10001.
А для того, чтобы результат операции запомнился в адресе 10000, команду:
301 00 10000 10001.
Из этого можно предположить (так и было), что в коде операции третий двоичный разряд был признаком записи результата операции по первому адресу.
Простите - ностальжи... |
|
|
| номер сообщения: 54-15-2196 |
|
|
|
|
Спасибо, Сэд.
У Вас хорошая память. Я начинал уже с ассемблера (с символьными обозначениями команд)
Несколько документальных кадров.
Текст:
За ПОСЛЕДНИЕ годы в печати появлялись отдельные высказывания доктора технических наук
гроссмейстера М. М. Ботвинника по вопросу программирования шахматной игры. Первые результаты его работы в этой области изложены в статье «Математическое отображение шахматной игры». В связи с предстоящим обсуждением в Центральном шахматном клубе статья публикуется предварительно, чтобы все желающие принять участие в дискуссии могли ознакомиться с предложениями М. М. Ботвинника, проверить их на различных примерах и высказать свое мнение по этому важному и интересному вопросу. |
|
|
| номер сообщения: 54-15-2197 |
|
|
|
|
Edwards: saluki: важно решить, с какого уровня расхождения оценки мы "перестаем смотреть" - мы же можем решить, что +1 достаточно, а можем и +0.1 удовлетворится.
|
Ну, нет, насколько я понимаю, тут решать нечего.
Если есть некий предел расчёта (он более или менее предопределяется имеющимся временем).
Обратимся к примеру Мустица. Пусть при 1.h3 g6 мы получили не +0.50, а все +4.99.
Тем не менее, это всё равно меньше, чем +5.00, полученные нами при расчёте 1.Bxh7+.
Таким образом, никакого смысла в том, чтобы смотреть остальные (помимо 1...g6) ответы на 1.h3 - нет. Нет, ибо и так уже ясно, что белые в варианте 1.h3 при данной глубине расчёта не получат ничего более, чем +4.99.
Тут всё очень жёстко.
Варианты возникают только, если та глубина, на которой мы получили +5.00 (и +4.99) - для нас не предельна.
|
Не совсем понял, Эдврадс, почем тут глубина счёта? Если после 1.h3 g6 оценка +4.99, то ясно, что в ответ они сыграют что-то другое, а не 1...g6, и оценка этого другого будет, скорее всего, меньше. При такой большой оценке +5.00 ходу 1.Bxh7+ глубина счёта не имеет значения, ибо того попросту прекращаем (за исключением, может быть, проверки на форсированную матовую атаку королю черных).
saluki:
во-2, мы можем определить что этот параметр "плавает" и зависит от числа фигур на доске, открытых линий, наличия коней в центре или на краю доски и так далее, далее, далее.
|
Насколько понял saluki, плавать может тот самый порог расхождения оценки, за которым "перестаем смотреть" ходы, чья оценка опускается ниже этого критического расхождения с текущим лучшим ходом. Скажем, в миттельшпиле порог этот может быть +1, а в эндшпиле +2 из-за бОльшей критичности ходов в эндшпиле, то бишь даже ходы, якобы слабее, чем на +1, неплохо посмотреть, дабы не зевнуть непоправимо чего-то. |
|
|
| номер сообщения: 54-15-2198 |
|
|
|
|
Хайдук:
Не совсем понял, Эдврадс, почем тут глубина счёта? Если после 1.h3 g6 оценка +4.99, то ясно, что в ответ они сыграют что-то другое, а не 1...g6, и оценка этого другого будет, скорее всего, меньше. |
Ну, почитайте первоначальную цитату из Мустица про альфа-бета отсечение, всё поймёте, наверное.
Разъяснение Мустица об альфа-бета алгоритме Вам понятно?
Я всего лишь продолжал мысль Мустица, не более.
Хайдук:
При такой большой оценке +5.00 ходу 1.Bxh7+ глубина счёта не имеет значения, ибо того попросту прекращаем (за исключением, может быть, проверки на форсированную матовую атаку королю черных). |
Нет, это всё совсем не так (насколько я понимаю).
Во-первых, число "+5.00" сугубо иллюстративное, его можно заменить хоть на "0.00" (и, соответственно, заменить нужным образом другие цифры), от этого смысл пояснения Мустица не поменяется.
Во-вторых, конечно же, прога ни в коем случае не должна прекращать перебор, получив где-то "+5.00" (за исключением случая, когда она предельно ограничена во времени, когда ей необходимо принимать решение немедленно).
Не должна, ибо всегда может обнаружить "+10.00" в другой ветке (понимание чего Вы обнаружили, написав про "проверку на мат").
Вообще мы с Вами тут, по-моему, утратили контакт, Хайдук, утратили взаимно-однозначное понимание контекста наших с Вами рассуждений.
Ещё раз - я всего лишь крутился вокруг описания альфы-беты Мустицем (Вы же, видимо, воспарили в какие-то иные сферы).
Если у Вас нет претензий к описанию Мустица, то не должно быть таковых и к моим словам.
Хайдук:
Насколько понял saluki, плавать может тот самый порог расхождения оценки, за которым "перестаем смотреть" ходы, чья оценка опускается ниже этого критического расхождения с текущим лучшим ходом. Скажем, в миттельшпиле порог этот может быть +1, а в эндшпиле +2 из-за бОльшей критичности ходов в эндшпиле, то бишь даже ходы, якобы слабее, чем на +1, неплохо посмотреть, дабы не зевнуть непоправимо что-то. |
Дело в том, что для меня пока неясно, существует ли вообще в современных программах сам феномен такого порога, при котором якобы можно бросить какие-то варианты на пол-дороге.
В частности, альфа-бета алгоритм - ни в каких тонко настраиваемых порогах не нуждается, альфа-бета - это простое отсечение, очень грубо и ясно математически обоснованное. Отсекаемые альфа-бетой ветки просто-напросто теоретически не могли бы стать первой линией программы (если б она даже захотела их посчитать полностью), поэтому они ей и не интересны.
С другой стороны, возможно, некоторые варианты и отбрасываются на пол-дороге. И если такой алгоритм отсечения действительно реализован, то да, становятся актуальными Ваши и Салюки рассуждения о его настройке. Но, повторюсь, для меня пока не очевидно, что такой алгоритм реализован. Я тут не до конца ещё разобрался. |
|
|
| номер сообщения: 54-15-2199 |
|
|
|
|
Edwards: Дело в том, что для меня пока неясно, существует ли вообще в современных программах сам феномен такого порога, при котором якобы можно бросить какие-то варианты на пол-дороге.
В частности, альфа-бета алгоритм - ни в каких тонко настраиваемых порогах не нуждается, альфа-бета - это простое отсечение, очень грубо и ясно математически обоснованное. Отсекаемые альфа-бетой ветки просто-напросто теоретически не могли бы стать первой линией программы (если б она даже захотела их посчитать полностью), поэтому они ей и не интересны. |
то, что я пытался "угадать", на практике выглядит таким образом:
| (8) Единственный ответ (singular extension). Стандартная альфа-бета прекращает анализ позиции, как только найден ход, который вызовет отсечение. Так как у нас не полное дерево игры, а мы используем оценочную функцию, может оказаться, что мы проврались, и никакого отсечения нет. Соответственно, мы думали, что в этой позиции у нас лучше, а на самом деле мы теряем ферзя. Идея единственного ответа состоит в том, что найдя один хороший ответ, мы не отсекаем сразу всё поддерево, а продолжаем перебор, пока не найдём второй хороший ход. Если же мы его не нашли, то позиция анализируется заново, на сей раз на глубину N+1. Очень помогает в тактических позициях - программа начинает видеть комбинации на несколько ходов раньше, но резко замедляет перебор и поэтому используется только программами, работающими на суперкомпьютерах. |
ну с поправкой на время написания статьи (лет 12 назад, по ощущению), сейчас я думаю она везде реализована. |
|
|
| номер сообщения: 54-15-2200 |
|
|
|
|
| На основании высказываемых мнений у меня складывается впечатление, что Ботвинник был как-бы самодуром, мало в чем, кроме традиционных (некомпьютерных) шахмат, смыслящим |
|
|
| номер сообщения: 54-15-2201 |
|
|
|
|
| Хайдук: На основании высказываемых мнений у меня складывается впечатление, что Ботвинник был как-бы самодуром, мало в чем, кроме традиционных (некомпьютерных) шахмат, смыслящим |
Ув. Хайдук, Вы имеете представление о вычислительной технике и программировании 60-70-х годов?
Только во второй половине 70-х появились ЕС ЭВМ, которые имели 32-разрядную архитектуру с 24-разрядной шиной адреса, что позволяло адресовать максимум 16 мегабайт физической оперативной памяти. 16мб ОЗУ - физический предел. Быстродействие (сейчас не помню цифр) - соответствующее.
Я несколько лет программировал для ЕС-1022 с ОЗУ 256 Кбайт. Умение экономить память и машинное время определяло уровень программиста.
В таких условиях было совершенно естественно искать пути программирования шахмат альтернативные 'стратегиям' Шеннона.
И я думаю, что к поиску альтернативных стратегий, начатому Ботвинником и психологами-эвристиками, наука в скором времени вернется. |
|
|
| номер сообщения: 54-15-2202 |
|
|
|
|
Edwards: Хайдук:
Не совсем понял, Эдврадс, почем тут глубина счёта? Если после 1.h3 g6 оценка +4.99, то ясно, что в ответ они сыграют что-то другое, а не 1...g6, и оценка этого другого будет, скорее всего, меньше. |
Ну, почитайте первоначальную цитату из Мустица про альфа-бета отсечение, всё поймёте, наверное.
Разъяснение Мустица об альфа-бета алгоритме Вам понятно?
Я всего лишь продолжал мысль Мустица, не более.
|
Неплохо бы показать эти отсечения на конкретной позиции. Тогда будет понятнее. |
|
|
| номер сообщения: 54-15-2203 |
|
|
|
|
Edwards: Меня тут на недружественном ресурсе просветили немного:
Mustitz:
Используется альфа-бета отсечения. Общий смысл примерно такое:
белые ходят 1. Bxh7+ им выигрывают ладью (оценка +5)
белые ходят 1. h3 черные отвечают 1... g6 и получается оценка (+0.5).
В этом случае происходит отсечение ненужных веток, и остальные ответы черных на ход 1. h3 не рассматриваются. Да, допустим что черные в варианте 1. h3 Qxg2# матуют (т. е. оценка может быть насколько угодно меньше +0.5). Но все равно это лишняя работа, потому что оценку исходной позиции (минимум +5) это не изменит. |
Действительно считать совсем уж всё - не обязательно, конечно, теперь это для меня очевидно.
С другой стороны, это альфа-бета отсечение на первый взгляд смотрится сугубо, что ли, технической процедурой, абсолютно рациональной, не связанной с какими-то хитростями. |
Эдвардс, неясно почему тебе вроде все ясно с альфа-бетой Мустица  . Отсечение и отказ от просмотра вариантов происходит из-за большой разницы в оценках, но этим оценкам нельзя доверять на 100%, потому что они эвристические, а компы намного слабее гроссов в эвристике. Если разница в оценках небольшая, то нужно считать дальше, ибо эвристикой можно зевнуть что-то важное. Потому и считают ФСЁ на большую глубину/горизонт, дабы отодвинуть ненадёжную оценку эвристикой на этот горизонт, что обеспечивает время поправить плохую оценку. Подходя к прежнему горизонту, комп углубляет счёт за этим горизонтом и тем самым может заметить ошибки, сделанные эвристическим оцениванием в своё время, когда оборвал счет на прежнем горизонте. Компы зевают оценкой, но зевают далеко впереди (на горизонте счёта) от текущего хода и потому такие зевки почти не сказываются на текущем ходе - тот обычно такой, что оставляет возможность исправить зевки на старом горизонте, когда тот поглотится счётом до дальнейшего горизонта. |
|
|
| номер сообщения: 54-15-2205 |
|
|
|
|
Хайдук:
Эдвардс, неясно почему тебе вроде все ясно с альфа-бетой Мустица . Отсечение и отказ от просмотра вариантов происходит из-за большой разницы в оценках, но этим оценкам нельзя доверять на 100%, потому что они эвристические, а компы намного слабее гроссов в эвристике. Если разница в оценках небольшая, то нужно считать дальше, ибо эвристикой можно зевнуть что-то важное. Потому и считают ФСЁ на большую глубину/горизонт, дабы отодвинуть ненадёжную оценку эвристикой на этот горизонт... |
Хайдук, все рассуждения об альфа-бете подразумевали то, что программой уже достигнута предельная глубина перебора. Т.е. максимальная глубина, которую она может себе позволить в данных конкретных обстоятельствах (например, в обстоятельствах турнирной партии с, естественно, ограниченным контролем времени).
В этом случае Ваши рассуждения теряют смысл, надеюсь, это понятно. |
|
|
| номер сообщения: 54-15-2206 |
|
|
|
|
Edwards: Хайдук, все рассуждения об альфа-бете подразумевали то, что программой уже достигнута предельная глубина перебора. Т.е. максимальная глубина, которую она может себе позволить в данных конкретных обстоятельствах (например, в обстоятельствах турнирной партии с, естественно, ограниченным контролем времени).
В этом случае Ваши рассуждения теряют смысл, надеюсь, это понятно. |
Я бы не сказал, что вполне теряют, ибо на предельной глубине можно отсечь ходы с очень ниской оценкой и в дальнейшем, когда предельная глубина оставит эти ходы позади, даже тогда их не рассматривать. Такое чревато, хотя вероятность зевков небольшая, если ОФ хорошая и надёжная. |
|
|
| номер сообщения: 54-15-2207 |
|
|
|
|
| Мне кажется, Вы всё-таки просто не поняли смысла алгоритма альфа-бета отсечения, Хайдук. |
|
|
| номер сообщения: 54-15-2208 |
|
|
|
|
Самое интересное, по-моему, это эвристическая оценка позиции. Что скрывается под этой эвристикой? Неужели, примитивный балльно-индексный аппарат позволяет давать довольно точные оценки непростым положениям? Ведь должны существовать очень строгие цепочки приоритетов. Но при этом разных исключений из общих правил - пруд пруди. Однако, машина все-таки как-то оценивает позицию, учитывая и соотношение материала, и расположение фигур, и состояние пешечных цепей, и динамику...
Зная систему приоритетов у машины, шахматист сможет более успешно играть с железным другом, выбирая позиции, которые являются исключением из общих правил.
__________________________
Спасение там, где опасность. |
|
|
| номер сообщения: 54-15-2209 |
|
|
|
|
| Edwards: Мне кажется, Вы всё-таки просто не поняли смысла алгоритма альфа-бета отсечения, Хайдук. |
И в чем состоит этот смысл, чего конкретно не понял?  |
|
|
| номер сообщения: 54-15-2210 |
|
|
|
|
Edwards: Я тут нагуглил неплохую статью.
Кажется, по крайней мере, в качестве шахкомпьютерного ликбеза она вполне интересна - Алгоритмы шахматных программ |
Любопытно, что в разделе "Улучшения" не приведена следующая идея, которая мне кажется довольно разумной (хотя, конечно, уже давно может быть известно, что это бред).
У каждой позиции есть оценки нескольких уровней. Оценка нулевого уровня дается оценочной функцией. Оценка третьего уровня - перебором на три полухода, оценкой конечных позиций с помощью ОФ и минимаксом. Поскольку перебор и так уже делается итеративно, появляется нехитрая идея: останавливать перебор на некотором уровне, если оценка позиции на этом уровне и, скажем, на паре предыдущих, приблизительно одинакова.
Идеальная ОФ, кстати, должна выдавать одинаковые оценки, независимо от уровня. Так что это еще и способ отладки ОФ. |
|
|
| номер сообщения: 54-15-2211 |
|
|
|
|
Хайдук: | Edwards: Мне кажется, Вы всё-таки просто не поняли смысла алгоритма альфа-бета отсечения, Хайдук. |
И в чем состоит этот смысл, чего конкретно не понял? |
Я не знаю, чего конкретно Вы не поняли, ув. Хайдук :(
Мне просто представляется, что все Ваши рассуждения с альфа-бетой никак не соотносятся.
Зато, возможно, соотносятся с чем-то другим - и притом более интересным.
Кстати, ещё одну из нестрогих, но информативных интерпретаций альфа-беты мне подкинули более компетентные люди:
Skipper_NORTON:
перебор с альфа-бета отсечениями - аналогичен перебору всех позиций |
|
|
|
| номер сообщения: 54-15-2212 |
|
|
|
|
saluki:
то, что я пытался "угадать", на практике выглядит таким образом:
| (8) Единственный ответ (singular extension). Стандартная альфа-бета прекращает анализ позиции, как только найден ход, который вызовет отсечение. Так как у нас не полное дерево игры, а мы используем оценочную функцию, может оказаться, что мы проврались, и никакого отсечения нет. Соответственно, мы думали, что в этой позиции у нас лучше, а на самом деле мы теряем ферзя. Идея единственного ответа состоит в том, что найдя один хороший ответ, мы не отсекаем сразу всё поддерево, а продолжаем перебор, пока не найдём второй хороший ход. Если же мы его не нашли, то позиция анализируется заново, на сей раз на глубину N+1. Очень помогает в тактических позициях - программа начинает видеть комбинации на несколько ходов раньше, но резко замедляет перебор и поэтому используется только программами, работающими на суперкомпьютерах. |
|
saluki, по-моему, Вы не правы.
Этот "singular extension" - это, насколько я понял, нечто подобное идее "Форсированного варианта" (ФВ).
Если почитать приведённую Вами цитату, то вроде бы становится ясным, что в "singular extension" речь идёт о борьбе против лишних отсечений. А не о борьбе за увеличение отсечений.
Т.е. это - совсем не то, что Вы пытались "угадать". А ровно обратное.
Я писал об этом так:
Edwards:
Некоторые варианты программа должна считать глубже, чем остальные, а вот стремление считать некоторые варианты "мельче", чем остальные мне представляется не столь перспективным. |
"Singular extension" - это и есть стремление "считать некоторые варианты глубже, чем остальные". Насколько я понимаю.
А Вы "пытались угадать" так:
saluki:
по моей логике "оптимизация перебора" эквивалентна тому, что бы считать меньше позиций, т.е. некоторым позициям ставить оценку "хуже чем другие варианты" a priori. |
Я полагаю, что Вы всё же угадали.
Но Ваш успех связан не с "singular extension", а скорее с "null move". И, может быть, ещё с чем-нибудь. |
|
|
| номер сообщения: 54-15-2213 |
|
|
| |
|
|
|
|
|
|
|
| Copyright chesspro.ru 2004-2024 гг. |
|
|
|
