winpooh: (Default)
"В продолжение двадцати лет эмигрантской жизни в Европе я посвящал чудовищное количество времени составлению шахматных задач. Это сложное, восхитительное и никчемное искусство стоит особняком: с обыкновенной игрой, с борьбой на доске, оно связано только в том смысле, как, скажем, одинаковыми свойствами шара пользуется и жонглер, чтобы выработать в воздухе свой хрупкий художественный космос, и теннисист, чтобы как можно скорее и основательнее разгромить противника. Характерно, что шахматные игроки — равно простые любители и гроссмейстеры — мало интересуются этими изящными и причудливыми головоломками и, хотя чувствуют прелесть хитрой задачи, совершенно неспособны задачу сочинить. <…>

Мне вспоминается одна определенная задача, лучшее мое произведение, над которым я работал в продолжение двух-трех месяцев весной 1940 года в темном оцепеневшем Париже. <…> Помню, как я медленно выплыл из обморока шахматной мысли, и вот, на громадной английской сафьяновой доске в бланжевую и красную клетку, безупречное положение было сбалансировано, как созвездие. Задача действовала, задача жила. Мои Staunton’ские шахматы, великолепные массивные фигуры на байковых подошвах, отягощенные свинцом, с пешками в шесть сантиметров ростом и королями почти в десять, важно сияли лаковыми выпуклостями, как бы сознавая свою роль на доске. <…>

Мои часы — ручеек времени по сравнению с оледенелым его озером на доске — показывали половину третьего утра. <…> Кругом было очень тихо. Облегчение, которое я испытывал, придавало тишине некоторую нежность. Из-под дивана выглядывал игрушечный грузовичок. В соседней комнате ты и наш маленький сын мирно спали. Лампа на столе была в чепце из голубой сахарной бумаги (военная предосторожность), и вследствие этого электрический свет окрашивал лепной от табачного дыма воздух в лунные оттенки. Непроницаемые занавески отделяли меня от притушенного Парижа. Лежавшая на диване газета сообщала крупными литерами о нападении Германии на Голландию.

Передо мной лист скверной бумаги, на котором в ту лилово-черную парижскую ночь я нарисовал диаграмму моей задачи. Белые: Король, a7; Ферзь, b6; Ладьи, f4 и h5; Слоны, e4 и h8; Кони, d8 и е6; Пешки, b7 и g3. Черные: Король, e5; Ладья, g7; Слон, h6; Кони, e2 и g5; Пешки, c3, c6, d7. Белые начинают и дают мат в два хода. Решение дано в следующей главе."


-- В.Набоков, "Другие берега"



Замечу, что моя программа с настройками по умолчанию находит здесь мат только в три хода:

White(1): load nabokov.fen
3N3B/KP1p2r1/1Qp1N2b/4k1nR/4BR2/2p3P1/4n3/8 w - - 0 1
 
White(1): analyze
 
3N3B/KP1p2r1/1Qp1N2b/4k1nR/4BR2/2p3P1/4n3/8 w - -
 
  1    32763        2          2763  1. Bxg7+ Bxg7 2. b8=B+ d6 3. Rxg5# {+Mate in 3}
  2    32763        3          6051  1. Bxg7+ Bxg7 2. Rxg5+ Kd6 3. Qc5# {+Mate in 3}
  3    32763        4          9601  1. Bxg7+ Bxg7 2. Rxg5+ Kd6 3. Qc5# {+Mate in 3}
  4    32763        5        13043  1. Bxg7+ Bxg7 2. Rxg5+ Kd6 3. Qc5# {+Mate in 3}
  5    32763        8        46108  1. Bxg7+ Bxg7 2. Rxg5+ Kd6 3. Qc5# {+Mate in 3}
  6    32763      12        139430  1. Bxg7+ Bxg7 2. Rxg5+ Kd6 3. Qc5# {+Mate in 3}
  7    32763      27        592426  1. Bxg7+ Bxg7 2. Rxg5+ Kd6 3. Qc5# {+Mate in 3}
  8    32763      91      2724710  1. Bxg7+ Bxg7 2. Rxg5+ Kd6 3. Qc5# {+Mate in 3}

