winpooh: (Default)
На Crestbook выложено интервью с гроссмейстером, обладателем Кубка Мира Борисом Гельфандом.

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



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

Успел как раз вовремя - к встрече Ананда с Карлсеном. Магнус партию выиграл, а через некоторое время оформил и победу в турнире. Ура новому чемпиону мира!
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)
Из многих легенд о происхождении Го мне особенно нравится вот эта.
Из книги А.Кузьмина "Солнце и снег", http://www.weichi.ru/publ/ukigata.htm
Читать... )
winpooh: (Default)
Одна из самых ресурсоёмких задач в программировании шахмат - генерация траекторий дальнобойных фигур: слона, ладьи и ферзя. Её приходится реализовывать либо в виде цикла с большим количеством проверок (не вышли ли мы за пределы доски? не наткнулись ли на фигуру, свою или противника?), либо путём просмотра довольно объёмных, до мегабайта, таблиц с хитроумно устроенными индексами. И то, и другое - не слишком экономичные по времени операции.

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

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

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

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

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

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

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

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

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

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

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


Всё это происходило в 1963-м. Шахматисту, которого через 34 года Deep Blue обыграет в историческом матче, исполнилось на тот момент шесть месяцев.
Кросс-пост в Берлогу 2.0.
winpooh: (Default)
К осьминогу, полученному пришиванием лишних ног собаке, добавлена ещё одна. Заодно для славной греческой буквы найдено самое естественное обозначение - квадратные скобки :))
http://herbsutter.spaces.live.com/Blog/cns!2D4327CC297151BB!785.entry
winpooh: (Default)
Кросс-пост в [livejournal.com profile] ru_go

В 2007-м году в мире компьютерного Го произошёл реальный прорыв - на малых досках программы достигли силы данов. Дело в том, что последние лет десять прогресса в силе игры практически не было - что на большой (19x19), что на малой (9x9) досках программы играли примерно на уровне 10-го кю. Классические "шахматные" алгоритмы (альфа-бета перебор на фиксированную глубину + ФВ + статическая оценка позиции) в Го не работали - прежде всего из-за невозможности понять, когда же позиция достаточно "успокоилась", чтобы её можно было статически оценивать (а главное - как?). Революция произошла с появлением алгоритма UCT.

По сути своей, UCT - это алгоритм из семейства Монте-Карло. Для каждого возможного по правилам хода делается большое количество (порядка десятков или сотен тысяч) симуляций - фактически, пробных партий, состоящих из случайных ходов за обе стороны. Итог этих партий (окончательный счёт очков по китайской системе) усредняется, и выбирается ход с наибольшим матожиданием. Всё!

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

Алгоритмы семейства UCT активно исследуются уже несколько лет, но только недавно появились их эффективные реализации. Лучшие из UCT-программ действительно играют на маленькой доске в силу дана - готов подтвердить лично! Я скрестил камни с программой MoGo. Родом она из Франции, автор недавно успешно защитил по ней PhD thesis и, увы, прекратил дальнейшую разработку. Есть, однако, надежда на продолжение - исходный код передан группе студентов, которые намерены продолжить исследования. Так вот, на то, чтобы начать время от времени обыгрывать MoGo на 9х9, у меня ушла пара дней. В длинной же серии партий я до сих пор не уверен в своей победе. Сейчас у меня на KGS третий кю. Так что у MoGo против неподготовленного противника - несомненно, уровень дана :))

Интересная особенность Го-алгоритмов, основанных на Монте-Карло - в выигранной позиции они начинают делать сверх-надёжные ходы, тем не менее не упускающие победу. Программа не делает различий между выигрышем в 30 очков и в пол-очка - в результате обычно именно 0.5...1.5 очка и выигрывает. Именно так всегда предпочитали делать в партиях с любителями японские профессионалы, у них это считалось показателем стиля! А вот выяснить, сколько очков MoGo в среднем проигрывает, мне не удалось - в безнадёжных позициях программа просто сдаётся.

