Логические игры

Вторая серия о многолетней борьбе Каспарова с армадой терминаторов. Первую статью из цикла читайте здесь.

Шахматные программы считали с каждым годом всё быстрее и всё адекватнее оценивали позиции, в том числе и не изобилующими тактическими ударами. Алгоритмы совершенствовались и боты достигли успехов, выигрывая не только в комбинационном, но и в позиционном ключе. Компьютерные игроки почти излечились от жадности и если люди жертвовали материал, то роботы, ради восстановления игрового баланса, троянских коней с легким сердцем отправляли обратно.

Участие компьютеров в человеческих соревнованиях вошло в моду. IT-компании охотно и щедро спонсировали мероприятия, с непременным условием – роботы играют на тех же правах, что и люди. Особенно интересен 1994 год, в которых произошли несколько знаковых событий, когда внезапно компьютеры начали регулярно наносить людям чувствительные поражения.

История о нашумевшем противостоянии Каспарова с детищем IBM уже затрагивалась на GeekTimes Хабре. Мой комментарий хоть и набрал приличное количество плюсов, содержит несколько существенных неточностей, которые я уже исправить, увы, не в силах. Дабы внести ясность и расставить все точки над ё, было решено написать более подробную статью про этот знаковый матч. Однако в творческом процессе выяснилось, что затронутая тема гораздо обширнее, многограннее и интереснее, и охватывает куда больший период времени. А посему статья про матч 1997 года органично трансформировалась в серию публикаций о незаурядных победах и поражениях 13-го чемпиона мира в борьбе с искусственным разумом на протяжении 15 лет.

         Если используешь их в битве, но победа долго не приходит, их оружие притупляется, а рвение — ослабевает. Если осаждаешь города, их силы истощаются. Если подвергаешь войско длительной войне, запасов государства не хватит.
…
         Поэтому я слышал об успехе быстрых военных походов, и не слышал об успехе затяжных. Ни одно государство не извлекло выгоды из длительной войны.

Сунь Цзы "Искусство войны"
 
В предыдущей статье, я рассказал о том как выполняется захват камней в го, но не упомянул об одном правиле. Правило это столь важное, что имеет собственное имя — Ко.

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

Лао Цзы "Дао дэ Цзин"
 

Камни в Го одинаковы и после установки на доску их нельзя двигать. Кажется, что это простая игра, но это не так. Простые правила ведут к невообразимому разнообразию тактических комбинаций. Проблематика «жизни и смерти» — хорошая тому иллюстрация.

На написание этого обзора натолкнул пост «Секрет древней игры го. Почему компьютер до сих пор не обыграл человека?», опубликованный 25 мая. В самом посте, и, тем более, в комментариях, было много сказано по поводу компьютерных шахмат вообще и матча Deep Blue — Каспаров (1997) в частности. Понятно, что сейчас, спустя уже без малого двадцать лет, мало кому интересны все подробности того матча: компьютеры развиваются с колоссальной скоростью, современные смартфоны легко дадут фору компьютерам того времени, да и возможно, сами шахматы несколько утратили популярность последнее время — по каким причинам — это уже тема отдельного разговора.

Впрочем, некоторые подробности, судя по всему, действительно неизвестны, а подробности эти таковы, что заголовки о “падении последнего интеллектуального бастиона” — не более, чем газетный прием, ибо случившийся по итогам матча, по сути, скандал, в силу своей шахматной специфичности вряд ли был бы интересен широкой публике. Нет, я, несмотря на то, что всегда являлся поклонником Гарри Кимовича Каспарова (исключительно в шахматном плане), не собираюсь его оправдывать за то поражение и пытаться доказать, что все было совсем не так, как сейчас общеизвестно. И уж тем более целью не является опровержение некоторых комментариев на шахматную тему к посту хабраюзера alizar. Единственная цель — рассказать некоторые подробности того, что именно произошло в Нью-Йорке в начале мая 1997 года, и почему результат этого противостояния, по мнению автора, на самом деле никому ничего не доказал.

Чемпион мира по шахматам, юный Магнус Карлсен сыграл с Биллом Гейтсом в суперблиц в эфире скандинавского телеканала NRK и поставил ему мат девятым ходом.

Многие знакомы с проектом Seti@home: мощнейшей инициативой по поиску следов внеземных цивилизаций в океане данных, получаемых с неба, с использованием мощностей миллионов компьютеров по всему земному шару («матрицы»).

Хотя инопланетян до сих пор не обнаружили, Seti@home вполне успешно демонстрирует потенциал крупномасштабных распределенных вычислений. Проекты типа BOINC распространили подобные инициативы в другие области: биологию, медицину и физику.

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



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

