Итак, мы подробно рассмотрели в статье, как работают важнейшие составляющие реальной шахматной программы по отдельности и вместе. Пора подвести некоторые итоги, сделать выводы, и попытаться оценить будущие перспективы.
Итак, мы добрались до самого сердца шахматной программы Стокфиш. Ее основной функции - search. Именно здесь бьется пульс этого движка.
Сейчас мы произведем разбор этой функции. О ее важности уже не раз говорилось на предыдущих страницах. Теперь нам предстоит понять, как основной поиск выглядит в реальной программе. Еще раз напомню, что функцию search можно найти в файле search.cpp. Обзорному описанию содержания этого файла была посвящена предыдущая часть
То, что распределённые сотрудники в IT- и финтех-командах закрывают текущие задачи — вроде бы факт. Но есть проблема, о которой заявляют те, кто перешёл на гибридный или удалённый форматы работы. Распределённые команды теряют связь, потому что перестают быть командой в прямом, человеческом смысле слова.
В этой части мы наконец-то обратимся к коду реальных программ. Примером нам будет служить код поиска шахматной программы Стокфиш. В настоящее время это безусловно сильнейшая шахматная программа в мире.
В этой части мы рассмотрим вторую важную составляющую шахматных программ - оценочную функцию. Долгие годы она находилась в роли "пасынка" для процесса разработки. Но на то существовали объективные причины.
Парадокс Протагора и Эватла
Знаменитый философ и учитель софистики Протагор обучил юношу Эватла юриспруденции. Ученик обещал заплатить за обучение, но только если выиграет свой первый судебный процесс. Однако после окончания учебы Эватл не стал браться за дела и платить отказался. Тогда учитель подал на него в суд.
Спор:
Аргументация Протагора: Если Эватл проиграет суд, то он обязан заплатить по решению суда. Если Эватл выиграет суд, он выиграет свой первый процесс, а значит, обязан заплатить по условиям их изначального договора. Вывод учителя: при любом исходе ученик должен отдать деньги. Контраргументация Эватла: Если я выиграю суд, то по решению суда я ничего не должен платить. Если я проиграю суд, то я не выполнил условие договора (не выиграл свой первый процесс), а значит, по контракту я тоже ничего не должен платить. Вывод ученика: я не должен платить ни при каком исходе.
Рассуждения:
Логическая ошибка кроется в интерпретации фразы «выиграл процесс». У Протагора: «выиграть процесс» — это просто сам факт победы в суде (успешный исход дела). У Эватла: «выиграть процесс» — это значит освободиться от уплаты. Эватл подменяет понятия. Он считает, что если он выиграл суд, значит, он не должен платить по договору. Но одно не исключает другое: он может выиграть суд и при этом быть обязанным выплатить гонорар, потому что суд доказал его статус выигравшего дело (тем самым активировав договор).
Если рассматривать парадокс с точки зрения судебного права, то он возникает из-за смешения двух разных юрисдикций: условий частного контракта (договора) и власти судебного решения (закона). В логике этот софизм решается так:
В этой части мы коснемся некоторых наиболее ходовых понятий, которые часто используются в терминологии компьютерных шахмат и без которых затруднительно конструктивное обсуждение вопросов перебора. Также рассмотрим некоторые второстепенные методы направленного перебора, которые тем не менее глубоко интегрированы в структуру поиска. И в концовке обсудим общий порядок обхода всего дерева перебора целиком.
Очередная латиница для русского языка, но только гибридная с совместимостью один к одному и с полным отсутствием диграфов, триграфов или ещё чего похуже, а также с минимальным количеством диакритических знаков.
Продолжаю публикацию интересных математических задач.
5 рациональных пиратов (А, Б, В, Г и Д) должны разделить 100 золотых монет. Иерархия: А — самый старший, Д — самый младший. Старший предлагает план дележа. Если за него проголосует хотя бы половина пиратов (включая его самого), план принимается. Если нет — старшего выбрасывают за борт, и право предложить план переходит к следующему. Как пират А должен разделить золото, чтобы остаться в живых и получить максимум?
Решение: Нужно рассуждать с конца. Если останутся только Г и Д, Г заберет всё (его голоса хватит для 50%). Чтобы этого не допустить, В должен предложить Д хотя бы 1 монету, чтобы тот поддержал его. Пират А знает это и предлагает: 98 — себе, 0 — Б, 1 — В, 0 — Г, 1 — Д. В и Д согласятся, так как при отказе и переходе хода к Б они могут не получить ничего или меньше.
В третьей части мы взглянем на дерево перебора в общем контексте поиска. Увидим, каким образом методы отсечений из предыдущей части влияют на дерево в целом или на значительные его части, а также для полноты картины оценим влияние этих методов в историческом контексте. Эту и следующую части можно пропустить, если общего описания основных методов ограничения перебора ранее кажется достаточным.
Самой важной частью шахматной программы, которая вносит основной вклад в силу игры, является направленный перебор. А самой главной частью направленного перебора являются отсечения и сокращения наиболее неперспективных ходов. Отбрасывая наименее важные ветви, программа вкладывает ресурсы машины в наиболее перспективные варианты. Чем больше отсекает программа, тем дальше она углубляется по дереву вариантов. И чем глубже она считает, тем сильнее играет.
Если бы программа считала до конца — до конечного результата в партии, то ей не потребовалась бы даже оценочная функция. Исторически, программы считали все глубже и глубже, и соответственно играли все лучше и лучше.
Здесь мы рассмотрим три наиболее значимых метода ограничения перебора вариантов. Они наиболее действенны, поскольку применяются по всей глубине дерева, хотя и срабатывают не в каждой позиции. Именно они приводят к наибольшему сокращению ветвления вариантов в дереве перебора, а значит и к наибольшему углублению.
Наверное многие из вас помнят шахматные состязания людей против компьютеров, которые проводились еще относительно недавно. Обычная картина для того времени - на сцене, за шахматным столом, под светом софитов и вспышками фотокамер в своих креслах расположились два человека. Один из них - шахматный гроссмейстер, сосредоточенно смотрит на доску. Второй же - оператор, часто поглядывает на экран монитора, который установлен рядом. Многочисленные зрители затаив дыхание наблюдают за этим действом со стороны.
Но самые глубокие страсти кипят за кулисами. Там не находит себе места многочисленная команда шахматной машины. Их труды только что закончились и они вынуждены просто наблюдать. Здесь находится группа умудренных опытом гроссмейстеров, которые на протяжении многих недель вкладывали в машину как свои огромные знания, так и многовековой опыт всего человечества. Здесь же многочисленная команда программистов, которая помогала им в этом процессе. Наконец, все действо патронируется большой корпорацией, которая не поскупилась оплатить их труды и конечно же задействовала для игры огромные вычислительные мощности. Наконец-то все эти многомиллионные вливания помогут сокрушить человека.
Красочная картина...
Не так давно я публиковал на Хабре обзорную статью о применении кубика Рубика в криптографии, где приводил интересный кейс с крипто-челленджем Клауса Шмеха. Потом мне стали попадаться еще интересные задачи с зашифрованными посланиями на кубике Рубика, как, например, случай на Reddit, где пользователь просил сообщество помочь расшифровать сообщение, которое ему оставила девушка на кубике Рубика. На олимпиадах по криптографии, как выяснилось, тоже периодически появляются задачки с шифрами на кубике Рубика. Всё это привело меня к мысли, что шифрование на кубике Рубика может быть весьма интересным занятными. И я решил поэкспериментировать с "рубошифрованием". В этой статье приведу первую (простую) задачку, на решение которой мне понадобилось около часа. Жду ваших решений в комментариях. А правильный ответ и собственное решение опубликую через пару недель.
Создай свое собственное судоку — одна из интересных головоломок игры MIT Mystery Hunt 2014 года. Головоломка представляла собой пустое поле судоку, к которому прилагались 4 набора подсказок. Первые 3 набора были необходимы для того, чтобы вписать в пустое поле исходные цифры головоломки: они относились к секторам, строкам и столбцам поля соответственно. Последний набор относился к цифрам поля и служил для получения ответа на задание после решения судоку.
Очень часто в современном мире слышно вой о том, что «раньше было лучше», и зачастую все как мантру принимают это на веру. Мол, не будут же почтенные старцы нам врать? Но я склонен подвергать такие заявления сомнению, так как зачастую мы видим только вершину успеха, забывая про все огрехи. К примеру, многие полагают, что старые редакции D&D не сильно уступают современным редакциям, а возможно, даже лучше. Монстры там были сильнее, подземелье сырее, и на каждую грань d100 были интересные нюансы. Но что на самом деле? И почему d100 спокойно заменил d20 со временем? Что именно было в D&D раньше? Что поменялось? В чем ключевые отличия старого и нового D&D?
Настольные игры уже давно перестали быть развлечением для «избранных»: игротеки, проводимые крупными издателями, собирают большое число людей, а каждый офисный работник может с гордостью сказать, что на корпоративе они играли в настольную игру «Мафия» (ну или «Надувного Валеру», тут уж кто во что горазд). Я бы даже сказал, что ситуация стала диаметрально противоположной: из очень нишевого развлечения настолки превратились в массовое, но для большинства так и остались где-то на уровне «Монополии», «500 злобных карт» и «Манчкина» (последний это уже для про-игроков). Я же в свою очередь хотел бы рассказать про относительно свежую «большую» кооперативную настолку «Оскверненный Грааль. Короли Краха».
В этом месяце вышло уже 110 дополнение к MTG. На это раз посвящённое коллаборации со вселенной Черепашек-Ниндзя (при этом, дополнений, не выходящих в основном соревновательном формате, за все эти годы вышло ещё больше). Но речь в статье пойдет не об этом новом блоке, а о фундаментальных особенностях правил и способах их "правки".
Карточная Магия исторически имеет несколько проблем в базовой механике, с которыми игрокам приходится жить и от которых никуда не деться. Тем не менее, можно ультимативно разрешить основные проблемы, придумав иной формат игры. Например - "Разделённая Колода".
Спидкубинг – сборка кубика Рубика и других головоломок на скорость – уже давно перестал быть просто хобби и превратился в глобальное интеллектуальное соревновательное движение. С 2003 года по всему миру проводятся турниры под эгидой Всемирной ассоциации кубика (World Cube Association – WCA), формируя единую систему правил, рейтингов и мировых рекордов. На март 2026 года количество уникальных участников (людей, которые хотя бы один раз выступали на официальных соревнованиях WCA) – более 282 000 человек из более чем 150 стран мира, а количество проведенных официальных соревнований – более 16 600. Причем за последние полгода добавилось порядка 15 000 новых участников и проведено боле 2 500 соревнований.
На этом фоне в среде спидкуберов всё чаще появляются разговоры о признании спидкубинга полноценным видом спорта и даже о его потенциальном включении в олимпийскую программу в будущем. С 2023 года WCA активно адаптирует свои правила под стандарты МОК с целью получения статуса IOC-recognized international sports federation. Делается это для расширения возможностей фандрайзинга, большей легитимности, запуска антидопинговых программ и т.д. Но до включения в программу Олимпиад, все же, еще очень далеко.
Сегодня расскажу об опыте Китая, который пошел по более прагматичному и централизованному пути. Спидкубинг в Поднебесной не только стремительно развивается, но и уже получил официальный статус спортивной дисциплины. Более того, в стране реализуется стратегия развития спидкубинга, предполагающая рост аудитории до 12 миллионов занимающихся к 2028 году.
Как Китай продвигает спидкубинг на государственном уровне, и чем этот опыт может быть интересен России – обсудим далее.
Пиксель кажется чистым изобретением компьютерной эры – светящаяся точка на экране, из миллионов которых складываются все наши фото, игры и видео. Мы привыкли думать о нём как о технической единице: квадратной и цифровой.
Но если посмотреть внимательнее, идея пикселя появилась задолго до первых процессоров. Это не столько технология, сколько способ мышления: разбить сложное изображение на отдельные части и собрать их заново уже в своей голове.
Художники открыли эту логику первыми, когда наносили на холст сетку, пытались управлять светом через темную комнату – она же камера-обскура, а позднее превратили дискретность в художественный принцип. Затем пришла цифровая революция: пиксель стал матрицей чисел, стандартом тестирования и языком видеоигр. А сегодня пиксель вернулся туда, откуда появился, – в материальный мир, но уже как культурный феномен. Теперь пиксель можно держать в руках: это кубик Рубика или кирпичик LEGO. В этой статье мы пройдём путь от аналоговой сетки к цифровому пикселю и обратно… к кубику Рубика.
Видели мозаики из кубиков Рубика? В сети достаточно контента с кубическими картинами, портретами из десятков, сотен, и даже тысяч кубиков. Но никто не собирает мозаики из пирамидок. Пирамидка (она же – пираминкс) – это перестановочный пазл, похожий на кубик Рубика. Ее цветные элементы – те же пиксели, только треугольные, и цветов не шесть, а четыре. Казалось бы, бери и складывай. Однако мозаик из пирамидок я не встречал.
Давайте разбираться почему. Пирамидка устроена сложнее, чем кажется. Во-первых, на грани пираминкса нельзя путем вращения получить любую комбинацию цветов, как на одной грани кубика Рубика. И эта механическая особенность является существенным ограничением при создании мозаик. Во-вторых, форма пирамидки не позволяет без специальных приспособлений составлять несколько головоломок между собой. В-третьих, треугольная форма цветных плиток делает сетку мозаики достаточно сложной для пикселизации исходного изображения, а всего четыре цвета дают существенно меньшую палитру, чем у кубика Рубика. И все же мозаика из пирамидок – вполне решаемая, хотя и нетривиальная задача, где пересекаются творчество, геометрия, комбинаторика и немного инженерной изобретательности.