Есть у MoGo и слабости - она плохо понимает живые формы накадэ в углу. Квадратик, пирамидка и автомобиль - ваши лучше друзья в пожирании групп этого монстра :)) Играть с MoGo надо надёжно, не пытаясь соревноваться с ней в тенуки. Если обоснованно отвечать её на угрозы - через несколько ходов в ваших руках волшебным образом оказывается сэнте. Попытки играть с MoGo в её же стиле, разбрасывая камни по доске, у меня были менее удачными.

На большой доске программа играет не так сильно, хотя по результатам KGS-версии держится где-то на уровне 2...3-го кю. В пробной партии на 19x19 против моего чёрного Китая MoGo разыграла несколько ходов по книжке, после чего принялась шлёпать камни на 5-ю и 6-ю линии. Продолжать партию с недо-Такемией я не стал - просто не хватило терпения. Ещё поэкспериментирую, но только после праздников, на свежую голову :))

По информации от автора, Linux-версия играет сильнее - так как лучше использует многопоточность.

Ссылки:
http://www.kiseido.com/download.htm - IgoWin: лучшая 9х9 программа эпохи до-UCT
http://senseis.xmp.net/?UCT - краткое описание алгоритма UCT + псевдокод
https://www.lri.fr/~teytaud/mogo.html - программа MoGo (свободно распростраяемые бинарники для Windows и Linux)
http://www.godrago.net/en.htm - GUI для движка. Обязательно прочитайте инструкции по установке на странице MoGo.
http://gogui.sourceforge.net - ещё один GUI (Java)

winpooh: (Default)
Для тех, кто. Между сайтом http://varmed.net и журналом [livejournal.com profile] nurt существует некоторая, совершенно неочевидная и в высшей степени загадочная связь.
winpooh: (Default)
Дошёл до первого дана на Го-сервере KGS. Причём намного раньше, чем предполагал ещё несколько месяцев назад. Конечно, инфляция рейтингов, да и специфика интернет-игры мне помогли. Но и своей заслуги преуменьшать не буду.

фото

Рейтинг дорос у новой учётной записи, которую я завёл в начале года. Как видно из картинки, превращение произошло после произнесения волшебного слова.
Интересно, что старый добрый аккаунт WinPooh пока ещё прочно пыхтит на уровне 3-го кю :)
winpooh: (Default)
Вторая, она же заключительная, часть казанских фотографий. Блиц-прогулка по Кремлю и около.

фото

http://pics.livejournal.com/winpooh/gallery/000071tp?page=2
winpooh: (Default)
Выложил первую часть казанских фотографий - игровой зал и его ближайшие окрестности.
http://pics.livejournal.com/winpooh/gallery/000071tp
winpooh: (Default)
Важная веха в развитии моей шахматной программы GreKo: её уже начинают клонировать :)
Некий автор из Эквадора выложил "свой" движок, заменив в GreKo пару строчек с информацией о копирайте. Оказалось, однако, что коммьюнити не дремлет - обман был раскрыт в удивительно короткий срок.
Подробности истории тут: http://216.25.93.108/forum/viewtopic.php?t=11037
winpooh: (Default)
В черте города ожидается 0…+2°, в центре Москвы +1…+3°, в Подмосковье от 0 до -х тепла.
http://news.gismeteo.ru/?newsitem=63302112520
winpooh: (Default)
По некоторой надобности собираюсь в ближайшее время посетить один из офисов МТС (нет-нет, не подумайте ничего плохого, я как был на Билайне, так на нём и останусь. Куда же мне без пчёл :))

Пока узнавал в инете адрес и как проехать, наткнулся на полезный документ - "Памятку посетителя офиса МТС". Которую немедленно и прочитал, в порядке моральной подготовки...


ПАМЯТКА ПОСЕТИТЕЛЯ ОФИСА "МТС"

