Comments 45
По теореме Цермело…
Не надо так пугать. Этот факт легко доказывается без аксиомы выбора, поскольку количество возможных позиций конечно.
Да, действительно. Я по невежеству знал только одну теорему Цермело. А та теорема из теории игр довольно тривиальна, я просто не знал, что она имеет название.
По-моему, эксперимент в значительной степени некорректен. Одна и та же партия делает кумулятивный вклад в результат: после того, как равновесие было существенно нарушено (скажем, на полторы-две пешки), в подавляющем большинстве случаев процесс развивается дальше лавинообразно — разрыв увеличивается, а в данном эксперименте после этого еще несколько раз снимаются результаты, даже тогда, когда ежу понятно, что партия проиграна. Это объясняет завышенную оценку ферзя для компьютерных партий и заниженную для гроссмейстеров. Действительно, если играть до мата, как это делают компьютеры, то лишь небольшая часть выигранных эндшпилей завершается без того чтобы превращать пешки в ферзей(*), в то время как гроссмейстеры обычно сдают такие партии до превращений.
Я предлагаю изменить условия эксперимента следующим образом: для каждой партии измерять оценку ровно один раз, скажем, на 15-м ходу. При этом можно даже не искать фазу успокоения; можно предположить, что шум, вносимый разменами, меньше полезного сигнала. Правда, здесь тоже нюанс: если варьировать номер хода, когда происходит измерение, то, с одной стороны, получим сильно зависящую от этого параметра оценку ладьи (ее сила очень чувствительна к общему количеству фигур на доске), а с другой — вроде бы нельзя усреднять по номеру хода (вроде бы из-за того, что нет аддитивности), иначе свалимся в первоначальный эксперимент.
* NB: эта фраза показывает, что в русском языке «ферзь» — одушевленное существительное, «пешка» — почему-то нет.
Я предлагаю изменить условия эксперимента следующим образом: для каждой партии измерять оценку ровно один раз, скажем, на 15-м ходу. При этом можно даже не искать фазу успокоения; можно предположить, что шум, вносимый разменами, меньше полезного сигнала. Правда, здесь тоже нюанс: если варьировать номер хода, когда происходит измерение, то, с одной стороны, получим сильно зависящую от этого параметра оценку ладьи (ее сила очень чувствительна к общему количеству фигур на доске), а с другой — вроде бы нельзя усреднять по номеру хода (вроде бы из-за того, что нет аддитивности), иначе свалимся в первоначальный эксперимент.
* NB: эта фраза показывает, что в русском языке «ферзь» — одушевленное существительное, «пешка» — почему-то нет.
Спасибо, идея с одним измерением за партию интересная. Можно ещё выбирать то сочетание фигур, которое дольше всего за партию находилось на доске. Попробую поэкспериментировать с разными вариантами отбора позиций…
А используемый софт легко будет переиспользовать? Хочу проверить одну идею насчет оценки позиций (примерно тот же эксперимент поставить), но критерий оценки нестандартный, сейчас даже сходу затрудняюсь описать его.
В принципе, код достаточно простой, написан в стиле «C++ как улучшенный C». Попробуйте скачать и поразбираться — начать лучше всего с класса Position. Если возникнут вопросы, всегда готов ответить, пишите тогда в личную переписку…
Я осознал, что нужно что-то другое. Я хочу странного, а именно — найти простой признак, отличающий «ясные» позиции от «неясных». Формально говоря, ясность позиции — это дисперсия результата партии, если много раз сыграть эту позицию сильными движками. То есть, если результат почти всегда один и тот же, то позиция объявляется ясной. Я хочу найти простой, то есть вычислительно дешевый, способ оценки ясности. Например, кажется верным следующее утверждение: если материальная оценка сильно смещена от нуля (скажем, на 2 пешки и более), то позиция скорее всего ясная.
«Пешка» — тоже одушевлённое. Ср. винительный падеж для одушевлённых и неодушевлённых.
Обалденная статья! Огромная работа проделана и очень наглядно и интересно представлена. Спасибо большое!
Мне кажется, что в ваше исследование вносят искажение «личности игроков».
Я бы предложил провести серию партий какого-либо движка самого с собой с измененными начальными условиями. Т.е., например, у одной стороны в самом начале забираем слона, у другой три пешки играем 100 партий с переменой черное-белое и смотрим на статистику.
Я бы предложил провести серию партий какого-либо движка самого с собой с измененными начальными условиями. Т.е., например, у одной стороны в самом начале забираем слона, у другой три пешки играем 100 партий с переменой черное-белое и смотрим на статистику.
Интересное предложение, но тут маленькая техническая трудность: надо где-то взять 100 (а лучше 1000, можно и больше) стартовых позиций с таким соотношением материала. Потому что движок у меня детерминированный, он будет одни и те же ходы повторять. Впрочем, это всё решаемо, конечно же.
Хммм. А если стартовые позиции выбирать из вашей базы, а выигрышность оценивать не по актуальному результату исторической партии, а дать доиграть партию программе за обе стороны. Потом повторить с инверсией цветов.
Тогда можно будет исключить из рассмотрения влияние персоналий игроков. Плюс добавить новый фактор — право первого хода.
Тогда можно будет исключить из рассмотрения влияние персоналий игроков. Плюс добавить новый фактор — право первого хода.
Очевидный недостаток такого подхода в том, что полностью игнорируется позиционная составляющая оценки. Чтобы понять это, достаточно рассмотреть два тривиальных случая:
В первом случае, исход партии практически полностью определяется тем, успеет ли пешка добежать до поля превращения, то есть позицией. Во втором — вероятность выигрыша вроде бы должна быть больше 2 * N > P! Но всем известно, что мат двумя конями одинокому королю поставить нельзя.
- Король + Пешка против Короля
- Король + 2 Коня против Короля
В первом случае, исход партии практически полностью определяется тем, успеет ли пешка добежать до поля превращения, то есть позицией. Во втором — вероятность выигрыша вроде бы должна быть больше 2 * N > P! Но всем известно, что мат двумя конями одинокому королю поставить нельзя.
Естественно, материальная оценка не претендует на абсолютную точность. Я об этом упомянул в статье — это всего лишь первое приближение, и оно работает только в вероятностном смысле:
«Пусть мы видим случайно выбранную позицию, в которой у белых перевес в 2 пешки (ΔM = 2). С вероятностью, близкой к 80%, мы можем утверждать: партия закончится победой белых.»
Более того, никакая статическая оценка в шахматах не будет правильно оценивать все позиции — без процедуры поиска никак не обойтись.
«Пусть мы видим случайно выбранную позицию, в которой у белых перевес в 2 пешки (ΔM = 2). С вероятностью, близкой к 80%, мы можем утверждать: партия закончится победой белых.»
Более того, никакая статическая оценка в шахматах не будет правильно оценивать все позиции — без процедуры поиска никак не обойтись.
> Во втором — вероятность выигрыша вроде бы должна быть больше 2 * N > P! Но всем известно, что мат двумя конями одинокому королю поставить нельзя.
Если усреднять не по позициям типа «король и два коня против короля», а по всем позициям, где у белых два лишних коня, вероятность победы будет близка к 100%. Например, «король, два коня и три пешки против короля и трёх пешек», или «король, два коня и ладья против короля и ладьи». Смысл подсчёта баланса — именно в этом.
Если усреднять не по позициям типа «король и два коня против короля», а по всем позициям, где у белых два лишних коня, вероятность победы будет близка к 100%. Например, «король, два коня и три пешки против короля и трёх пешек», или «король, два коня и ладья против короля и ладьи». Смысл подсчёта баланса — именно в этом.
Не пробовали ли вы квадратичную модель, как в StockFish? Будет ли она заметно лучше?
Пока не пробовал. Теоретически, конечно, она может быть лучше, но потребуется большее количество данных для обучения, и количество коэффициентов сразу резко возрастает — вместо пяти весов фигур надо будет рассматривать 10x10 = 100 коэффициентов (включая линейные и перекрёстные члены в квадратичной форме).
Мне кажется более интересным подход, который был реализован в Рыбке — большая таблица со статистикой для всех возможных соотношений материала. Она занимает несколько мегабайтов, и даёт усиление игры до 50 пунктов Эло, если я правильно помню.
Мне кажется более интересным подход, который был реализован в Рыбке — большая таблица со статистикой для всех возможных соотношений материала. Она занимает несколько мегабайтов, и даёт усиление игры до 50 пунктов Эло, если я правильно помню.
Высокая стоимость фигур у Андерсена объясняется тем, что они у него сугубо атакующе-жертвенный материал, позволяющий эффектно выигрывать у соперников 19 века (не разбирающихся в современных позиционных методах игры, с помощью которых гусарские наскоки убиваются в зародыше). Поиграй бы Андерсен в своём стиле против нынешних топовых гроссов, не факт чтобы ему удалось выиграть против них хотя бы одну партию (ну, разве что, изредка в блиц).
Тот же Таль одними фигурами не комбинировал. То, что он чаще жертвовал коней-слонов-ладей-ферзей, чем пешки, ещё не означает, что его атаки не учитывают собственный пехотный материал.
Думаю, если бы Вы протестировали партии другого гения эффектных комбинаций позапрошлого столетия — Пола Морфи — то у него бы показатели были такие же, как и у современных шахматистов. Потому что картинным жертвам предшествовал позиционный перевес, которого не достичь без помощи пешек.
Тот же Таль одними фигурами не комбинировал. То, что он чаще жертвовал коней-слонов-ладей-ферзей, чем пешки, ещё не означает, что его атаки не учитывают собственный пехотный материал.
Думаю, если бы Вы протестировали партии другого гения эффектных комбинаций позапрошлого столетия — Пола Морфи — то у него бы показатели были такие же, как и у современных шахматистов. Потому что картинным жертвам предшествовал позиционный перевес, которого не достичь без помощи пешек.
Здорово. Спасибо за труд, было очень интересно почитать.
У меня вопрос.
По поводу «дисперсии результатов партии» и в целом методик компьютерного анализа с опорой на результаты сыгранных партий — существуют многоходовые задачи, которые на данный момент (насколько я знаю) не могут быть решены компьютером. Например, вот задача, где предлагается поставить мат за 21 ход: chessfield.ru/chess-puzzles/filter/131072
Конкретно в данной задаче материальное соотношение равно, но есть и другие, где машина, имея преимущество проиграет человеку, но выиграет у другой машины.
Как быть с подобными позициями (партиями) при анализе и можно ли быть уверенным, что их количество не так велико, чтобы можно было ими пренебречь?
У меня вопрос.
По поводу «дисперсии результатов партии» и в целом методик компьютерного анализа с опорой на результаты сыгранных партий — существуют многоходовые задачи, которые на данный момент (насколько я знаю) не могут быть решены компьютером. Например, вот задача, где предлагается поставить мат за 21 ход: chessfield.ru/chess-puzzles/filter/131072
Конкретно в данной задаче материальное соотношение равно, но есть и другие, где машина, имея преимущество проиграет человеку, но выиграет у другой машины.
Как быть с подобными позициями (партиями) при анализе и можно ли быть уверенным, что их количество не так велико, чтобы можно было ими пренебречь?
Уже не в первом комментарии встречаются рассуждения вида «а вот в такой-то позиции оценка материала будет давать сбой, потому что на самом деле там выигрыш/ничья за белых/чёрных...».
Конечно, всё это так! Шахматы — игра очень конкретная, никакого магического рецепта для оценки позиции нет и быть не может. Только счёт, счёт и счёт. Плюс разумная оценка на листьях :)
СТАТЬЯ — О ДРУГОМ.
Нам известно, что в оценку компьютера всегда входит материал — фигурам присваиваются определённые веса. Присваиваются чаще всего по интуиции или по традиционным меркам. Цель статьи — найти эти веса каким-то более определённым методом, чем «с потолка», дать им некоторое математическое обоснование. НЕ ОТКАЗЫВАЯСЬ ОТ ДРУГИХ ЧЛЕНОВ В ОЦЕНКЕ. А дополняя их.
Конечно, всё это так! Шахматы — игра очень конкретная, никакого магического рецепта для оценки позиции нет и быть не может. Только счёт, счёт и счёт. Плюс разумная оценка на листьях :)
СТАТЬЯ — О ДРУГОМ.
Нам известно, что в оценку компьютера всегда входит материал — фигурам присваиваются определённые веса. Присваиваются чаще всего по интуиции или по традиционным меркам. Цель статьи — найти эти веса каким-то более определённым методом, чем «с потолка», дать им некоторое математическое обоснование. НЕ ОТКАЗЫВАЯСЬ ОТ ДРУГИХ ЧЛЕНОВ В ОЦЕНКЕ. А дополняя их.
Экспериментальный анализ сам по себе штука неоднозначная, поэтому подобные комментарии и встречаются — просто предпосылки и методы вызывают некоторую настороженность и неоднозначность что ли.
Говорить о полной математической обоснованности конечно же не приходится — на безрыбье и конь слон.
Посыл мне понятен — занятно, интересно. И «потолок» теперь немного ниже, но другой :)
Шахматы тем и прекрасны, что к математике их так просто не приручишь (по крайней мере в обозримом будущем).
Был бы рад почитать о ваших дальнейших ходах!
Говорить о полной математической обоснованности конечно же не приходится — на безрыбье и конь слон.
Посыл мне понятен — занятно, интересно. И «потолок» теперь немного ниже, но другой :)
Шахматы тем и прекрасны, что к математике их так просто не приручишь (по крайней мере в обозримом будущем).
Был бы рад почитать о ваших дальнейших ходах!
А какой там план выигрыша в этой задаче? :)
1. g3-g4 (обеспечиваем тропинку для белого короля)
Затем белый король съедает пешку на a5, потом по тропинке a5-a4-a3-a2-b1-c1-d1-e1-f1-g1-h2-g3:f3-e4-d5 вторгается на половину поля чёрных — и что делать дальше? Я там пробовал разные варианты и везде облом…
1. g3-g4 (обеспечиваем тропинку для белого короля)
Затем белый король съедает пешку на a5, потом по тропинке a5-a4-a3-a2-b1-c1-d1-e1-f1-g1-h2-g3:f3-e4-d5 вторгается на половину поля чёрных — и что делать дальше? Я там пробовал разные варианты и везде облом…
Я так понимаю, нужно поставить ферзя (e6-e7-e8Ф, что касается пешки f7, то она жертвуется) и довести чёрных до цуцванга, вынудив королём пойти на h6. Тогда ферзь матует с поля h8. При этом нужен точный порядок ходов — иначе или не укладываемся в 21 ход или даже пат. Как-то так, наверное (у меня пока решить не получилось).
Начало рассуждений верное )
Показать решение?
Показать решение?
Бывает и такое: задача — мат в 64 хода.
Иллюстрация на тему неоднозначности оценки позиции по материальному перевесу.
Ход белых:
Иллюстрация на тему неоднозначности оценки позиции по материальному перевесу.
Ход белых:
Задача — мат в 64 хода
Решение задачи
- 1. Kxc3+ Kb1
- 2. Dxf5+ Ka2
- 3. Df7+ Kb1
- 4. Dh7+ Ka2
- 5. Dxg8+ Kb1
- 6. Dh7+ Ka2
- 7. Df7+ Kb1
- 8. Df5+ Ka2
- 9. Dd5+ Kb1
- 10. Dd3+ Ka2
- 11. Dc4+ Kb1
- 12. Dxf1+ Ka2
- 13. Dc4+ Kb1
- 14. De4+ Ka2
- 15. Dd5+ Kb1
- 16. Dxh1+ Ka2
- 17. Dd5+ Kb1
- 18. Dd3+ Ka2
- 19. Dc4+ Kb1
- 20. Dxa6 Ka2
- 21. De6+ Kb1
- 22. Dc4 c6
- 23. De4+ Ka2
- 24. De6+ Kb1
- 25. Dc4 g2
- 26. De4+ Ka2
- 27. De6+ Kb1
- 28. Dg6+ Ka2
- 29. Dg8+ Kb1
- 30. Dxg2 Ka2
- 31. Dg8+ Kb1
- 32. Dc4 h4
- 33. De4+ Ka2
- 34. De6+ Kb1
- 35. Dc4 h5
- 36. De4+ Ka2
- 37. De6+ Kb1
- 38. Dc4 h3
- 39. De4+ Ka2
- 40. De6+ Kb1
- 41. Dxh3 Ka2
- 42. De6+ Kb1
- 43. Dc4 h4
- 44. De4+ Ka2
- 45. De6+ Kb1
- 46. Dc4 h3
- 47. De4+ Ka2
- 48. De6+ Kb1
- 49. Dxh3 Ka2
- 50. De6+ Kb1
- 51. Dc4 c5
- 52. De4+ Ka2
- 53. De6+ c4
- 54. Dxc4+ Kb1
- 55. De4+ Ka2
- 56. De6+ Kb1
- 57. Dc4 f1=D
- 58. Dxf1+ Ka2
- 59. Df7+ Kb1
- 60. Dc4 e2
- 61. Dxe2 Ka2
- 62. De6+ Kb1
- 63. Dc4 ~
- 64. Df1#
По моему на 20 ходу черные ставят ферзя вместо отступления и будет ничья.
Полагаю, что нарушение последовательности, наоборот, может лишь приблизить мат.
Суть — используя характерный прием с последовательностью шахов и ключевое поле с4, вынуждать черных отдавать одну за другой фигуры в цикле до возникновения цугцванга, после которого и следует неизбежный мат. Если черные проведут ферзя, то белые его съедят и мясорубка продолжит работать дальше по тому же принципу.
Суть — используя характерный прием с последовательностью шахов и ключевое поле с4, вынуждать черных отдавать одну за другой фигуры в цикле до возникновения цугцванга, после которого и следует неизбежный мат. Если черные проведут ферзя, то белые его съедят и мясорубка продолжит работать дальше по тому же принципу.
Нет, принцип будет нарушен. После постановки ферзя на 20-м ходу его нельзя съесть этим же принципом, и уже нельзя получить цунгцванг для мата. Поставте позицию к 20му ходу, и вместо хода королем поставте ферзя и попробуйте его забрать после этого на любом ходу.
Давайте разберем, я не против. На 20-ом ходу после взятия черной ладьи получаем данную позицию.
В случае хода черных на f1 с проведением пешки в ферзи, белые тут же съедают оного на 21-ом ходу с шахом, вынуждая черного короля пойти на a2, после чего продолжается та же самая свистопляска с шахами и постановкой белого ферзя на c4 при черном короле на b1, вынуждая черных точно так же продолжать отдавать фигуры (ходить пешками) вплоть до последнего цугцванга, когда фигур для «отсрочки мата» уже не останется.
В случае хода черных на f1 с проведением пешки в ферзи, белые тут же съедают оного на 21-ом ходу с шахом, вынуждая черного короля пойти на a2, после чего продолжается та же самая свистопляска с шахами и постановкой белого ферзя на c4 при черном короле на b1, вынуждая черных точно так же продолжать отдавать фигуры (ходить пешками) вплоть до последнего цугцванга, когда фигур для «отсрочки мата» уже не останется.
Отличная статья, респект.
Можно немного отвлеченный вопрос?
Если в основном шахматные движки анализируют конкретную позицию на каждом ходу, есть ли программы, которые пытаются смотреть динамику?
Каждый человеческий игрок обладает индивидуальностью, сказывающейся на манере игры. Для известных гроссмейстеров есть записи партий.
Может ли программа выявлять учитывать какие-то индивидуальные склонности соперников, как человеческих, так и машинных?
Или это слишком сложно?
Можно немного отвлеченный вопрос?
Если в основном шахматные движки анализируют конкретную позицию на каждом ходу, есть ли программы, которые пытаются смотреть динамику?
Каждый человеческий игрок обладает индивидуальностью, сказывающейся на манере игры. Для известных гроссмейстеров есть записи партий.
Может ли программа выявлять учитывать какие-то индивидуальные склонности соперников, как человеческих, так и машинных?
Или это слишком сложно?
Думаю, что компьютерам уже поздно учиться у людей, так как они обогнали их в шахматах навсегда — на 600 пунктов Эло и больше. Поэтому вопрос индивидуального стиля в сравнении с людьми не стоит — как не стоит он в игре гроссмейстера с разрядником (более сильный шахматист может выиграть как угодно — хоть в стиле Морфи с лихой атакой, хоть в стиле Карпова с позиционным зажимом).
Персональные стили в основном нужны для развлекательных программ, вроде Чессмастера. Кстати, GreKo тоже участвует в качестве основного движка в одной из таких оболочек: LucasChess.
Вот интересная статья про стили, оценку и поиск, хотя и старинная: http://www.thorstenczub.de/complcss2.html
Персональные стили в основном нужны для развлекательных программ, вроде Чессмастера. Кстати, GreKo тоже участвует в качестве основного движка в одной из таких оболочек: LucasChess.
Вот интересная статья про стили, оценку и поиск, хотя и старинная: http://www.thorstenczub.de/complcss2.html
Программа Deep Thought (предшественница Deep Blue) училась именно на партиях людей. Это был конец 80-х — компьютеры как раз приближались по рейтингу к людям, но ещё им уступали.
Вот статья о том, как настраивали её оценку: www.tim-mann.org/DT_eval_tune.txt
Вот статья о том, как настраивали её оценку: www.tim-mann.org/DT_eval_tune.txt
Хорошая статья. В SmarThink в своё время я пошёл примерно по тому же пути, только модель материала у меня имеет существенно больше параметров. Во-первых, для каждой фигуры есть отдельно миттельшпильная и эндшпильная оценки, а во-вторых добавлены ещё оценки отдельных подмножеств. Хотя, конечно, сейчас уже нужно эту часть переделывать, т.к. решая коммерческие задачи я вместе с коллегами написал большой фреймворк для автоматического построения предиктивных моделей по большим массивам…
Интересно, насколько можно усилить программу исключительно подстройкой параметров? Недавно много обсуждали программу Жираф, там автор использовал машинное обучение не только для оценки, но и для настройки эвристик поиска и сортировки ходов. Правда, программа не очень сильная пока что, где-то 2300-2400.
arxiv.org/pdf/1509.01549v2.pdf
arxiv.org/pdf/1509.01549v2.pdf
Это вопрос, который, наверное, не имеет однозначного ответа, т.к. всё зависит от того, насколько хороша текущая оценочная функция :)
Я веду исследования как раз в этом направлении: тюнинг как оценки, так и некоторых параметров поиска. Думаю, что за этим будущее, но там есть ряд серьёзных сложностей, конечно. Например, я много экспериментировал в попытках сделать более точную модель отсечений — пунктов 30, наверное, я на этом собрал, но там трудно правильно сформулировать целевую функцию, т.к. нужно правильно мерить негативный эффект от ошибки, а это весьма нетривиальная задача.
Я веду исследования как раз в этом направлении: тюнинг как оценки, так и некоторых параметров поиска. Думаю, что за этим будущее, но там есть ряд серьёзных сложностей, конечно. Например, я много экспериментировал в попытках сделать более точную модель отсечений — пунктов 30, наверное, я на этом собрал, но там трудно правильно сформулировать целевую функцию, т.к. нужно правильно мерить негативный эффект от ошибки, а это весьма нетривиальная задача.
Sign up to leave a comment.
Определяем веса шахматных фигур регрессионным анализом