Правильный ответ даёт если отключить эвристику нулевого хода.
Приводить его здесь не буду, чтобы не портить никому удовольствие от самостоятельного решения :)
winpooh: (Default)
Общий счёт для чемпионов мира этой осенью, по результатам двух матчей: +0 -7 =10.
winpooh: (Default)
Дождались, наконец-то. Сегодня в индийском городе Ченнай (бывший Мадрас) состоится первая партия матча за звание чемпиона мира по шахматам Ананд - Карлсен.
Многие считают, что это будет самый интересный матч с начала XXI века, а то и со времён встреч Карпова с Каспаровым.
Столь же многие думают, что безоговорочный фаворит - Магнус Карлсен.

Два самых интересных предстартовых материала:

- Сергей Шипов: Магнус обязан выиграть матч и стать официальным чемпионом мира
- Евгений Свешников: Не удивлюсь, если Карлсену не удастся завоевать титул с первой попытки

Начало партий в 13:30 по Москве. Следить буду на http://crestbook.com и http://chesstv.com. Болею за Ананда.

Crestbook

Oct. 30th, 2013 04:04 pm
winpooh: (Default)
Статья о Битмане опубликована на Crestbook.
Добавлены избранные шахматные партии Александра Рафаиловича.

http://crestbook.com/node/1859
winpooh: (Default)
Статья опубликована в 4-м номере журнала ОГО.



Владимир МЕДВЕДЕВ
МОИ ВСТРЕЧИ С АЛЕКСАНДРОМ БИТМАНОМ


Это очень субъективные заметки о моём общении с недавно ушедшим от нас А.Р.Битманом – ценителем и пропагандистом Го, шахматистом, математиком, поэтом. Личность Александра Рафаиловича была настолько многогранной, что я не претендую на сколь-нибудь полный рассказ о нём. Надеюсь, тем не менее, внести своими воспоминаниями хотя бы несколько штрихов в портрет этого незаурядного человека.

Далее... )
winpooh: (Default)
Некоторое время назад я писал о состоянии дел в исчерпывающем расчёте на компьютере различных игр - шахмат, шашек, Го... Для шахмат на тот момент были доступны шестифигурные эндшпильные таблицы. За прошедшее время прогресс не стоял на месте, и к делу подключилась "тяжёлая артиллерия" в виде суперкомпьютера МГУ "Ломоносов" (31-е место в TOP500 на июнь 2013 года). В результате этой весной широкой публике были представлены таблицы Ломоносова - полная эндшпильная база для окончаний с числом фигур на доске не более 7, включая королей.

Доступ к таблицам предоставляется только онлайн, из шахматной оболочки "Аквариум". Впрочем, при всём желании скачать на домашний компьютер их будет проблематично - полный объём данных составляет 140 терабайт. Для сравнения: пятифигурная база занимает порядка 7.5 ГБ, шестифигурная - более 250 ГБ.

На официальной странице проекта приводится несколько эндшпильных позиций с оценкой "по Ломоносову". Вот одна из них - чёрные начинают, и получают форсированный мат в 545 ходов.



Всё-таки шахматы - очень простая игра, не правда ли? :))

GreKo 9.0

Jan. 1st, 2012 06:28 pm
winpooh: (Default)
Традиционная новогодняя версия моего шахматного движка:
http://greko.110mb.com

Изменения по большей части в настройках поиска. Мои тесты показывают прирост силы порядка 50 пунктов Эло на суперкоротких контролях времени.
Предыдущая версия, тем временем, сделала автору новогодний подарок, выиграв турнир своего дивизиона, и добравшись до уровня 2625 в рейтинге CCRL на 1-е января.

32ND AMATEUR SERIES (Division 5)