Уважаемые посетители !
Напоминаем Вам, что:
1. Карточки Экспресс - оплаты продаются в кассе (направо, следующий зал).
2. "Положить на счет" можно там же.
3. Смена тарифа - напротив в службе сервиса.
4. "Заняться роумингом" - там же.
5. "Поставить роуминг" там же.
6. И вообще, там же находятся такие неизвестные науке звери как: "роулинг", "ромлинг", "ровинг" и "ромбик". И "РАМЭН" тоже!!!
7. Восстановление SIM-карты - там же.
8. Взять распечатку можно в службе фин. контроля (направо наискосок).
9. Все прайс-листы с новыми (и старыми) тарифами находятся на стойке.
10. Самого дешевого тарифа НЕ СУЩЕСТВУЕТ В ПРИРОДЕ !!!
11. Самого выгодного тоже.
12. И самого удобного тоже.(Есть только самый "рациональный", самый "локальный", самый "активный" и т.д.)
13. Инструкции к телефонам мы отдельно не продаем.
14. Карточек БИ+ у нас НЕТ!!!
15. И мы НЕ знаем где они продаются!!! !!!
16. Карточек МСС нет тоже!!!
17. Смотри пункт 15.
18. И карточек "СОНЕТ""а ТОЖЕ!!! !!! !!!
19. Смотри пункт 17.
20. И Интернет - карточек у нас ТОЖЕ НЕТ !!! !!! !!!
21. Что такое "Билайн" мы не знаем.
22. И НЕ подключаем к нему соответственно.
23. Здесь у нас - ТОЛЬКО "МТС".
24. Тариф "Юбилейный" есть только в МСС. "Экономичный" тоже.
25. Что такое МСС мы тоже не знаем.
26. В долларах мы НЕ "берем".
27. Произнося фразу типа ""МТС" ворует деньги" вы рискуете своей жизнью.
28. "Мегафон" - это устройство для усиления голоса.
29. Вопрос типа "Мне нужен телефон, чтобы за 300 км от Москвы брал" карается лекцией о принципах работы сетей GSM.
30. У всех аппаратов "чувствительность", "приемистость" и т.д. - одинаковые.
31. Тарифы "Без абонентской платы" существуют только в рекламе.
32. Б/Ушных телефонов у нас нет, и мы их не принимаем и не планируем..
33. Комплект "Таксафон" - это не компакт-диск
34. Миниклавиатура для Ericsson действительно стоит 58 рублей, это не опечатка
35. Телефоны мы НЕ заряжаем.
36. Если покупать 2 телефона сразу, скидки не даются.
37. Тариф "Летний" действует летом, осенью, возможно зимой, ну и весной пожалуй тоже.
38. Бляяяя! Как вы все достали!

Первоисточник: http://narod.gorodkirov.ru/showThread?thr_id=7726&frm_id=14
winpooh: (Default)
По поводу приезда в Москву [livejournal.com profile] valchess виртуальной тусовке с http://kasparovchess.crestbook.com вчера вечером удалось собраться в составе [livejournal.com profile] bazar_wokzal, [livejournal.com profile] winpooh, уже упомянутого [livejournal.com profile] valchess и примкнувших к ним мм Макса Ноткина и гм Сергея Шипова. Присутствовали также программа GreKo и кот Лисик.

В числе прочего, удалось: 1) съесть арбуз 2) послушать много хорошей музыки 3) обсудить самые важные вопросы жизни, Вселенной и всего остального 4) убедиться в очередной раз, что программы играть не умеют, но всё равно выигрывают 5) подвигать пешки в разных режимах и разных составах, а также 6) вживую наблюдать рождение знаменитых онлайн-репортажей Сергей Шипова с сайта ChessPro.

Отдельным пунктом был оформлен демонстрационный выигрыш в 40 очков на пяти камнях форы у чемпиона мира 2005 года по компьютерному Го :)

фото

Игра пара на пару: Ноткин + Пух vs. Шипов + Валчесс. Кот нам судья.
winpooh: (Default)
Вчера ездили в паломническую поездку в Сергиев Посад.
Фотографий много, постепенно буду выкладывать.

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:52 am
Powered by Dreamwidth Studios