Показаны сообщения с ярлыком игры. Показать все сообщения
Показаны сообщения с ярлыком игры. Показать все сообщения
пятница, 19 июня 2009 г.
Машинный разум нанёс человеку удар в го
Фора в семь камней и соперник девятого про-дана вам о чём-то говорят? Нам тоже. Между тем речь идёт о старейшей игре в мире, ведущейся на доске. И мир взбудоражен: программы смогли побороть профессиональных игроков самого высокого уровня. За результатом, который интересен, казалось бы, только фанатам, стоит колоссальный труд в области искусственного интеллекта. Мы сдаём "кремнию"?
Китайские легенды датируют рождение го началом второго тысячелетия до нашей эры. Эта древняя игра, пожалуй, даже более сложна, чем шахматы. Уж для машинного интеллекта она определённо сложнее. Тем ярче достижение компьютерщиков.
В феврале на престижном турнире по го Taiwan Open 2009 компьютерная программа MoGo обыграла двух профессионалов в битве на гобане 19 х 19. С гандикапом в 7 камней она победила игрока девятого дана Дзюньсюнь Чжоу (Jun-Xun Zhou), а с форой в 6 камней сломила сопротивление игрока первого дана Личэнь Чиэня (Li-Chen Chien).
Девятый дан, заметим, это предел мастерства, профи высшей пробы. Учитывая фору, данную машине, можно сказать, что она выступила на уровне если не профессионала, то самого сильного любителя.
Существует несколько вариаций правил го (японские, китайские, американской ассоциации го и ряд других). Отличаются они в деталях, касающихся применения форы, ряда правил, действующих в ходе игры, и также подсчёта очков в конце сражения, а ещё – правилами определения ранга игроков.
Ранги (кю и даны) влияют на начальные условия игры: если встречаются соперники разного уровня, слабому даётся фора в виде нескольких камней, которые тот выкладывает на доску до первого хода противника.
В основном считается, что разница в ранге на одну единицу компенсируется одним камнем гандикапа, но в Китае, Японии и Корее в ранжировании профессиональных игроков предполагается, что разница в один дан соответствует только трети камня форы, то есть уровни мастерства идут плотнее. И это впечатляющее достижение. Лет пять назад программы го могли уверенно выигрывать исключительно у детишек, недавно приступивших к изучению этой мудрой стратегической игры. С обычными любителями те же программы играли на равных, ну а профессионалам машины бесславно "сливали", даже имея гандикап в 25 камней.
И ещё год-полтора назад уровень программ оставался сравнительно скромным. Несколько случаев побед машин в отдельных партиях над суперпрофи имели место при большем (чем в 2009-м) гандикапе, либо при играх на уменьшенном поле (9 х 9).
Основные правила го не столь уж сложны. Упрощённо говоря, задача игроков сводится к окружению камней противника своими камнями. Но игра эта обладает большой "глубиной" – вариантов действий в ответ на ходы соперника – огромное количество, а вариантов тактики даже в локальных сражениях (вокруг одной из групп камней) – ещё больше. Можно констатировать: пал бастион, который долгое время считался одним из последних примеров превосходства живого разума над машинным. Пусть программы для игры в го (Computer Go, смотрите также computer-go.info) практически не уступают в длительности своей эволюции шахматным программам, многие специалисты утверждали, что в го машина никогда не победит игрока-человека, входящего в число сильнейших в данной дисциплине на планете.
Причина в том, что особенности игры (в сравнении с теми же шахматами) позволяют человеку сравнительно просто видеть очень длинные последовательности возможных ходов, выстраивая на этой основе хитроумные тактику и стратегию (а вот это уже совсем непросто). Но программа не может мыслить как человек, она механистична, а её выбор ответного хода — результат перебора вариантов, а не творческое решение проблемы.
"Софтинки", способные хоть как-то играть против человека, появились очень давно, но что важнее — уже в конце 1990-х были созданы программы, способные сражаться с чемпионами мира и даже выигрывать у них. Легендарная первая игра в матче Гарри Каспарова против машины (Deep Blue – Kasparov 1996) тому пример.
Чемпион, упустив эту одну игру, выиграл в том году весь матч, но через год усовершенствованная Deep Blue победила Каспарова уже окончательно (Deep Blue – Kasparov 1997).
Интуиция, опыт, знание огромного числа игр прошлого, подкреплённые образным, чисто человеческим мышлением, которое так трудно формализовать, уступили в тот раз "железке" Deep Blue, способной перебирать по 200 миллионов позиций в секунду.
Перебирать, впрочем, не тупо. Ведь общее число возможных положений фигур в шахматах колоссально, а значит, машине нужен был алгоритм, позволяющий "разумно" выбирать среди множества вариантов продолжения наиболее перспективные.
Шахматный автомат Turk, построенный в 1770 году, был лишь мечтой о машинах, способных побороть человека в древней игре. Но хотя он являлся обманом (а играл за "турка" ловко спрятанный человек), владельцам аппарата удавалось морочить публике головы много-много лет (иллюстрация с сайта wikipedia.org).
Естественно, что программу компьютерщикам помогали готовить люди, досконально знающие шахматную теорию. Так что можно сказать, что в 1997 году гроссмейстер проиграл не суперкомпьютеру, но коллективному разуму множества людей, и это некоторое утешение для человечества в целом. А слабым утешением лично для Каспарова оказались ничейные матчи с двумя другими, не менее коварными программами, проведённые в 2003-м.
Вообще же после матча 1997 года новые игры сильнейших шахматистов-людей против сильнейших программ продолжились, но уже не вызывали такого высокого интереса, как раньше. В 2002 году "кремниевый шахматист" Deep Fritz сыграл с Владимиром Крамником вничью, а в 2006-м та же программа победила-таки и этого чемпиона.
Примерно на равных с сильнейшими "сапиенсами" бездушные игроки научились выступать в 1990-м. Но позже компьютерным гениям удалось пойти ещё дальше, чем в шахматах. В последних у человека всегда остаётся шанс на выигрыш у машины. А вот в шашках такого шанса у нас уже нет.
В 2007 году шашки оказались полностью "взломанными", то есть были просчитаны на суперкомпьютере все их возможные ходы и комбинации. Благодаря этому последняя версия шашечной программы Chinook – она, кстати, и играла в 1990-х с чемпионом мира Мэрионом Тинсли (Marion Tinsley) – стала беспроигрышной. То есть ни один человек у неё не сможет выиграть никогда, поскольку машина в абсолютно любой позиции всегда знает самый лучший ход.
С шахматами такой "взлом" едва ли возможен в обозримом будущем. Число всех возможных позиций на шахматной доске (не противоречащих правилам, скажем, двух королей вы не можете поставить рядом) составляет ориентировочно 10^46 (в шашках порядок куда скромнее — 10^20), потому лучшие суперкомпьютеры планеты сообща не переберут их всех поочерёдно даже за время, на многие порядки превышающее возраст Вселенной.
Сможем ли мы лет через 50 нарастить производительность суперкомпьютеров на много-много порядков или придумать способ "взлома" шахмат в обход полного перебора?
Это большой вопрос. Но что уж тогда говорить об игре в го? Тут магия больших чисел просто подавляет любого, кто пытается "с линейкой" измерить глубину возможных ходов.
По словам Дэвида Дошея (David Doshay) из Калифорнийского университета в Санта-Круз (UCSC), ведущего собственное исследование го и к тому же создавшего ещё одну го-программу SlugGo, число возможных конечных позиций в партии го (на стандартном поле 19 х 19) составляет 10^171. И к ним можно прийти одним из 10^1100 путей!
Это число столь велико (сравните — сумма всех элементарных частиц во Вселенной составляет "всего" 10^80), что прямой перебор всех вариантов игры абсолютно невозможен.
Историческая родина го – Китай. Точное время появления этой игры неизвестно, но, так или иначе, случилось это ещё до нашей эры.
Наибольшей популярностью го пользуется в Корее, Китае, Тайване и Японии. Там же живут сильнейшие игроки мира. Получив запись ходов для каждой игры из этих миллионов, программа составляет статистику – какие первые ходы с большей вероятностью ведут к выигрышу.
У человека за выбор хода в го отвечает интуиция, помноженная на распознавание образов. Работает визуальная аналогия (эта форма группы влияет на эту часть доски, эта конфигурация опасна, и так далее). Человек мыслит категориями жизни, эволюции и смерти групп камней на доске. Он узнаёт знакомые конфигурации, даже если они лишь близки к когда-то виденным. Он учится обобщать образы (вот камни выстроены в цепочку, вот кольцо с разрывом на боку, вот ещё что-то). Образность и помогает человеку принимать решения за разумное время.
суббота, 13 июня 2009 г.
пятница, 15 мая 2009 г.
Физика
15 мая 1859 родился Пьер Кюри (Pierre Curie), французский физик, лауреат Нобелевской премии по физике 1903 года. Кюри родился в Париже, в семье врача. Получил домашнее образование. В возрасте 16 лет получил ученую степень бакалавра Парижского университета, а спустя еще два года стал лиценциатом физических наук. С 1878 работал вместе со старшим братом Жаком в минералогической лаборатории Сорбонны. Вдвоем они открыли пьезоэлектрический эффект. В 1895 г. Кюри женился на Марии Склодовской, студентке из Польши. Начиная с 1897 г. они исследовали явление радиоактивности. В 1903 г. Шведская королевская академия наук присудила Пьеру и Марии Кюри Нобелевскую премию по физике за 1903 год. Пьер и Мария Кюри получили половину награды «в знак признания ... их совместных исследований явлений радиации, открытых профессором Анри Беккерелем». В октябре 1904 г. был назначен профессором физики Сорбонны. В 1905 г. был избран Академиком во Французскую академию наук. Специально для него в Парижском университете была образована кафедра общей физики и радиоактивности.
19 апреля 1906 Кюри, переходя в дождливый день улицу в Париже, поскользнулся и попал под экипаж. Колесо телеги раздавило ему голову, смерть наступила мгновенно. В 1995 г. его прах вместе с прахом жены был захоронен в Пантеоне.
Наконец-то нашел флешку, в которую давно играл. Подошло бы к узлам. Попробуйте распутать. Правила проста, передвигаем точки так, чтобы линии не пересекались.
воскресенье, 10 мая 2009 г.
Образование.
10 мая 1956 — В СССР отменена плата за обучение в старших классах средних школ.
До сих пор считаю, что в СССР было самое клевое образование. Умели учить. У меня отец - педагог. Спасибо ему за все, чему он меня научил.
Несколько фраз "Кто хочет, тот ищет возможность, кто не хочет, тот ищет причину".
"Образование — это то, что у вас останется, когда вы забудете всё, чему учились"— Б. Ф. Скиннер
Флешка. Нужно довести чувачка, до заряжающего устройства, чем-то напоминает леммингов(если кто играл).
четверг, 7 мая 2009 г.
Пентиум
Помимо Дня Радио 7 мая, именно в этот день в 1997 году — компания Intel официально представила микропроцессор Pentium II. Официальную версию его появления не буду писать, а вот альтернативная весьма интересна. В 1980-х годах в России над процессором «Эльбрус» трудился Владимир Мстиславович Пентковский, который работал при РАН под руководством Бабаяна. Примерно в 1989 делегация от Intel посетила лаборатории Вычислительной техники РАН, где встретилась с Пентковским. Пентковский получил приглашение приехать по обмену опытом в США в исследовательский центр Intel. Из этой поездки в Россию Пентковский не вернулся, а через несколько месяцев Intel официально заявила о разработке принципиально нового процессора под названием Pentium (назван в честь разработчика ). Вот так-то.
И флешка как всегда.
четверг, 30 апреля 2009 г.
Домино
Вот одна логическая игра в домино. Правила просты, расположить доминошки в квадрате 8*8, так чтобы не повторялись.
Домино - небольшие пластинки, по традиции изготавливавшиеся из слоновой кости или просто кости с небольшими круглыми вставками черного дерева. Время происхождения домино - приблизительно около 1120 до н.э. Оно, хотя и достаточно распространено на Западе, на самом деле является китайским изобретением. Произошло от игральных костей, которые были ввезены в Китай из Индии в далеком прошлом.
Есть версия, что игру в домино создали монахи-доминиканцы. Во-первых, так называлась одежда духовных лиц - преимущественно черный плащ с капюшоном. Во-вторых, само название игры в домино происходит от латинского корня “dominans”, что означает - господствующий, главный и является началом обращения в католической мессе: “Dominus vobiscum” (Господь да пребудет с вами”). Выдвинуто предположение, что в домино зашифрована господствующая система устройства мироздания - Универсальный Закон Гармонии макро- и микрокосмоса : игра в домино имеет семь цифровых знаков ( от 0 до 6 ), что символизирует, в частности, семь планов бытия и семеричное строение Вселенной.
Игра в домино была широко распространена чуть ли не во всех средневековых монастырях. Когда же какому-нибудь монаху случалось одолеть своего соперника, то он с радостью восклицал “Бенедициамус Домино” (“Слава Богу”) или “Домино Гратиас” (“Благодарю Господа”). Отсюда, по-видимому, и происходит это название.
Каждая косточка домино первоначально представляла собой результат бросания двух игральных костей. Одна половинка домино представляет результат бросания одной кости, вторая - другой. В китайские комплекты были введены дубликаты,
они состоят из двух комплектов: военного и гражданского. Китайское домино длиннее, чем типичное европейское.
В Корее и Индии домино до сих пор служит инструментом для предсказания судьбы. Вообще, первоначально эти костяшки предназначались исключительно для гадания и магических церемоний. Ведь азарт и божественное откровение - “две вещи несовместные”.
На Востоке известно 47 различных игр с использованием домино. Существуют домино с цветными костяшками, где цвет обозначает достоинство. Названия игр чрезвычайно поэтичны: ”гвоздики в тумане”, “войти в пагоду”, “прыжок газели”.
Примерно в XVIII веке домино прибыло в Европу, когда оно появилось в Италии. Удивительно, что это заняло так много времени, ведь установление Великого Шелкового Пути произошло задолго до этого. При переходе в европейскую культуру игра частично видоизменилась. Европейские комплекты не содержат ни различных классов костей, ни дубликатов. Вместо этого у них есть семь дополнительных домино, в которых одна из половинок - с изображением “пусто”.
Интересно, что американские эскимосы также играют в игру, использовавшую фишки, очень напоминающие домино. Это очень странно, если не предположить некоей связи, существовавшей в древности между Китаем и Америкой.
В настоящее время существует большое разнообразное количество игр, основанных на этих,вроде бы простых костяшках.
Многие из этих игр появились уже в ХХ веке....
Домино - небольшие пластинки, по традиции изготавливавшиеся из слоновой кости или просто кости с небольшими круглыми вставками черного дерева. Время происхождения домино - приблизительно около 1120 до н.э. Оно, хотя и достаточно распространено на Западе, на самом деле является китайским изобретением. Произошло от игральных костей, которые были ввезены в Китай из Индии в далеком прошлом.
Есть версия, что игру в домино создали монахи-доминиканцы. Во-первых, так называлась одежда духовных лиц - преимущественно черный плащ с капюшоном. Во-вторых, само название игры в домино происходит от латинского корня “dominans”, что означает - господствующий, главный и является началом обращения в католической мессе: “Dominus vobiscum” (Господь да пребудет с вами”). Выдвинуто предположение, что в домино зашифрована господствующая система устройства мироздания - Универсальный Закон Гармонии макро- и микрокосмоса : игра в домино имеет семь цифровых знаков ( от 0 до 6 ), что символизирует, в частности, семь планов бытия и семеричное строение Вселенной.
Игра в домино была широко распространена чуть ли не во всех средневековых монастырях. Когда же какому-нибудь монаху случалось одолеть своего соперника, то он с радостью восклицал “Бенедициамус Домино” (“Слава Богу”) или “Домино Гратиас” (“Благодарю Господа”). Отсюда, по-видимому, и происходит это название.
Каждая косточка домино первоначально представляла собой результат бросания двух игральных костей. Одна половинка домино представляет результат бросания одной кости, вторая - другой. В китайские комплекты были введены дубликаты,
они состоят из двух комплектов: военного и гражданского. Китайское домино длиннее, чем типичное европейское.
В Корее и Индии домино до сих пор служит инструментом для предсказания судьбы. Вообще, первоначально эти костяшки предназначались исключительно для гадания и магических церемоний. Ведь азарт и божественное откровение - “две вещи несовместные”.
На Востоке известно 47 различных игр с использованием домино. Существуют домино с цветными костяшками, где цвет обозначает достоинство. Названия игр чрезвычайно поэтичны: ”гвоздики в тумане”, “войти в пагоду”, “прыжок газели”.
Примерно в XVIII веке домино прибыло в Европу, когда оно появилось в Италии. Удивительно, что это заняло так много времени, ведь установление Великого Шелкового Пути произошло задолго до этого. При переходе в европейскую культуру игра частично видоизменилась. Европейские комплекты не содержат ни различных классов костей, ни дубликатов. Вместо этого у них есть семь дополнительных домино, в которых одна из половинок - с изображением “пусто”.
Интересно, что американские эскимосы также играют в игру, использовавшую фишки, очень напоминающие домино. Это очень странно, если не предположить некоей связи, существовавшей в древности между Китаем и Америкой.
В настоящее время существует большое разнообразное количество игр, основанных на этих,вроде бы простых костяшках.
Многие из этих игр появились уже в ХХ веке....
среда, 29 апреля 2009 г.
Ход конем
Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.
Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года). В письме к Гольдбаху он сообщал: «…Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб.» Помимо рассмотрения задачи для коня, Эйлер разобрал аналогичные задачи и для других фигур.
В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня. Задача отыскания гамильтонова пути в графах является известной NP-полной задачей.
Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532 [1] (количество замкнутых маршрутов с учётом направления в два раза больше). В то же время задача подсчёта всех возможных незамкнутых маршрутов значительно сложнее и не решена до сих пор. Известно, [2] что количество незамкнутых маршрутов не превышает числа сочетаний 1,2*10^47
Материал из Вики
Ну и флешка, почти на эту тему
Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года). В письме к Гольдбаху он сообщал: «…Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб.» Помимо рассмотрения задачи для коня, Эйлер разобрал аналогичные задачи и для других фигур.
В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня. Задача отыскания гамильтонова пути в графах является известной NP-полной задачей.
Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532 [1] (количество замкнутых маршрутов с учётом направления в два раза больше). В то же время задача подсчёта всех возможных незамкнутых маршрутов значительно сложнее и не решена до сих пор. Известно, [2] что количество незамкнутых маршрутов не превышает числа сочетаний 1,2*10^47
Материал из Вики
Ну и флешка, почти на эту тему
пятница, 24 апреля 2009 г.
Без тормозов
В эту игрушку играл давно, правда в другом оформлении. У бегунка нет тормозов, то есть он не остановится пока не наткнется на препятствие. Затягивает не по детски
четверг, 23 апреля 2009 г.
Гравитация 2 и Рождение Спектрума
Продолжение вчерашней флешки, теперь в цвете. Смысл тот же - попробуй не упустив мяч, добраться до места назначения.
Кстати, именно 23 апреля 1982 года выпустили компьютер ZX Spectrum. У меня был ZX Spectrum 48. Эти игры на аудиокассетах, загружающиеся под страшный скрежет. Одна из моих самых любимых игр была Lode Runner. Она была четвертой на стороне Б на моей первой игровой касете, я знал весь ее скрежет наизусть.
Кстати, именно 23 апреля 1982 года выпустили компьютер ZX Spectrum. У меня был ZX Spectrum 48. Эти игры на аудиокассетах, загружающиеся под страшный скрежет. Одна из моих самых любимых игр была Lode Runner. Она была четвертой на стороне Б на моей первой игровой касете, я знал весь ее скрежет наизусть.
среда, 22 апреля 2009 г.
Гравитация
Игра на тему гравитации. Опять терпения не хватает. Изначально все просто, но с каждым уровнем приходиться подключать мозг все больше и больше.
суббота, 18 апреля 2009 г.
Portal
Официальный трейлер новой игры–головоломки Portal от VALVE, выходящей в октябре 2007 года в одном комплекте с HL2–ep.II. Гейм–сообщество столкнется с поистине уникальной и необычной игрой. Она позволяет, используя т.н. Portal–Gun и эффект тоннельного перехода, познакомиться с принципами перемещения в 4–мерном пространстве, в частности, в квазигиперкубе. Возможности для задействования интеллекта — безграничные. Только не сломайте его, увидев самого себя, бегущего за вами. Разработкой игры занималось какое–то полусекретное спецподразделение VALVE — ApertureScience, на сайте которого без знания DOS–команд делать нечего. Мистического тумана добавляют безуспешные попытки предшественников. Для погружения в тему советую послушать запись эфира с крупнейшим теоретиком квантовой телепортации (эффекта Эйнштейна–Подольского–Розана) итальянским профессором Л.Аккарди (MP3, 35 Мб, есть стенограмма) и теорией струн. А в этом ролике можно увидеть применение Portal–Gun в привычном окружении — наглядная картина бесконечно падающих бульдозеров из "Града обреченного" Стругацких. Люди придумали игру для инопланетян? Похоже на то. Theres'a hole in the sky, through which things can fly.
четверг, 16 апреля 2009 г.
Объем
Наткнулся давеча на огромный ресурс забавной математики MatchNet, где находится большое разнообразие интересных задачек, упражнений и игр (опять на буржуйском языке, когда я его выучу?). Вроде бы и более нечего о нем сказать, если бы не пространственные головоломки, убил почти 5 часов на это. Для любителей черчения и геометрии. Удачи
Подписаться на:
Сообщения (Atom)