30.0 - GreKo 8.2 32-bit
26.0 - LittleThought 1.052 32-bit
25.0 - Eeyore 1.52
24.5 - Pupsi2 0.08
23.0 - Murka 2.0 32-bit
22.0 - Atlas 3.14b 32-bit
22.0 - Simplex 0.9.8 32-bit
20.5 - OliThink 5.3.0
20.5 - Alex 2.14a 32-bit
20.0 - Hussar 0.4
16.5 - Ifrit m1.5
14.0 - Ice 0.2
winpooh: (Default)
Принял участие в традиционном шахматном блиц-турнире по случаю дня рождения [livejournal.com profile] bazar_wokzal. Поскольку в эту игру не играл уже больше года, накануне пошёл потренироваться на FICS. По итогам тренировки были поставлены а) задача-минимум - не набрать ноль очков, и б) задача-максимум - не занять последнее место. В итоге обе задачи удалось с запасом перевыполнить. На самом деле, была и ещё одна, главная - дожить в здравом рассудке до конца турнира в 29 партий без антракта.

Несмотря на полное отсутствие практики, сыграл на свой уровень - набрал 25% в плотном составе с множеством гроссмейстеров, мастеров и кандидатов. Из чего можно сделать вывод, что шахматная моя сила не убывает. Совсем как у Ходжи Насреддина - который и в детстве не мог поднять тот камень во дворе, и в юности, да и сейчас всё так же.
winpooh: (Default)
На Crestbook выложено интервью с гроссмейстером, обладателем Кубка Мира Борисом Гельфандом.

Первая часть
Вторая часть



Б. Гельфанд, Э. Сутовский, 2005
Белые начинают и делают ничью
winpooh: (Default)
Под новый год, аккурат 31-го декабря, ко мне пришёл добрый дедушка Мороз и забрал с собой старый блок питания вместе с материнской платой. Своеобразие подарка заключалось в том, что, во-первых, я провёл несколько праздничных дней без компьютера, наслаждаясь шедеврами домашней кулинарии и мирового синематографа. А во-вторых, появился повод произвести полный апгрейд системы. В результате в процессоре стало больше ядер, в комнате - больше шума (кулер пока не обновил), в дисковых массивах - больше гигабайтов. Дополнительным бонусом стал навык восстановления данных из массивов RAID-0 и RAID-1, живших на встроенных контроллерах старой материнской платы (совершенно невозможная операция, если верить продавцам из Будёновского центра :)) Ну, и твёрдое убеждение, что, хотя на этот раз пронесло, но бэкап таки делать надо. Спасибо, дедушка Мороз!

Для обновлённого компьютера сразу нашлось достойное применение - стартовали два турнира по адванс-шахматам. В одном из них, на Экстрабрейне, я буду защищать звание чемпиона, завоёванное в прошлом году. В другом - сражаться с сильнейшими адвансерами в пятом чемпионате гостевой KasparovChess. Таким образом, в сумме получается 25 одновременных партий. Одну из них, на KC, я уже завершил быстрой ничьей, и тем самым вышел в лидеры турнира :))

winpooh: (Default)
Совместно с коллегами с форума Crestbook подготовили читательскую конференцию с Александром Никитиным - шахматным тренером, из подопечных которого достаточно упомянуть Гарри Каспарова.
В процессе работы над материалом обрёл бесценный опыт расшифровки скайповских аудиозаписей. Труды были не напрасны - ответы получились интересными, подробными и содержательными.

Первая часть - здесь:
http://www.crestbook.com/?q=node/1099

Вторая - будет опубликована на днях.
winpooh: (Default)
Был сегодня в ГУМе на чемпионате мира по блицу в рамках мемориала Таля. Посмотрел вживую несколько туров, взял автограф у Василия Иванчука на книге "Дзэн и искусство стрельбы из лука" (больше ничего под рукой не оказалось) - и скорее домой, слушать аудио-онлайн Сергея Шипова на crestbook.com.

