winpooh: (Default)
Вольно же мне, не вняв движенью лет,
секунды жизни тратить безвозвратно.
Скачать бы весь ваш этот интернет -
и после не закачивать обратно.
winpooh: (Default)
По просторам интернета
бродят боты-телепаты.
Закупают наши души
по тарифам предоплаты.

У него ментальный сканер
на Питоне или Руби.
Он тебе покажет баннер,
а потом навек погубит.
winpooh: (Default)
В продолжение темы об эмуляторах ПМК. Появилась ещё одна реализация -- на этот раз со знаменитыми ЗГГОГ-ами. Эмулятор в точности воспроизводит богатую фауну сверхчисел, обнаруженную энтузиастами и подробно описанную в "Технике-молодёжи". А ещё (мечта детства сбылась!) у него есть постоянная память для программ. Теперь в метро можно играть не только в Го и шахматы, но и в "Лунолёт" :))
И, конечно, я буду использовать его по прямому назначению -- по уровню удобства ни один встреченный мной на Андроиде калькулятор и рядом с МК-61 не стоял.

Слово автору:
"Моя аппликация использует результаты гениального исследования человека с очень мощным микроскопом, реверс-инженера и программиста Феликса Лазарева, автора проекта emu145. Благодаря ему эмулятор в мельчайших подробностях повторяет поведение настоящего калькулятора, со всеми его недокументированными возможностями. Достигается это благодаря прямому исполнению микрокода, который Феликс "вытащил" микроскопом из микросхем калькулятора."



MK 61/54 на Гугл-Маркете.
Большое спасибо автору эмулятора [livejournal.com profile] cax.
winpooh: (Default)
Статья опубликована в 4-м номере журнала ОГО.



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


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

Далее... )
winpooh: (Default)
ИИ китайского тетриса
эвристикой новой занят:
"И всё-таки она вертится...
падает... исчезает!"

Под влиянием статьи на Хабре о том, как лёгким движением паяльника многочисленные модификации игрушки превращаются одна в другую.
В комментариях ещё обсуждается, можно ли поставить на них Линукс.
winpooh: (Default)
В третьем номере журнала Александра Динерштейна "ОГО" нашёл ссылку на скрипт для анализа партий: GoStyle Web App. На входе он просит имя игрока на КГС, или zip-архив с партиями. Затем какое-то время (порядка минуты) думает, и выдаёт характеристику по нескольким критериям: агрессивный/спокойный стиль, территория/влияние, и т.п. Кроме того, подсказывает набор форм, на которые стоит обратить внимание - если они встречаются в проанализированных партиях реже, чем у более сильных игроков. А самое интересное, на мой взгляд - даёт два списка из профессионалов, наиболее близких и наиболее далёких по стилю.

У меня на КГС сейчас есть несколько активных аккаунтов. Чтобы разнообразить эксперимент, я дал программе четыре разных набора партий. Численные значения параметров (по шкалам от 1 до 10) оказались примерно такими, как я и предполагал (классика, спокойная игра, территория, плотность - в этом направлении). Интересно, что среди рекомендованных к просмотру профессионалов есть вполне чёткое разделение - ни один не попал в обе группы сразу.

Немного статистики... )

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

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

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



Всё-таки шахматы - очень простая игра, не правда ли? :))
winpooh: (Default)
В 2012 году я, поддавшись всеобщей моде, прошёл два онлайн-курса на Coursera. О первом, по машинному обучению, я уже писал. Теперь краткий отчёт о втором - по компиляторам.
Целью прохождения курса было собрать воедино свои разрозненные знания по предмету и ликвидировать наиболее зияющие белые пятна в программистском самообразовании. Могу сказать, что этой цели я достиг.


