Привет!
Все мы знаем Го — глубокую, медитативную игру на доске 19x19. Камни, пересечения, территории... А что, если выкинуть саму сетку и разрешить ставить камни куда угодно в пределах доски?
Мы в команде YSDA (Yandex School of Data Analysis или Школа Анализа Данных, ШАД) задались этим вопросом и решили проверить. Получилось азартно, хаотично и, что самое главное для нас как разработчиков, — чертовски интересно с точки зрения алгоритмов.
Метод Монте-Карло это алгоритм принятия решений, часто используемый в играх в качестве основы искусственного интеллекта. Сильное влияние он оказал на программы для игры в Го, хотя находит свое применение и в других играх, как настольных, так и обычных компьютерных (например Total War: Rome II). Так же, стоит отметить, что метод Монте-Карло используется в нашумевшей программе AlphaGo, победившей го-профессионала 9-го дана Ли Седоля в серии из 5 игр.
В данной статье хотелось бы рассказать про версию алгоритма Монте-Карло под названием Upper Confidence bound applied to Trees (UCT). Именно после публикации этого алгоритма в 2006-м году, программы для игры в Го сильно усилили свои позиции и достигли значительных успехов в игре против человека.
Читать полностью »
В предыдущей статье я говорил про взаимодействие камней со стенкой. Сейчас я покажу как это выглядит в теории.
Приведу по очереди четыре примера. В качестве стенки (1-ой линии) я использую середину доски 13х13, чтобы за ней нарисовать как выглядит отражение.
Я начинал свою историю игры в Го давным давно в 2006 году. Начало может быть вполне обычное, а может быть и нет.
После поступления в аспирантуру я решил, что теперь у меня появилось много свободного времени, которое надо тратить на разные интересные занятия (очевидно, что с аспирантурой у меня в последствии ничего толкового не вышло, хотя поездить по иностранным школам было очень приятно в плане путешествий, а не приобретения профессиональных знаний). Одно из интересных занятий было посвящено шахматам. Эта игра казалась мне венцом творения интеллектуальных игр. Как то поделился я мыслями со своим приятелем, а он мне и говорит, что есть игра гораздо сложнее — Го называется. (На тему Го можно почитать у GlukKazan)
Читать полностью »