Успел как раз вовремя - к встрече Ананда с Карлсеном. Магнус партию выиграл, а через некоторое время оформил и победу в турнире. Ура новому чемпиону мира!
winpooh: (Default)
В прошлом году в записи про УХУДУ и ПУП я давал ссылки на рукописные бланки с автокодом шахматной программы ИТЭФ - предшественницы "Каиссы". Недавно обнаружил проект по созданию эмулятора машины М-20, той самой, на которой эта программа работала. Значит, есть надежда на успешный запуск под эмулятором! Если, конечно, исходный код достаточно полный.

Теперь сканы сконвертированы из tiff в pdf, за что спасибо [livejournal.com profile] ramlamyammambam. Вместе с PC-версией "Каиссы" разместил их на страничке моей шахматной программы GreKo.
winpooh: (Default)
Выиграл финальный матч за звание чемпиона сайта Extrabrain по шахматам. В оставшихся двух партиях с Игорем Щукиным у меня шансов не то что бы много, но счёт сейчас 4:1 в мою пользу. Матч получился весёлым, почти в каждой партии что-то жертвовалось. Вот, к примеру, подтверждение известного тезиса Алехина о том, что "ферзь только мешает".

[Event "48250"]
[Site "Extrabrain"]
[Date "2009.04.20"]
[Round "1"]
[White "WinPooh"]
[Black "Ischukin"]
[Result "1-0"]
[EventDate "2009.04.20"]


1.d4 Nf6 2.c4 c5 3.e3 g6 4.Nf3 b6 5.Nc3 Bg7 6.Be2 O-O 7.O-O d6 8.Qd3 e6 9.e4 Nc6 10.d5 Nd4 11.dxe6 Bxe6 12.Nxd4 cxd4 13.Nb5 Rc8 14.Qxd4 a6 15.Nc3 Nd5



16.Qxg7+ Kxg7 17.cxd5 Bd7 18.Bxa6 Rb8 19.a4 f5 20.Be3 fxe4 21.Rfd1 Qe7 22.Be2 g5 23.h3 Bf5 24.Rd4 Kg8 25.Rb4 Qf7 26.Rxb6 Rxb6 27.Bxb6 h5 28.a5 g4 29.hxg4 Bxg4 30.Bf1 h4 31.Ra4 Bf5 32.a6 h3 33.g3 Ra8 34.Be3 Kg7 35.Kh2 Qe7 36.b4 1-0


До настоящего момента удалось пройти всю дистанцию (отбор, полуфинал, финал) без поражений, с общим результатом +26-0=8.
winpooh: (Default)
Речь пойдёт об одном простом, но элегантном трюке, упрощающем код генератора ходов в шахматной программе. Как уже упоминалось в заметке про слонов, самая ресурсоёмкая процедура - это поиск траекторий дальнобойных фигур. Вот один из возможных путей этого поиска, без использования сканирующих доску циклов.

(Краткого и внятного изложения данного алгоритма на русском языке я пока не встречал, поэтому попробую восполнить пробел. Краткость - обещаю, внятность - как получится :)


Если программа для представления доски использует битборды (набор из 12-ти 64-битных чисел, по одному на каждый тип белых и чёрных фигур), можно разменять память на время, предвычислив траектории ладьи и слона для каждого поля пустой доски. Например, у нас есть ферзь на E4. Соответствующий битборд выглядит так:

- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - 1 - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -


Во всех примерах здесь и далее рассматривается представление доски, где полю A8 соответствует старший бит 64-битного слова, а полю H1 - младший. Таким образом, фигура на E4 кодируется как 0х8000000.

На пустой доске возможные траектории ферзя находятся элементарно:

1 - - - 1 - - -
- 1 - - 1 - - 1
- - 1 - 1 - 1 -
- - - 1 1 1 - -
1 1 1 1 - 1 1 1
- - - 1 1 1 - -
- - 1 - 1 - 1 -
- 1 - - 1 - - 1


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

Для вертикалей и горизонталей:

- - - - - - - -
- - - - 1 - - -
- - - - 1 - - -
- - - - 1 - - -
- 1 1 1 - 1 1 -
- - - - 1 - - -
- - - - 1 - - -
- - - - - - - -


Для диагоналей:

- - - - - - - -
- 1 - - - - - -
- - 1 - - - 1 -
- - - 1 - 1 - -
- - - - - - - -
- - - 1 - 1 - -
- - 1 - - - 1 -
- - - - - - - -


Поля E8, A4, H4, E1 (для прямых линий) и A8, H7, B1, H1 (для диагоналей) в масках не учитываются - ферзь с поля E4 нападает (или не нападает) на эти поля независимо от того, стоит ли на них какая-нибудь фигура.

Теперь видно, что вертикальные/горизонтальные траектории ферзя с поля E4 определяются состоянием 10-ти полей, а диагональные - только 9-ти. Оценка сверху для числа возможных комбинаций - соответственно, 2^10 = 1024 и 2^9 = 512 вариантов. Таким образом, если завести для поля E4 два массива из [1024] и [512] 64-битных чисел, то алгоритм поиска траекторий ферзя на E4 сводится к следующим пунктам:

1) вычисляем побитовое AND всех фигур на доске с маской для вертикалей/горизонталей
2) вычисляем индекс в таблице [1024], берём из неё первый битборд с атаками по вертикалям/горизонталям
3) вычисляем побитовое AND всех фигур на доске с маской для диагоналей
4) вычисляем индекс в таблице [512], берём из неё второй битборд с атаками по диагоналям
5) применяем к двум полученным битбордам побитовое OR - получаем битборд с полными атаками ферзя для заданного положения фигур

Весь вопрос в том, как быстро вычислить индексы. Дело в том, что после сложения, например, с диагональной маской мы получим целое число в диапазоне от 0x40000000000000 до 0x200 - назовём его Х. Одно из 512 возможных. Нужно взаимно однозначно отобразить это число в диапазон от 0 до 511.

На помощь приходит так называемое совершенное хэширование (perfect hashing). Оказывается, достаточно арифметически умножить Х на некоторую константу magic, после чего старшие разряды произведения идельно (без коллизий) хэшируют исходный диапазон в то, что нам надо. Остаётся только проделать битовый сдвиг. Результирующая формула имеет вид:

X = (occupied & mask[E4]);
index = (magic * X) >> (64 - 9);


index гарантированно оказывается в диапазоне 0...511. Можно идти в таблицу и брать нужный результат.

Для нашего излюбленного поля E4 слоновый magic может быть равен, например, 0x8501010000104000, а ладейный - 0x0018080080240080.
Как найти magic для каждого поля доски? Проще всего - генератором случайных чисел. Берём случайное 64-битное число, прогоняем все 512 (или 1024, или сколько их там выходит) возможных конфигураций, ищем значение, при котором не происходит коллизий.

Есть одна деталь. Когда я генерировал набор magic-ов для Греки, я сначала в качестве случайных чисел брал "честные" значения из линейного конгруэнтного генератора. Магические константы находились, но как-то очень уж медленно. На некоторые поля уходило по несколько часов, а иногда компьютер не мог угадать magic и за всю ночь. Тогда я обратил внимание на то, что в open-source программах магические числа очень разреженные, т.е. содержат малое количество единиц. Модифицированный генератор - для чисел с 7-ю установленными битами - обеспечил нахождение всех коэффициентов для ладьи и слона за считанные секунды...

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

Ссылки

Chess program board representations - статья Роберта Хьятта, основы битборд-представления
Rotated bitmaps, a new twist on an old idea - ещё одна его статья: как эту задачу решали до магических битбордов
Magic bitboards - подробное описание алгоритма, со ссылками на первоисточники в pdf и примерами реального кода
De Bruijn Sequence - простое объяснение магии, стоящей за техникой perfect hashing.

Кросс-пост в Берлогу 2.0.