подробности... )
winpooh: (Default)
Прошёл курс Machine Learning: десять недель, порядка 30 часов видео, тесты на усвоение материала и 8 практических работ. Просмотрел все лекции, выполнил контрольные и упражнения по программированию - всё на 5 (синдром отличника, это не лечится). Очень познавательный и полезный курс, я узнал для себя много нового. Содержание широкое - от метода наименьших квадратов, линейной регрессии и градиентного спуска до самых современных подходов вроде Support Vector Machines, Map-Reduce, онлайн-обучения, рекомендательных систем и т.д. Заодно наконец-то освоил Octave/MATLAB, и "потрогал руками" многие из рассмотренных в курсе алгоритмов - в частности, обучение нейросетей.

Особо следует отметить мастерство преподавателя, Andrew Ng, в построении курса - он умеет объяснять достаточно сложные вещи (те же SVM) step-by-step, начиная с простых примеров, и достаточно быстро добираясь до сути. При этом объём необходимой для общего объяснения математики - даже меньше, чем первые два семестра в институте. Так, в части линейной алгебры почти удалось обойтись без детерминантов матриц и теорем о собственных векторах.

Собираюсь теперь применить полученные знания к настройке оценочной функции своей шахматной программы. В планах также через некоторое время пройти на Coursera ещё один-два курса по Computer Science - есть несколько интересных вариантов. Но дело это затягивающее, тут привыкание вырабатывается :))
winpooh: (Default)
Во вторник и среду посетил конференцию Оракла. Проводилась она в этом году в Большом зале РАН, недалеко от памятника Гагарину - удачный выбор места в день космического юбилея. Пару лет назад я уже был на подобном мероприятиии, только не в Москве, а в Питере, и организатором тогда числилась ещё Sun. В отличие от того раза, практически все доклады были про Java - не было ни C++, ни OpenSolaris. В целом, всё получилось для меня вполне познавательно - как для человека, лет 15 писавшего на C/C++, и с миром Java соприкоснувшегося относительно недавно.


Детальный обзор инструментов платформы JavaEE 6
Поскольку с данным зверем работать мне не приходится, слушал в основном для расширения кругозора и практики в английском языке. Да и в параллельных секциях ничего интересного не было :)

Low Latency Development Techniques for Financial Systems, доклад компании Deutsche Bank
Интересный доклад о том, как люди написали трейдинговую систему на Java, используя C-style. С большим количеством велосипедов, бинарным логированием, и оптимизацией всего чего только можно. Обсуждение в основном свелось к философским вопросам "а зачем?" и "почему не C++?"

Диагностирование проблем и настройка GC в HotSpot JVM под нужды конкретного Java приложения
О том, какие грабли таит в себе сборщик мусора, если его неправильно настроить. Есть слайды.

Производительность Java-платформы
Снова о граблях - на этот раз в основном в JIT. Есть слайды.

Искусное тестирование производительности
А в этом докладе коллекция рассмотренных граблей включала как две предыдущие, от GC и JIT, так и разного рода методологические и естественнонаучные :)

Project Coin: незначительные, но полезные изменения языка в JDK
Про JDK7, JDK8, JDK9, далее везде. Предварительно демонстрировался слайд - "мы вам ничего не обещаем и не гарантируем, эта презентация просто разговор о том, что, может быть, будет реализовано".

Dual-Pivot Quicksort и Timsort, или как сортировка в JDK 7 стала еще быстрее
Про двухопорную быструю сортировку и новую вариацию на тему MergeSort. Много магии и эмпирики. Запомнился факт, что двухопорную сортировку рассматривал ещё сам Хоар (меня поправляют - это был Роберт Седжвик), только она ему чем-то не понравилась. Тестовые наборы у него другие были :)

Будущее JVM Hotspot
А этого доклада не было. Все уже зашли в зал, и тут организаторы извинились, и всё внезапно отменилось.

mVAS продукты на базе JavaCard: use cases
Ещё один доклад для расширения кругозора. Узнал про JVM, которая живёт на сим-карте. Теперь никогда не спутаю её с обычной телефонной J2ME.

