Программирование → Рейтинг на основании истории
Постановка задачи
Контекст: есть шахматный турнир с достаточно большим количеством игроков самого разного уровня.
Приняты решения: не разбивать игроков на чётко определённые группы (друг друга не знаем ещё, непонятно, кого куда помещать), не делать турнир «на вылет» (много новичков, им просто обидно будет вылететь после первой партии). Более-менее (вручную) справляемся с выбором партнёром примерно одинакового уровня.
Задача: сделать систему рейтинга по результатам турнира. Поскольку играем не «на вылет», финала нет. Учитывать количество очков несерьёзно из-за разношерстности игроков. То есть система рейтинга должна быть такой, что выигрыш у самого слабого игрока или проигрыш у самого сильного практически не должны влиять на наш рейтинг.
Искусственный интеллект → Chess@home: создаем крупнейший шахматный ИИ
Многие знакомы с проектом Seti@home: мощнейшей инициативой по поиску следов внеземных цивилизаций в океане данных, получаемых с неба, с использованием мощностей миллионов компьютеров по всему земному шару («матрицы»).
Хотя инопланетян до сих пор не обнаружили, Seti@home вполне успешно демонстрирует потенциал крупномасштабных распределенных вычислений. Проекты типа BOINC распространили подобные инициативы в другие области: биологию, медицину и физику.
Хотя инопланетян до сих пор не обнаружили, Seti@home вполне успешно демонстрирует потенциал крупномасштабных распределенных вычислений. Проекты типа BOINC распространили подобные инициативы в другие области: биологию, медицину и физику.
Ненормальное программирование → Сетевая игра на bash: шахматы
Я давно хотел написать какую-нибудь сетевую игру на bash, причём желательно, чтобы управление было удобное, с клавиатуры, обычными курсорным клавишами. Вообще, тема интерактивного взаимодействия в bash глубже, чем «введите число, нажмите „Enter“» не раскопана. Мне пришлось всё изобретать и исследовать самостоятельно. Я очень старался найти что-то похожее по уровню интерактивности, но не нашёл.
Поскольку тонкости управления с клавиатурой съели очень много моего времени, я не стал заморачиваться с тонкостями совместимости, поэтому игра тестировалась только под Mac OS X, есть ненулевая вероятность, что она заработает и под Linux и уж точно её можно допилить там до рабочего состояния.
Для работы игра требует наличия nc (aka Netcat) и терминала с поддержкой 256 цветов (под Mac OS рекомендую iTerm2). При наличие интереса к игре, допилю до терминала на 16 цветов и /dev/tcp. Кстати начал выкладывать все свои шел-поделки на ГитХаб.
Так как игра сетевая, у неё требуется указать два параметра, о которых она расскажет, если её запустить без них. Первый — адрес машины противника, второй — порт. Порт выбирается одинаковым на обеих машинах. Игру можно запустить и на одной машине, в двух консолях (на скриншоте как раз такой случай).
Играть просто — в каждый момент времени активна только одна доска (на скриншоте — правая, у неё буквы и цифры вокруг доски ярче), на активной доске курсор двигается курсорными клавишами — ←, →, ↑ и ↓, взять фигуру и поставить её на доску — по клавише пробела или Enter. Как только вы поставили фигуру на доску, ход переходит к сопернику. «Съесть» фигуру соперника проще простого — достаточно поставить свою фигуру на чужую. В игре есть защита — нельзя «съесть» свою фигуру.
Ничего помимо этого в игре нет — не производится правильность контроля ходов, нет проверки на завершение игры, можно даже ходить фигурами соперника. Было очень сложно придумать как обрабатывать нажатия в shell, так что остальное сделать я просто не успел, не поместилось в формат «игрушка за вечер».
Я постарался снабдить свой код комментариями и писать достаточно структурировано, чтобы можно было разобраться как всё работает самостоятельно.
Поскольку тонкости управления с клавиатурой съели очень много моего времени, я не стал заморачиваться с тонкостями совместимости, поэтому игра тестировалась только под Mac OS X, есть ненулевая вероятность, что она заработает и под Linux и уж точно её можно допилить там до рабочего состояния.
Для работы игра требует наличия nc (aka Netcat) и терминала с поддержкой 256 цветов (под Mac OS рекомендую iTerm2). При наличие интереса к игре, допилю до терминала на 16 цветов и /dev/tcp. Кстати начал выкладывать все свои шел-поделки на ГитХаб.
Так как игра сетевая, у неё требуется указать два параметра, о которых она расскажет, если её запустить без них. Первый — адрес машины противника, второй — порт. Порт выбирается одинаковым на обеих машинах. Игру можно запустить и на одной машине, в двух консолях (на скриншоте как раз такой случай).
Играть просто — в каждый момент времени активна только одна доска (на скриншоте — правая, у неё буквы и цифры вокруг доски ярче), на активной доске курсор двигается курсорными клавишами — ←, →, ↑ и ↓, взять фигуру и поставить её на доску — по клавише пробела или Enter. Как только вы поставили фигуру на доску, ход переходит к сопернику. «Съесть» фигуру соперника проще простого — достаточно поставить свою фигуру на чужую. В игре есть защита — нельзя «съесть» свою фигуру.
Ничего помимо этого в игре нет — не производится правильность контроля ходов, нет проверки на завершение игры, можно даже ходить фигурами соперника. Было очень сложно придумать как обрабатывать нажатия в shell, так что остальное сделать я просто не успел, не поместилось в формат «игрушка за вечер».
Я постарался снабдить свой код комментариями и писать достаточно структурировано, чтобы можно было разобраться как всё работает самостоятельно.
Open source → Лучшая шахматная программа Rybka дисквалифицирована и лишена всех наград
В профессиональном спорте атлета могут дисквалифицировать за применение допинга, но за какую провинность можно наказать компьютерную программу? Оказывается, в мире компьютерного киберспорта, а именно, в шахматах, тоже суровые правила. Комиссия из 34 разработчиков шахматных движков приняла решение: многократный чемпион мира по шахматам, программа Rybka, признана виновной в плагиате исходных кодов из двух Open Source программ Crafty и Fruit.Теперь исполнительный комитет Международной ассоциации компьютерных игр требует у автора программы, мастера международного класса и выпускника Массачусетского технологического института Васика Райлиха, вернуть все трофеи и призовые деньги, которые он заработал обманным путём, то есть грубо нарушив лицензию GNU GPL.
Data Mining → Tim Salimans o выигрыше в конкурсе предсказаний результатов шахматных партий от Kaggle
Kaggle организует соревнования для людей, которые занимаются data mining. Сейчас открыты два конкурса. Один на 3 миллиона долларов, цель которого улучшить систему, по которой людей кладут в больницы. Второй — с призовым фондом 3000 долларов, чтобы улучшить измерения эллиптичности галактик, что позволит лучше измерить так называемую «темную материю» во вселенной.
Уже прошло около двух десятков конкурсов. О своем опыте участники делятся на блоге. Ниже — перевод поста Tim Salimans о его опыте участия в конкурсе предсказания результатов шахматных встреч на основе прошедших результатов.
Участникам конкурса предоставлялись результаты более 1,84 миллиона встреч более чем 54.000 шахматистов. Задача была предсказать результаты 100.000 игр между этими же шахматистами за следующие три месяца. В конкурсе приняли участие 189 команд.
Уже прошло около двух десятков конкурсов. О своем опыте участники делятся на блоге. Ниже — перевод поста Tim Salimans о его опыте участия в конкурсе предсказания результатов шахматных встреч на основе прошедших результатов.
Участникам конкурса предоставлялись результаты более 1,84 миллиона встреч более чем 54.000 шахматистов. Задача была предсказать результаты 100.000 игр между этими же шахматистами за следующие три месяца. В конкурсе приняли участие 189 команд.
Python → Задачка о восьми ферзях из песочницы
Рассмотрим такую любимую задачу на понимание алгоритмов, как «Задача о восьми ферзях». Классическое определение: «расставить на шахматной доске 8 ферзей так, чтобы ни один из них не бил другого». Ок, задачка очень популярная на разных собеседованиях, и Википедия нам сразу дает решение на моем любимом Python'е.
И это наверняка правильное решение с точки зрения обычного человека, но абсолютно бессмысленное с точки зрения хакера, и вот я вам расскажу почему:
Искусственный интеллект → Некоторые идеи написания искуственного интелекта для шахмат из песочницы
К сожалению, для шахмат пока нет лучших алгоритмов, чем перебор очень многих позиций. Правда, перебор порядком (и не одним) оптимизированный, но все же это большой перебор. Для поиска ответного хода строится дерево с исходным ходом в корне, ребрами — ходами-ответами и узлами — новыми позициями.
Как в элементарных алгоритмах выбирается следующий ход объяснить просто. На своем ходе вы выбираете такой ход (по вашему мнению), который принесет наибольшую пользу (максимизирует вашу выгоду), а противник на очередном своем ходе старается выбрать ход, который принесет ему больше всего пользы (максимизирует его выгоду и минимизирует вашу). Алгоритм с таким принципом называется минимакс. На каждом этапе вы присваиваете каждому узлу в дереве оценку позиции (об этом потом) и на своем ходе ее максимизируете, а на ходе противника — минимизируете. Алгоритм во время работы должен пройти по всем узлам дерева (то есть по всем возможный игровым позициям в игре), то есть совсем непригоден по времени.
Следующее его усовершенствование — альфа-бета отсечение (метод веток и границ).
Как в элементарных алгоритмах выбирается следующий ход объяснить просто. На своем ходе вы выбираете такой ход (по вашему мнению), который принесет наибольшую пользу (максимизирует вашу выгоду), а противник на очередном своем ходе старается выбрать ход, который принесет ему больше всего пользы (максимизирует его выгоду и минимизирует вашу). Алгоритм с таким принципом называется минимакс. На каждом этапе вы присваиваете каждому узлу в дереве оценку позиции (об этом потом) и на своем ходе ее максимизируете, а на ходе противника — минимизируете. Алгоритм во время работы должен пройти по всем узлам дерева (то есть по всем возможный игровым позициям в игре), то есть совсем непригоден по времени.
Следующее его усовершенствование — альфа-бета отсечение (метод веток и границ).
Веб-разработка → Javascript играет в шахматы — размер скрипта 1 KB!
Javascript в работе использует уже чуть ли не каждый веб-разработчик. Но пока только мексиканцу Оскару Толедо удалось упихнуть в один килобайт кода на Javascript самый настоящий шахматный алгоритм.
По ссылке можно сразиться с компьютером прямо в окошке браузера, а также ознакомиться с
Персональные блоги → livechess.ru выставлен на продажу
Привет, хабралюди!
Уже два года я играю в шахматы на портале livechess.ru.
Сегодня владелец сайта опубликовал новость о том, что ресурс продается с аукциона.
Уже два года я играю в шахматы на портале livechess.ru.
Сегодня владелец сайта опубликовал новость о том, что ресурс продается с аукциона.