Всех читающих эти строки, друзей и гостей - с наступающим Новым Годом! Главное пожелание - не забывать, что было написано на обложке Путеводителя Автостопом по Галактике :))
winpooh: (Default)
И снова об истории первых игровых программ. Оказывается, перед шахматами была предпринята попытка научить компьютер играть в подкидного дурака. Попытка эта с треском провалилась, после чего программисты переключились на шахматы. Где лет через 40-50 и преуспели, да так, что встал вопрос о закрытии шахмат как явления культуры. Так какая игра сложнеее? :) Недаром одним из лучших игроков в подкидного "один на один" считается 12-й чемпион мира по шахматам Анатолий Карпов!

Вот что пишет в своей книге "Беседы о программировании" А.С.Кронрод:

"...В 1958 году была постулирована некоторая программа действий. Тогда мы не знали, как удивительно медленно действует машина. И думалось - достаточно дерзнуть. Мы - Адельсон-Вельский, Ландис и я - сделали и пустили программу на машине М-2. Пока игра шла с колодой, всё было пристойно. Наверное, оттого, что человек тоже мало чего соображает в столь сложной ситуации. А может быть, все кругом просто плохо играли в эту игру. Или оттого, что уж слишком многое зависит от расклада. В общем, так или иначе, пока была колода, позора не было. Но что началось, когда колода кончилась! Именно с открытыми-то картами программа играла безумно, невероятно, непроходимо скверно!

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

Вместо ленточки появился эндшпиль. И - финал эндшпиля, для ускорения. И ровно на этом мы и кончились. Потому что считая эндшпиль 6 : 6, машина обязательно ломалась. После нескольких часов работы.... Что произошло от этой нашей неудачной деятельности? Прямо для думания - ничего. Или, вернее, негативный результат: с помощью машины мы могли думать много хуже, чем без неё. Точнее, через машину мы думали медленнее, чем непосредственно. Анализ показал неожиданное: мы просто не умели высказать всех своих соображений, как и почему выбираем ход (спрограммировать-то точные вещи мы уже умели). Именно тогда я задумался о сознании и подсознании.

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


Вот так рождались идеи, которые нынче путешествуют из кода в код сотен шахматных программ с открытыми исходниками :))

О таинственных аббревиатурах в заголовке. УХУДУ - это всего лишь "упорядочение ходов, удовлетворяющих данному условию". Что такое ПУП, Кронрод не раскрывает, но из контекста ясно, что это некая подпрограмма, связанная с оценкой позиции.

В качестве ссылок сегодня - в некотором роде исторический материал.

Автокод шахматной программы ИТЭФ для машины М-20. Представляет собой набор отсканированных рукописных бланков. УХУДУ и ПУП там присутствуют, я проверял :)
Каисса для PC - портированный в начале 90-х на Turbo C вариант одной из поздних мэйнфреймовских Каисс. Тех самых, что участвовали в первых чемпионатах мира. Программа запускается на современных машинах, и успешно играет!
winpooh: (Default)
Завершил игру в полуфинале чемпионата Extrabrain по адвансу. В заключительной партии с [livejournal.com profile] tihonoff чуть ли не с дебюта сидел без пешки, но, призвав решительность и строгость (а также правильные программы и цейтнот партнёра), смог отбиться. Что, впрочем, решало только формальный вопрос о распределении мест - в финальную часть мы оба уже попали досрочно...

диаграмма

диаграмма

В целом, результат порадовал. По крайней мере, есть моральное оправдание тому, что профилонил первенство KasparovChess.
winpooh: (Default)
Среди людей, лишь краем уха слышавших об успешной игре Фрицев и Рыбок против Каспарова, Крамника и пр., распространено мнение, что компьютеры "решили шахматы" - т.е. в каждой позиции программы могут найти идеальный ход. Да что там краем уха, отголоски этого мифа встречаются даже среди неплохих шахматистов-любителей, начинающих играть в адванс - современный, компьютеризованный вариант игры по переписке. После первых партий, с попытками следовать за компьютером ход-в-ход "по первой линии", они бывают немало удивлены :)) Впрочем, адванс - это тема для отдельной записи (и не одной), а сейчас о действительно решённых - с математической строгостью - играх.

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

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