Толчком к написанию статьи послужила статья habrahabr.ru/blogs/algorithm/105450 автора lightcaster, который занимается (похоже это интересное хобби) тем, что интересно моей команде в проекте foxyevents.de (не сочтите за рекламу) с предложением вступить к нам в команду разработчиков. Т.к. на Хабре нет способа написать этому человеку «извне», приходится написать свою собственную интересную (надеюсь) статью.

В классических шахматах при всех их несомненных достоинствах существует один «недостаток», о котором знают (либо догадываются) даже начинающие шахматисты: игрок, имеющий белые фигуры, ходит первым, что даёт ему «преимущество» над соперником. Данное «преимущество» не является особо значительным при игре двух любителей, но становится существеннее, когда за шахматную доску садятся более опытные игроки.

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

Спустя более чем 25 лет после своего создания тетрис остаётся самой популярной мобильной игрой в истории. Гениальное российское изобретение продолжает покорять мир, а недавно количество мобильных загрузок тетриса превысило 100 млн (имеются в виду только платные загрузки, за которые были уплачены роялти правообладателям).

В настоящее время права на продажу самой успешной игры принадлежат корпорации Electronic Arts. Лицензию она получила у компании Blue Planet Software. Сегодня эти две фирмы планируют организовать в Монреале (Канада) торжественное мероприятие, посвящённое юбилею.

Выяснять что лучше: Mac или PC дизайнер Adam Frederick предлагает не на форумах, на за шахматной доской. Соответствующую случаю доску он уже нарисовал. Правда, сдается мне, что форма подставки указывает на то, что художник был не совсем беспристрастен.

via coroflot.com

Тут в некоторой теме в комментариях начался спор в духе Counter-Strike 1.6 vs Call of Duty | [place any other modern FPS here]. Я думаю, что на Хабре есть киберспортсмены, заядлые геймеры, да и просто казуалы, играющие часок время от времени после работы. Так что, надеюсь, тема сразу не уйдет -∞, хоть я и рискую.

WARNING. Сравнение не идет со старыми играми завоевавшими себе киберспортивную популярность, как например Q3. И тем более уж не со старкрафтом или варкрафтом. Говорится о сравнительно новых командных играх, игроки в которые презрительно относятся к CS 1.6.

Здесь и далее под CS будет подразумеваться Counter-Strike 1.6, FPS расшифровывается как First Person Shooter.

Я в свои лучшие годы долго с переменным успехом играл в CS и считаю себя экс- киберспортсменом. Особых успехов не добивался, но имел некоторый опыт и фан участия в турнирах локального и областного характера. Всю кухню киберспорта прекрасно себе представляю, и не только CS.

Я считаю, что CS был и есть идеальным командным киберспортивным FPS, его состояние на текущий день является чрезвычайно сбалансированным и не требует никаких вмешательств кроме парочки незначительных фиксов. Очень часто сталкиваюсь с людьми, которые поливая грязью CS выставляют фишки неких других wannabe киберспортивных FPS как несомненные достоинства и преимущества над ним. Так вот, что я хочу сказать…

Фишка набора «Шахматы для Теслы» – то что играть надо настоящими вакуумными лампами. Дизайнер – Paul Fryer, год разработки – 2008, размеры доски – 17x48x50cm. Всего сделано семь комплектов, поэтому купить набор, к сожалению, почти невозможно.

Интереснейшую реализацию шахматной программы показали вчера на Хабре.
Почитав комментарии, я пришел к выводу, что принцип работы наиболее распространенных алгоритмов игры в шахматы, шашки и тому подобные известны не всем.

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

Клик на картинку:

Знаете ли вы, что в Google Spreadsheets при одновременной работе нескольких человек над одним документом изменения синхронизируются так быстро, что можно вполне комфортно играть в крестики нолики через интернет?

Компьютерная программа Deep Fritz обыграла чемпиона среди людей по шахматам со счетом 4:2. Электронный разум выиграл две игры, а четыре были сведены к ничьей.

Шестая партия длилась пять часов и закончилась на сорок седьмом ходу победой искусственного интеллекта. В ходе интервью, начавшегося сразу после матча, Крамник признался, что он «немного расстроен», однако через год или два можно будет устроить ещё один матч. По словам чемпиона мира по шахматам, если у него будет время подготовиться, то увеличатся шансы на выигрыш.

В 2002 году Крамник сыграл с компьютером вничью, однако с тех пор программное обеспечение было существенно обновлено, сообщает BBC.

Официальное открытие проекта Accoona состоялось в декабре 2004 г. Компания заключила соглашение с китайским правительством, а одним из инвесторов выступил фонд Билла Клинтона. Сам бывший президент присутствовал на церемонии торжественного открытия.