AlphaGo, разработанная компанией Google, обыграла чемпиона по Го. В чём была сложность построения игрового алгоритма?

Question

[khipster]

Каспарова в шахматы уже давно обыграл компьютер, а по поводу Го раздували шумиху, мол никогда компьютер не выиграет.

Вики:
Программа AlphaGo комбинирует метод Монте-Карло для поиска в дереве[en] (MCST) вместе с использованием свёрточных нейронных сетей для глубинного обучения оценки позиции и наиболее выгодных ходов. Суть этого метода (названого по аналогии с методом Монте-Карло в вычислительной математике) состоит в том, что сначала на текущей доске выбираются позиции, на которые можно пойти, а затем начиная последовательно с каждой из них разыгрывается большое количество случайных партий. Позиция, которая даёт наибольшее соотношение побед к поражениям, выбирается для следующего хода. (См. раздел Методы Монте-Карло в статье Компьютерное го). До AlphaGo наиболее успешные программы для игры в го использовали метод Монте-Карло[1].

Короче, простой перебор вариантов (умный, оптимизированный) но всё такой же перебор, т.е. сложность была просто в вычислительной мощности?

Comments

[doktr]

В шахматах 10^120 вариантов партий, а в Go - в 10^100 раз больше вариантов, чем в шахматах. Даже если все варианты просчитать, то их просто негде будет хранить, так как во Вселенной всего около 10^80 атомов.
Поэтому систему обучают с помощью нейронных сетей, чтобы она сама находила закономерности и в процессе игры предсказывала, какой ход лучше.

[uvelichitel]

В релизе указывалось, что играл обиходный кластер стоковых машин. Не grid CERNа и не облака.

[Алексей Николаев]

В Го физически невозможно просчитать ходы, их слишком много \ плюс масса верных вариантов делается чемпионами за счет интуиции профессионала, а не за счет просчета. Показательно, что в одной из партий машина ошиблась, и поняла это лишь через несколько ходов. Эта победа стала возможной исключительно за счет нейронных сетей, ИИ и машинного обучения. Скоро тест Тьюринга пройдут

Answer 1

[vchc]

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

Answer 2

[Иван]

Основная сложность - гораздо большая вариативность ходов (намного больше шахмат). Просто поиграйте в го.

Answer 3

[ivodopyanov]

По сути, основная идея Deep Mind, при помощи которой они обучили комп играм Atari и го, - это то, что большую таблицу можно неплохо аппроксимировать нейронной сетью.
Например, компьютер видит две разные позиции, но за счет обработки нейронной сетью "понимает", что они очень-очень похожи. Например, получены банальным сдвигом по одной из осей. А значит, и правильные решения будут почти одни и те же.

Answer 4

[jewubinin]

Простой перебор прекрасно работает в шахматах, но не работает в Го. В этом была и сложность.