Противоположный пример - малофигурные шахматные окончания. Никаких общих правил нет, но таблицы Налимова (объёмом до нескольких терабайт в случае 6-7-фигурных эндшпилей) обеспечивают идеальную игру в произвольной позиции. Наблюдать за ходами компьютера в некоторых окончаниях (вроде Ф+С против Ф+К) - очень хорошее средство разубедить себя в том, что шахматы есть игра логическая и стратегическая. Ходы производятся с человеческой точки зрения совершенно хаотичные и бессмысленные, но расстояние до мата (40... 30... 20 ходов...) неизменно сокращается.

При слабом решении требуется всё то же самое, но не для произвольной, а для начальной позиции. Так в 2007 году была решена игра чекерс (английские шашки). Насколько мне известно, факт решения чекерса не сильно огорчил игроков - мировые чемпионаты по-прежнему проводятся. Тем не менее, вы можете сыграть с онлайн-версией программы Chinook на её сайте. Если очень повезёт - получится ничья.

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

Игра Го полностью решена на доске 5х5 - но лишь в слабом смысле, хотя и для всех 25 начальных ходов. Библиотека Сенсея утверждает, что при анализе одного из вариантов на этой доске-малютке ошибся сам Cho Chikun - человек-легенда, возможно лучший игрок в Го 20-го века (после Го Сейгена, конечно :))



Большой список в разной степени решённых игр можно найти в Википедии. Упоминаются свободное рэндзю, реверси 6x6 и много других игр, названия которых для меня - полнейшая загадка...

Кросс-пост в Берлогу 2.0.
winpooh: (Default)
Одна из самых ресурсоёмких задач в программировании шахмат - генерация траекторий дальнобойных фигур: слона, ладьи и ферзя. Её приходится реализовывать либо в виде цикла с большим количеством проверок (не вышли ли мы за пределы доски? не наткнулись ли на фигуру, свою или противника?), либо путём просмотра довольно объёмных, до мегабайта, таблиц с хитроумно устроенными индексами. И то, и другое - не слишком экономичные по времени операции.

Поэтому уже давно предпринимались попытки сделать своего рода "аппаратный шахматный ускоритель" для таких рутинных задач, как поиск возможных ходов или расчёт мобильности фигур. В небезызвестном Deep Blue для этой цели использовалась матрица из 64 процессоров - по одному на каждое поле доски. Если заглянуть в историю чуть дальше, в начале 80-х можно обнаружить аппаратно реализованный генератор в шахматной системе Belle Кена Томпсона. Наверняка есть и другие примеры, удачные и не очень.

А теперь самое время вернуться к заголовку. Но вряд ли правы будут те, кто предположит, что под слоном здесь имеется в виду только шахматная фигура. Слово Александру Кронроду, чья книга "Беседы о программировании" за последние годы переиздана уже несколько раз, хотя пока так и не попалась мне в электронном виде.

Из главы "Беседа десятая - О работах Н.И.Бессонова".

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

В самом напряжённом по времени месте (определение возможных ходов данной фигуры с учётом расположения прочих фигур) СЛОН Бессонова экономит время в сто раз.

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

Имеющий уши да слышит.

В отзыве заведующего отделом Вычислительного центра Академии наук СССР В.М.Курочкина было сказано:

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

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

B в авторском свидетельстве на СЛОНа отказали. Это был уже последний отказ в изобретательской карьере Бессонова...


Всё это происходило в 1963-м. Шахматисту, которого через 34 года Deep Blue обыграет в историческом матче, исполнилось на тот момент шесть месяцев.
Кросс-пост в Берлогу 2.0.

Profile

winpooh: (Default)
Vladimir Medvedev

January 2014

S M T W T F S
   123 4
5678 91011
12 13141516 1718
1920 2122 23 2425
26 272829 3031 

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 10:57 am
Powered by Dreamwidth Studios