Фантом - персистентная ОС для управляемого кода
Рассказ [info]dz про Фантом. К сожалению, времени на доклад было явно недостаточно - всего 20 минут, и без слайдов.

Java Persistence API 2.0: Обзор
Напоследок послушал ещё один доклад про могучего зверя J2EE.
winpooh: (Default)
Recent Progress in Quantum Algorithms - статья о новых квантовых алгоритмах. То есть о тех, что появились после ставших уже "классическими" алгоритмов Шора и Гровера. Изложение популярное, вполне доступное всем, кто знаком с основами квантовой механики. У меня наконец-то оформилась некоторая иллюзия понимания того, как работает квантовый поиск в базе данных, и почему он быстрее обычного (да-да, всё дело в отсутствующем корне из t для броуновского движения...)

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

Красивая картинка - не абстрактная фантазия художника, и даже не сферический конь, а самая настоящая сфера Блоха.

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

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

winpooh: (Default)
Узнав из журнала [livejournal.com profile] avva про юбилей Мартина Гарднера,
вспомнил одну из любимых игрушек своего детства.

Мартин ГАРДНЕР
Самообучающаяся машина из спичечных коробков

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)
Одна из самых ресурсоёмких задач в программировании шахмат - генерация траекторий дальнобойных фигур: слона, ладьи и ферзя. Её приходится реализовывать либо в виде цикла с большим количеством проверок (не вышли ли мы за пределы доски? не наткнулись ли на фигуру, свою или противника?), либо путём просмотра довольно объёмных, до мегабайта, таблиц с хитроумно устроенными индексами. И то, и другое - не слишком экономичные по времени операции.

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

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

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

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

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

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

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

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

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

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

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


Всё это происходило в 1963-м. Шахматисту, которого через 34 года Deep Blue обыграет в историческом матче, исполнилось на тот момент шесть месяцев.
Кросс-пост в Берлогу 2.0.
winpooh: (Default)
Среди программистов на C/C++ широко известны соревнования на самый запутанный код, делающий тем не менее осмысленные вещи - Obfuscated C contest и ему подобные.
Программа, о которой пойдёт речь, по запутанности стоит где-то между "нормальным" кодом и типичными участниками IOCCC. Вот, к примеру, как в ней выглядит функция main():

main()
{
 int j,k=8,*p,c[9];
 F(i,0,8)
 {b[i]=(b[i+V]=o[i+24]+40)+8;b[i+16]=18;b[i+96]=9;   /* initial board setup*/
  F(j,0,8)b[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5);   /* center-pts table   */
 }                                                   /*(in unused half b[])*/
 F(i,M,1035)T[i]=random()>>9;
 W(1)                                                /* play loop          */
 {F(i,0,121)printf(" %c",i&8&&(i+=7)?10:n[b[i]&15]); /* print board        */
  p=c;W((*p++=getchar())>10);                        /* read input line    */
  N=0;
  if(*c-10){K=c[0]-16*c[1]+C;L=c[2]-16*c[3]+C;}else  /* parse entered move */
   D(k,-I,I,Q,1,1,O,8,0);                            /* or think up one    */
  F(i,0,U)A[i].K=0;                                  /* clear hash table   */
  if(D(k,-I,I,Q,1,1,O,9,2)==I)k^=24;                 /* check legality & do*/
 }
}


Автор программы, голландец H.G.Muller, поставил себе целью написать шахматный движок, рейтинг которого будет больше числа символов в С-коде. Это ему удалось. Размер исходника только 1433 байта, при этом Micro-Max играет примерно на 2000 пунктов Эло - неплохой спарринг-партнёр для перворазрядников или даже кандидатов в мастера.

Кроме исходного текста на сайте Micro-Max размещены и подробные комментарии - в них разъясняется, что делает каждая строчка, как кодируется информация о доске и фигурах, как работают поиск и оценка и т.п.

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

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 Jul. 23rd, 2017 08:34 am
Powered by Dreamwidth Studios