Jugando con la muerte en la forma en la IA ha aprendido a ganar humana Bashny.Net

En 16 juegos de máquinas Hombre derrotado (17, si se toma en cuenta Lee derrota Se-dol en el segundo), pero en el futuro que está esperando una logros aún más impresionantes: la resolución de los problemas matemáticos, fisiológicas y biológicas más impresionantes, la victoria sobre la enfermedad y la vejez, la eliminación de los accidentes de tráfico triunfar en los conflictos militares, y mucho más.
El mundo ha cambiado ante nuestros ojos, pero no todos lo perciben. ¿Cuándo y cómo el programa aprendió a tocar correctamente? ¿Es siempre la pérdida de un hombre muestra la derrota de toda la humanidad? Encontrarán si la conciencia de la inteligencia artificial?
Sobre el autor. B> Este artículo está basado en la conferencia "Inteligencia Artificial. Historia y perspectivas ", celebrada en la oficina de Moscú del Grupo Mail.Ru Sergei Markov. Sergei Markov, aprendizaje automático se dedica a la "Caja de Ahorros". En el sector bancario construir modelos predictivos para la gestión de procesos de negocio, basado en muestras suficientemente grandes de formación, que pueden incluir varios cientos de millones de casos. Entre sus aficiones Sergey indica la programación de ajedrez, juegos de IA, Minimax problema. SmarThink programa, creado por Sergei Markov, se convirtió en el campeón de Rusia (2004) y la CEI (2005) entre los programas de ajedrez (2004), y en la actualidad está en el top 30 de los programas más fuertes del mundo. Sergey también es el fundador de la organización no lucrativa científica y educativa siglo portal 22.
¿Cómo empezó todo

TecnoNúcleo - el hábitat de la pluralidad de la inteligencia artificial en la tetralogía "Cantos de Hyperion" de Dan Simmons. Uno de los ejemplos de visualización fuerte AI en la ciencia ficción.
De la misma noción de AI ocurrido historia desagradable. Apareciendo originalmente por la ciencia entre los profesionales que trabajan en el campo de la informática, rápidamente cayó en el entorno público y ha sufrido varios cambios. Si usted le pide al hombre de la calle hoy en día, que es la IA, es más probable que va a escuchar de él no es la definición que se mantiene en la mente de los expertos de AI.
Antes de empezar una historia, tiene que decidir exactamente lo que entendemos por inteligencia artificial, y dónde está el límite en el que termina región rscience de cómputo y áreas adyacentes comienzan.
AI en general - es los métodos utilizados para automatizar tareas que se consideran tradicionalmente que las tareas intelectuales, y para el cual una persona usa su inteligencia natural. Al automatizar problema resuelto por el hombre con la ayuda del cerebro, que de esta manera creamos AI. Otra cosa es que este AI se refiere comúnmente como aplicación o, con cierto grado de desprecio débil. salvedad desagradable es que sólo está disponible para la humanidad de hoy clase de AI.
En cuanto a la IA fuerte, inteligencia artificial general (AGI), ciertos acontecimientos allí, pero siempre y cuando estamos en el principio. IA fuerte - es un sistema que puede hacer frente a cualquier desafío intelectual. En la ficción imagen se forma tal como el hombre, AI, capaz de resolver cualquier problema.

Debido a que estamos tan ampliamente utilizado en informática definir la inteligencia artificial, desde el punto de vista formal, encontramos elementos de la existencia de la IA, incluso los antiguos griegos. Estamos hablando de la famosa mecanismo de Antikythera, que es uno de los artefactos fuera de lugar. Este dispositivo está diseñado para cálculos astrofísicos. La imagen de arriba muestra uno de los fragmentos conservados y un moderno reconstrucción del artefacto. El mecanismo consta de 37 engranajes de bronce en una caja de madera, en la que se colocaron los diales de flecha. Restaurar la posición de los engranajes internos de los fragmentos minerales recubiertos administrados por tomografía computarizada mediante radiografías.
Por sí misma, la tarea de la cuenta una vez considerada intelectual - si bien podría creer que se podría llamar intelectual
.
Dependencia de Contabilidad de John Napier diseñado para una rápida multiplicación.
tareas de cuentas automatizadas entre los primeros. Incluso antes de los primeros dispositivos mecánicos aparecieron artesanías tipo neperovyh palos. matemático escocés, uno de los inventores de logaritmos John Napier, cree una unidad de cuenta en 1617 En el contexto de la tecnología moderna, parece ridículos: rollos de papel - de hecho, las primeras tablas logarítmicas para realizar ciertas operaciones. Sin embargo, para los contemporáneos que era aproximadamente el mismo milagro como cualquier AlphaGo para nosotros. En un momento había incluso poetas dedican palos neperovym (huesos de Napier) versos. Dicen por qué nosites con los huesos de los antepasados, que es el mismo hueso, que es realmente vale la pena para estar orgullosos.

PASCALINA - máquina aritmética, inventado por el científico francés Blaise Pascal en 1642
Pascal, junto con el matemático alemán Wilhelm Schickard, que ofreció su propia versión de un ordenador en 1623, sentó las bases para el surgimiento de la mayoría de los dispositivos informáticos. Hemos sobrevivido unos pocos coches, incluso cuando Pascal creó la vida. Esta máquina fue capaz de sumar, dividir, restar y multiplicar.

completa máquina de copia de trabajo, inventado por el matemático Inglés Charles Babbage en 1822. La llamada máquina diferencial está diseñado para automatizar los cálculos mediante la aproximación de funciones por polinomios y el cálculo de las diferencias finitas.
Acerca de Charles Babbage había oído casi todos los científicos de la computación. Por desgracia, Babbage nunca fue capaz de crear un equipo de trabajo. Durante mucho tiempo no cesó la controversia, funciona, en principio se propusieron motor de diferencia. En el período de 1989 a 1991, el 200 aniversario del nacimiento de Charles Babbage, los dibujos y sobrevivientes, con modificaciones menores se recogió copia de trabajo de la máquina analítica. Se hicieron las modificaciones necesarias debido a los "errores" que se encuentran en los dibujos. Tal vez Babbage hizo deliberadamente algo de distorsión lucha contra copia pirata sin licencia.
Máquina Analítica - es el prototipo de las modernas máquinas de von Neumann. Cuando los ingenieros de IBM construyó la primera máquina electrónica, que utilizan planos de Babbage. Se utilizó para hablar de la arquitectura de Von Neumann, es decir, una máquina con dispositivo separado de computación con un dispositivo de entrada-salida, memoria, etc. Sin embargo, basado en las ideas de Babbage son.
Además de código de máquina operador de la máquina bebbidzhevoy aplicado declaración de sucursales y bucle condicional. Esta máquina es realmente un bisabuelo de lo que entonces era capaz de hacer sobre la base de la electrónica.

máquina jacquard - derramada mecanismo del telar de conformado para la producción de tejidos de figuras grandes. Creado en 1804 le permite gestionar por separado cada filamento de soporte o un pequeño grupo de ellos.
dispositivos de entrada-salida, tarjetas perforadas eran todavía a Babbage - que fueron utilizados en las máquinas de tejer zhakkardovskih para establecer el orden de los hilos en la fabricación de tejidos
. Nuevo tiempo

TAB - electromecánico máquina diseñada para el procesamiento automático de los datos numéricos y alfabéticos almacenados en tarjetas perforadas
. La primera estadística está construido tabulador estadounidense Herman Hollerith en 1890 para resolver los problemas asociados con los cálculos estadísticos. El inventor bien conocido y fabricante de equipos para trabajar con tarjetas perforadas participaron con éxito en el concurso organizado por el gobierno de Estados Unidos para encontrar medios de automatización del procesamiento de los resultados del censo de población. Para el conteo manual y análisis tomaría cerca de 100 personas que trabajan para 4-5 años sólo para recopilar y calcular las cifras totales del censo sociológicos.

tarjetas perforadas Hollerith.
TAB - este es un cuadro resumen muy primitiva. Cada tarjeta corresponde al cuestionario, que se hundió en la cuenta principal. Tarjetas cargadas en una pestaña, que los persiguieron rápidamente por sí mismas y producen resultados en forma de una tarjeta con la cantidad contada. Estas cantidades se invirtieron en otro tabulador, etc.
Después de ganar la competencia, Hollerith fundó la compañía - Tabulación de la compañía de máquinas, y después de una serie de fusiones y adquisiciones, se hizo conocido como IBM
. Los juegos que se juegan máquinas
Como en todo, la sección de la ciencia experimental de la informática, se dedica a la IA necesita una propia mosca Drosophila, un objeto de modelo, que se pueden probar las técnicas de IA. El juego - el más famoso de la mosca Drosophila en la IA
. Juego - espacio neto modelo. Se especifica las condiciones de estados definidos de forma única y se describe como un conjunto de parámetros. Creación de AI para el juego, que de este modo abstracto de la masa de los problemas de ingeniería que se encuentran entre AI y una solución práctica al problema. Nos abstracta de la codificación de los datos en la entrada y la salida de la conversión de la señal, el problema de la percepción, etc. Para nosotros, no es una tarea intelectual en el juego en su forma más pura. Esto es conveniente, ya que para los especialistas en la IA son perezosos y no quieren hacer nada más que la IA.

ajedrez Máquina "turco».
Juego - es un espectáculo. Si muestra el coche, que sabe cómo jugar bien, se hará una impresión incluso en la persona ignorante. Máquina de juego atrajo la atención durante cientos de años. En la imagen superior se puede ver una ilustración de la famosa broma - la primera máquina de ajedrez, diseñada inventor Wolfgang von Kempelen en 1769. En el interior del "coche" es en realidad esconde un jugador real. En este cuadro no se desdeñó a subir los principales actores de ajedrez de su época. Johann Baptist Allgaier, el jugador de ajedrez más fuerte de Austria finales del siglo XVIII -. El comienzo del siglo XIX, ha jugado para el turco varias partes
. Este es un dispositivo mecánico complejo no es la inteligencia artificial, pero es curioso que con su ayuda fue capaz de engañar a los contemporáneos. La gente realmente cree que algún artesano fue capaz de crear un sistema capaz de jugar al ajedrez con la ayuda de engranajes, palancas, mecanismos y saldos. Conservados incluso juegos de registros jugados por un turco mecánica contra Napoleón (aunque algunos historiadores han puesto en duda la exactitud de su tema). Así que tal vez había engañado incluso los más altos personajes.

Y este es el primer dispositivo que realmente sabía cómo jugar al ajedrez. El ajedrecista (en ruso - "jugador de ajedrez"). Fue creado en 1912 por el famoso matemático e ingeniero español Leonardo Torres Quevedo.
El ajedrecista era un tablero de ajedrez en el que la máquina mediante electroimanes movió el rey y la torre. La máquina está garantizada para poner el rey y la torre jaque mate a un rey solitario de una posición: el rey estaba junto a la torre blanca en el H8 - en el G-7, y el rey negro podría ser en cualquier campo. Dos supervivientes máquinas de copia en exhibición en el Museo Politécnica de Madrid.

Este es otro conocido AI pasado - mecanismo "Nimatron", creada en 1940 para jugar con él. Él - un juego matemático en el que dos jugadores se turnan para tomar los artículos presentados en varias pilas (generalmente tres). En un solo movimiento, se puede tomar cualquier número de elementos (mayor que cero) de un puñado. El ganador es el jugador que toma el último objeto.
Este es uno de los primeros juegos que han construido una teoría matemática completa de vuelta en el bienio 1901-1902. En cuanto a los métodos de nada "Nimatron" nueva presentada, sobre la base de la estrategia óptima ya conocido para este juego, pero fue una de las primeras decisiones de la teoría de juegos en la glándula.
Proyecto "Nimatron", dirigida por Edward Condon Uhler - uno de los padres de la mecánica cuántica moderna. A su juicio, el mayor fracaso del proyecto en mi vida, pero no con el punto de vista técnico y financiero. Trabajando en "Nimatronom" Condon y su equipo inventado muchas tecnologías (incluyendo, por ejemplo, el método de fabricación de placa de circuito impreso), que más tarde se alegó en la tecnología informática. Pero el equipo no patentó expertos, como resultado de cualquier cosa no funciona.
La estrategia óptima

Ernst Friedrich Ferdinand Zermelo - matemático alemán que hizo importantes contribuciones a la teoría de conjuntos y la creación de las bases axiomáticas de las matemáticas
. Hablando de inteligencia artificial para juegos está completo sin la mención de Ernst Zermelo y su teorema. fans del tema de la suerte de habla rusa. El trabajo de Zermelo fue escrito originalmente en alemán. Y si fue traducido al Inglés sólo en 1999, el idioma ruso - a finales de 1960 - principios de 1970. Debido a esto, en la literatura rusa escrito más o menos correcta sobre lo que hizo Zermelo, y en la literatura en idioma Inglés sigue siendo confuso. Por ejemplo, en un estudio dice que Zermelo demostró que si el blanco de ajedrez hará movimientos perfectos, asegúrese de llegar a al menos un empate. De hecho, nadie hasta la fecha no ha proporcionado tal evidencia, sin embargo Zermelo hizo otro descubrimiento importante.
No es un buen juego de ajedrez, y en general no sabía las reglas del juego. Tal vez por ello, y demostró en 1913 la primera teoría formal de la teoría de juegos. Según el libro "procesos gestionados y la teoría de juegos", publicado en la URSS en 1955, la descripción correcta de la contribución de Zermelo es: "Zermelo demostró juegos determinismo como el ajedrez, y lo que los jugadores racional puede, utilizando toda la información para desarrollar un juego de estrategia óptima . »Blog reglas ordinarias de ajedrez saben casi todo, pero hay algunas otras reglas muy importantes y no del todo evidentes. Por ejemplo, una regla mueve 50 establece que si durante 50 movimientos sin peón no se ha movido hacia delante, y nadie cifra no ha sido tomada, que se otorga a un empate. O si una determinada posición se repite tres veces - también galardonado con un empate. infinito juego de ajedrez en el número de golpes no puede ser - en algún momento en el juego de una manera u otra parada. Ernst Zermelo no lo sabía, y pensé que las posibilidades son interminables partidas de ajedrez: si se va cifra - volver, y así juega hasta que el universo no se desmorone en polvo.
Cómo ganar en el tic-tac-toe

Así que veamos cómo determinar la estrategia óptima de juego. Una pequeña digresión de ajedrez, tomar un ejemplo sencillo - tic-tac-dedo del pie, uno de los juegos más antiguos del mundo, apareció en el antiguo Egipto. Para este juego Zermelo utiliza inducción hacia atrás - el método por el cual se realiza la búsqueda en la dirección opuesta, a partir de la posición en la que una de las partes ha recibido una palmada o una estera, y terminando con la posición específica de pie en el tablero <. br> Zermelo no dio una descripción detallada de la inducción hacia atrás, pero usó el principio de que hay una posición para el lado ganador. Podemos nombrar para dicha evaluación posiciones: -1 - ganado dedo del pie, 1 - won cruza 0 - elaborar
. Ahora podemos ir hasta el árbol a partir de estas posiciones y ver si el curso es, con algunas posiciones, lo que lleva a una posición ganadora. Si no hay progreso, entonces el artículo será considerado ganador.
Por otro lado, si no hay progreso, lo que lleva a una posición ganadora, pero hay al menos un paso que conduce a la posición de no-hombre, entonces esta posición se considera un empate. Y si no hay progreso, ni el capitán ni ningún hombre, ni en posición ganadora, se considera la posición que se pierde.
El uso de esta regla, estamos en el árbol, a partir de las hojas, se mueve hacia arriba, y atribuimos evaluación nodos hasta que asignamos a las marcas de todas las posiciones. Después de recibir todas las puntuaciones para todas las posiciones, vemos un algoritmo perfecto para el juego. Una vez en una posición determinada del juego, siempre vamos a ver el progreso (si lo hay), lo que lleva a una posición ganadora. Si el movimiento ganador no está presente, se llevará a cabo un sorteo derrame cerebral, y sólo en el peor de los casos irá a una posición perdedora. En teoría, este sistema es capaz de almacenar en la memoria del árbol de evaluación para cada posición, jugará en el nivel de un dios.

Zermelo se entiende, pero se cree que este árbol tiene ramas infinitas donde no hay punto final. Se pregunta si es posible que un juego que tiene el árbol infinito en el tamaño de las posiciones en que, en un tiempo finito para calcular la estrategia óptima que está garantizado para estar en cualquier posición para hacer el movimiento perfecto? Y demostró que a pesar del hecho de que el árbol en sí puede ser infinito, podemos encontrar la estrategia óptima para un número finito de iteraciones. Y es un número finito de iteraciones sin duda no es mayor que el número de diferentes objetos en el juego.

EDSAC (Electronic Delay Storage calculadora automática) - la primera en el mundo de la actuación y prácticamente utilizó un programa de ordenador almacenado en la memoria, creada en 1949 por la Universidad de Cambridge (Reino Unido). En 1952, la puesta en práctica del juego de tic-tac-dedo del pie para la computadora EDSAC fue uno de los primeros videojuegos. El equipo aprendió a jugar el juego perfecto contra una persona que se sabe de él en términos de estrategia óptima.
Contacto Inducción: Método de Historia

economista Oskar Morgenstern, uno de los autores de la teoría de juegos, y el matemático John von Neumann, que hizo importantes contribuciones a la física cuántica, análisis funcional, teoría de conjuntos y otras ramas de la ciencia.
Empleo sobre la inducción de interpretación es inversa en la teoría de conjuntos. Otra área de conocimiento, sin la cual es imposible imaginar el desarrollo de la teoría de juegos, se encuentra en el campo de la economía. В 1944 г. вышла монография Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение», в которой авторы обобщили и развили результаты теории игр и предложили новый метод для оценки полезности благ. В этой работе впервые формально было дано определение метода обратной индукции.



В 1965 г. математик Ричард Белман предложил использовать метод ретроспективного анализа для создания баз данных решений шахматных и шашечных эндшпилей (заключительная часть партии). Он дал алгоритмическое описание применения метода обратной индукции для построения оптимальной стратегии в играх.



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

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



В 1977 г. Кен Томпсон, известный за вклад в создание языка С и ОС UNIX, представил одну из первых в мире эндшпильных таблиц для всех пятифигурных окончаний.

В 1998 г. наш соотечественник, программист Евгений Налимов создал чрезвычайно эффективный генератор шахматных окончаний, благодаря которому, учитывая рост производительности компьютеров, к началу 2000-х годов были посчитаны все шестифигурные окончания.



Эту главу закроет фотография не человека, а компьютера. В 2012 г. рассчитали семифигурные таблицы для ситуаций распределения фигур четыре против трех и пять против двух. Их назвали таблицами «Ломоносова», так как рассчитывались они на суперкомпьютерах МГУ «Ломоносов» и IBM BlueGene/P.

Неожиданные открытия в шахматах
Участие компьютеров в шахматных играх открыло людям то, о чем никто не догадывался сотни лет. Как уже упоминалось, в шахматах существует правило 50 ходов. Было известно, что есть очень редкие исключения, когда игрокам требовалось более 50 ходов для хитрых маневров. Однако когда Кен Томпсон начал публиковать результаты анализа, оказалось, что этих исключений очень много.
Эксперты ФИДЕ (Federation Internationale des Echecs — Международная шахматная федерация) предложили заменить правило 50 ходов на правило 75 ходов, что и было сделано.



Вскоре выяснилось, что в ряде случаев для завершения партии недостаточно и 75 ходов, но и на этом процесс поиска новых решений не остановился. На сегодняшний день рекордная задача — мат в 549 ходов.

В итоге ФИДЕ на это дело плюнули и решили вернуться к правилу 50 ходов. В конце концов, неужели мы будем подыгрывать компьютерам? Ни один человек со стандартным размером мозга не способен найти последовательность из сотен тихих ходов, ведущих к победе.



Кен Томпсон провел несколько показательных выступлений — «ладья и король против ферзя и короля». Компьютер играл за игрока, владеющего ладьей. Этот эндшпиль теоретически проигрышный — шахматист уровня мастера, владея ферзем, обычно легко выигрывает у любого противника. Компьютеру была поставлена задача максимально оттянуть свой теоретически неизбежный проигрыш. На одном из выступлений против компьютера играли Ханс Берлинер, чемпион мира в игре по переписке, со своим другом — сильным гроссмейстером из топ-30 мировых игроков. И двум гроссмейстерам не удалось заматовать короля. На доске происходило нечто феерическое — происходили неясные маневры, но черным чудесным образом удавалось выпутаться. Это была одна из первых прекрасных демонстраций того, что люди, возможно, переоценивают себя в понимании некоторых вещей.



Фрагмент листинга шахматной программы ИТЭФ для ЭВМ М-20.

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

На основе исходных текстов программы ИТЭФ началось создание новой шахматной программы, получившей название «Каисса». В 1974 г. Каисса стала первым чемпионом мира по шахматам среди компьютерных программ. Многие алгоритмы, придуманные авторами Каиссы, до сих пор применяются в шахматах. Каисса применила алгоритм отсечения позиций, и впервые — побитовое представление доски. Также она могла производить анализ во время хода соперника, использовала эвристику нулевого хода и сложные алгоритмы для управления временем.

Решение на уровне бога


Если заучить эти таблицы, вы сможете идеально играть в крестики-нолики с любым противником.

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

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

И третий вид — сильное решение. Для каждой позиции мы знаем ее точную оценку. Например, для крестиков-ноликов точно знаем дерево ходов — около 900 позиций, если учесть все симметрии.

29 апреля 2007 г. команда исследователей из Университета Альберты (Канада) под руководством Д. Шеффера (известного как ведущий разработчик шашечной программы «Чинук») смогла достичь «слабого» решения для английских шашек, по правилам которых шашки не бьют назад, а дамки не могут ходить на любое расстояние.

Английские шашки — самая большая из игр, решенных до настоящего времени. Размер ее поискового пространства 5×1020. Для того чтобы найти решение, в течение 18 лет сеть персональных компьютеров (в разное время от 50 до 200) произвела 1014 вычислений.



На начало 2016 г. найдено решение в 16 играх. Последней на данный момент решенной игрой стала пентаго. В отличие от шахмат и го поисковое пространство игры небольшое, что позволяет современному компьютеру играть идеально: с учетом всех возможных симметрий количество возможных позиций в пентаго составляет 3 009 081 623 421 558. В течение нескольких часов суперкомпьютер Edison семейства Cray, находящийся в Национальном научно-вычислительном центре энергетических исследований (NERSC), нашел «сильное» решение игры. Программа использовала для вычислений 98 304 потоков.



Также удалось найти решение для такой необычной игры, как «Магараджа», где черные имеют набор обычных шахматных фигур, а белые — единственную фигуру Магараджа. Это ферзь, способный ходить как конь. Доказано, что черным гарантирована победа.

DRAMA: от проигрыша машины к проигрышу человека


Американский математик и шашист Марион Франклин Тинсли был сильнейшим игроком мира в английские шашки на протяжении 30 лет. Тинсли ни разу в жизни не проигрывал матч за первенство мира и за свою 45-летнюю карьеру проиграл всего семь партий.
В 1992 г. проводился матч между Марионом Тинсли и программой «Чинук». Первый матч Тинсли выиграл у программы со счетом 4:2 при 33 ничьих. При анализе матча выяснилось, что в одной из партий Тинсли выбрал единственную верную позицию, ведущую к победе, за 64 хода до конца матча.

На матче реванше Тинсли успел сыграть шесть игр — все ничьи. После этого он почувствовал себя очень плохо и у него диагностировали рак поджелудочной железы и вскоре он умер. В 1995 г. программа «Чинук» выиграла у Дона Лафферти, наследника Тинсли на шашечном троне. Из 32 сыгранных партий единственная результативная партия завершилась в пользу компьютера. После этого первенство в шашках окончательно перешло к машинам.



Одна из величайших шахматных партий всех времен.

Более распиаренный матч, о котором слышали даже далекие от шашек и шахмат люди, состоялся в 1997 г. Гарри Каспаров проиграл суперкомпьютеру Deep Blue в матче из шести партий. Для сравнения: Deep Blue был способен просматривать 200 млн позиций в секунду, в то время как современные компьютеры просматривают 1—3 млн позиций в секунду. За прошедшие 20 лет компьютеры так и не смогли догнать этот уникальный инженерный проект.

Машина от компании IBM была не просто суперкомпьютером, а специализированным под шахматы проектом, в котором установили отдельные кристаллы с генераторами ходов, позволявшие за один такт процессора сгенерировать все возможные ходы в позиции. Однако сейчас такая мощь нам не требуется — мобильный телефон обыгрывает ведущих гроссмейстеров.

Огромный Deep Blue впечатлял одним своим видом, но его размеры привели к появлению стойкого мифа: мол, машины выигрывают у людей только благодаря своей мощности и быстроте — давят брутфорсом. Человек может просмотреть всего две или пять позиций в секунду, компьютер — сотни миллионов.



На самом деле это не так. На рисунке выше приведен пример задачи из учебника — мат в шесть ходов. Deep Blue, используя полный перебор, должен был бы потратить около 356 лет на поиск решения. В среднестатистической шахматной позиции возможно 35 ходов, чтобы просмотреть на два хода — 35 в квадрате, на три — в кубе и т.д.

Любая сильная современная программа находит решение на настольном компьютере максимум за несколько секунд. Более того, на современной машине вы можете запустить программу чемпиона 2008 г. против программы чемпиона 2015 г. Из 27 партий одну партию будет выигрывать слабейшая программа, 26 партий — сильнейшая. Это прогресс, достигнутый за семь лет. Это произошло не за счет роста мощности железа, а благодаря развитию алгоритмов. За данным процессом не стоят тысячи программистов и десятки гроссмейстеров. Сейчас над шахматными программами работают либо программисты-одиночки, либо очень небольшие группы. Например, одну из самых сильных программ в мире шахмат — Stockfish — создали три программиста. Над самыми крупными, с точки зрения числа задействованных программистов проектами — Deep Blue и Каисса — работало менее десятка программистов.

Все современные шахматные программы так или иначе являются детищем машинного обучения. В шахматной программе есть оценочная функция, рассматривающая позицию без всякого перебора. Это, грубо говоря, логистическая функция, имеющая 3—5 тыс. параметров, для подбора которых используются большие массивы шахматных позиций, выбранных обычно из партий самой же программы. Программа играет несколько тысяч партий, оттуда извлекаются позиции, программа снова играет и т.д. — цикл не заканчивается никогда.

Самое забавное, что если мы говорим о брутфорсе, то надо задаться вопросом: действительно ли брутфорс на стороне машин? В среднестатистическом человеческом мозге примерно 86 млрд нейронов и 150 трлн синапсов. Каждый синапс содержит примерно 1 тыс. молекулярных переключателей. Таким образом, если мы пересчитаем мозг в триггеры, то получим 150 квадриллионов (1, 5х1017) триггеров транзисторов. Конечно же, это две «машины» с абсолютно разной архитектурой, но мы очень примерно можем сравнивать их на некоторых задачах.



Один из самых мощных на сегодняшний день процессоров (Sparc-M7) имеет 10 млрд транзисторов. Самая большая программируемая пользователем вентильная матрица (FPGA) содержит до 20 млрд транзисторов. Это всего 2х109 раз, а в мозге 1, 5х1017 раз. Конечно, компьютеры имеют одно большое преимущество — скорость. Sparc работает на частоте 4, 3 ГГц. Человек же имеет следующие потенциалы действия нервных клеток: амплитуда — около 0, 1 В, длительность — около 1 мс, «рабочая» частота» — 10—100 Гц (до 1000 Гц).

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

Нейронные сети


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

«Грязнули» считали, что неважно, каким образом решать задачу. Если решение работает в рамках предметной области, значит оно хорошее. Они ввели термин hacking для ИИ — мы ломаем задачу, чтобы решить ее.

Если сейчас посмотреть на методы ИИ, используемые в играх, то увидим определенный синтетический подход. Формально необоснованные трюки, но хорошо работающие на практике, соседствуют с формально доказанными методами.

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



Первыми создателями моделей математических процессов, происходящих в человеческом мозге, стали Уорен МакКалок, Уолтер Питтс, Дональд Хебб в 1940-х годах. Они придумали первую модель искусственного нейрона — простой логистический сумматор.



Схема искусственного нейрона:

нейроны, выходные сигналы которых поступают на вход данному; сумматор входных сигналов; вычислитель передаточной функции; нейроны, на входы которых подается выходной сигнал данного; Wi — веса входных сигналов.
Во многом отношения между этими людьми заложили некоторые базовые вещи в науке. Например, мы не называем нейронные сети кибернетическими системами, хотя МакКалак и Питс начинали работать под началом Норберта Виннера, основоположника кибернетики. Богемный образ жизни МакКалака и Питса и вечеринки с алкоголем очень не нравились жене Виннера. Есть мнение, что она сильно повлияла на раздор между учеными. Питсу это стоило карьеры, и, вполне вероятно, жизни — впоследствии он спился. Но они не стали делать из ссоры идеологический спор. Их пути разошлись по личным, а не научным причинам.

Что мы знаем про нейроны? Первая поверхностная основа коннектома — это нейроны, соединенные аксонами и дендритами, исходящими и входящими отростками. Место контакта аксона и дендрита — это синапс. Как и многое в природе, здесь присутствует сигмоид в качестве сумматора. Сигналы из нейрона распространяются по исходящим отросткам, попадают в следующий нейрон, суммируются и определенная сумма передается дальше по отростку, преобразовывая синапсы через определенные пороговые функции.



MARK 1 — первый в мире нейрокомпьютер, созданный в 1958 г. Фрэнком Розенблаттом.

Перцептрон — первая искусственная нейронная сеть, воплощенная на практике Фрэнком Розенблаттом. Ученый решил, что нет времени ждать, пока электронные машины станут достаточно быстрыми, чтобы на фоннеймановской архитектуре смоделировать работу нейронной сети. Он начал делать нейронные сети из «палок и скотча» — этакий массив электронных нейронов и кучи проводов. Это были небольшие нейронные сети (до нескольких десятков нейронов), но они уже применялись в решении некоторых практичных задач. Розенблат смог даже продать нескольким банкам устройства, применявшиеся при анализе некоторых массивов.



С 1966 г. он стал заниматься необычными вещами. Например, учил крыс проходить лабиринт, тренировал их, потом умерщвлял. Затем извлекал их мозг, размалывал в кашицу и этой кашицей кормил следующее поколение крыс. Таким образом, он проверял, улучшит ли это показатели следующего поколения крыс при прохождении лабиринтов.

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



Спустя полвека после изобретений Розенблата у нас появился нейроморфический процессор TrueNorth, созданный IBM по заказу DARPA. Чип содержит более 5 млрд транзисторов и имитирует работу до 1 млн модельных «нейронов» и до 250 млн связей между ними («синапсов»). В IBM говорят, что из процессоров такого рода будут собирать реальный эмулятор работы человеческого мозга.

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

Если мы начинаем крутить матрицу нейронов внутри фон-неймановской машины, то сталкиваемся с дефицитом вычислительных ядер по сравнению с числом ячеек памяти. Сам цикл обсчетов всех синапсов получается длинным. Хотя задача очень хорошо распараллеливается в рамках одного цикла, вам все равно на следующем шаге понадобятся значения на вход, которые вы получили на предыдущем шаге расчета. Максимумальная эффективность распараллеливания может быть достигнута тогда, когда у вас столько вычислительных ядер, сколько синапсов.

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



Вернемся в 1970-е годы. После успехов Розенблата следующим видным специалистом в области развития ИИ стал Марвин Мински. Вместе со своим коллегой Папертом он написал книгу «Perceptrons», которая показала принципиальные ограничения перцептронов. Косвенным образом эта работа способствовала наступлению «зимы» ИИ (1970-е и 1980-е годы), когда возникло очень много сомнений о возможностях создания полноценного ИИ на основе нейросетей.

Интерес к нейронным сетям вернулся в начале 1990-х годов, когда стало понятно, что сравнительно небольшие нейронные сети, доступные на тот момент, уже способны решать некоторые задачи не хуже, чем классические методы нелинейной регрессии.



Leon A. Gatys et al./ arXiv.org

В 2016 г. новости о достижениях нейронных сетей стали появляться чуть ли не каждую неделю. Коллектив ученых из Германии разработал искусственную нейронную сеть, позволяющую «синтезировать» изображение из двух независимых источников: одно из них дает только содержание, другое — только стиль. Нейросеть научилась реалистично раскрашивать черно-белые снимки. Нейросеть научили ставить геотег на снимки еды и котиков. Нейросеть стала вычислять смешные картинки. Ну и так далее.

Новый прорыв: AlphaGo


Игра Го всегда была крепким орешком для ИИ. Скептики утверждали, что программы в го либо никогда не победят, либо одержат победу очень нескоро. Го сложнее шахмат в 10100 раз — именно в столько раз больше возможных позиций камней на стандартной доске 19×19, чем в шахматах.

Прорыв удалось совершить в программе AlphaGo благодаря алгоритму Монте-Карло-поиска по игровому дереву, управляемому двумя нейронными сетями, обученными на основе большого массива игр профессиональных игроков в го. Вначале AlphaGo выиграла у чемпиона Европы, затем победила Ли Седоля, одного из сильнейших (возможно, самого сильного) игроков мира.

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



Изображение: The Atlantic.

В AlphaGo одна из нейронных сетей (value network) используется для оценки позиций в терминальных узлах дерева поиска, другая (policy network) предназначена для умного отбора ходов-кандидатов. Также используется небольшое дерево перебора Монте-Карло. В каждом узле рассматривается 1-2 хода, средний коэффициент ветвления — меньше двойки. Благодаря этому стало возможным посчитать осмысленное дерево с очень ограниченным числом вариантов, и за счет этого найти действительно сильнейший ход в позиции.

Сначала AlphaGo тренировалась на партиях сильнейших игроков в го. В качестве входных данных для обучения использовались 160 тыс. игр с 29, 4 млн позиций. С момента, когда она стала играть не хуже обычных людей, корпус для тренировки нейронной сети или для постройки параметров оценочной функции стал генерироваться автоматически. Программа начала играть сама с собой, добавляя новые партии в обучающую выборку.

Угрозы и перспективы: плохой, хороший и очень хороший сценарий


Изображение: TechRadar.
Разные страхи, связанные с искусственным интеллектом, вызваны несколькими проблемами. Люди боятся самих себя, боятся допустить ошибку при создании ИИ — вдруг он будет вести себя не совсем так, как мы хотим. Представьте такую гипотетическую ситуацию: машине долго объясняют, что бывают грибы съедобные и несъедобные, и ядовитые грибы смертельны для человека. Дальше машине задается вопрос: любые ли грибы может есть человек? «Конечно любые, — отвечает машина. — Но некоторые только один раз в жизни».

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

Знакомые страхи? Однако эта история непосредственного отношения к ИИ не имеет — мы говорим лишь о том, что люди сами себе не доверяют. Мы боимся не только того, что развитый разум окажется злым. Он может оказаться и добрым, захочет нести людям добро, но увидит это «добро» по-своему.

У человечества с развитым ИИ есть два хороших сценария развития событий и один глобальный плохой. Глобальный плохой заключается в том, что наша технологическая мощь растет слишком быстро. В XIX в. при большом желании устроить апокалипсис человечеству не хватило бы сил аннигилировать всю жизнь на планете даже при тотальном помешательстве.

В середине ХХ в. обезумевшие руководители ведущих стран и несколько военных начальников на ключевых постах воплотили бы сценарий самоуничтожения. Для этого достаточно взять несколько десятков 200-тонных термоядерных бомб и сбросить их по экватору — земной шар расколется пополам.



Изображение: Plague Inc.

В XXI в. технологическая мощь такова, что для воплощения апокалиптичных сценариев не требуется большое количество фигурантов. Допустим, биохимическая лаборатория создает убийственный вирус. Быстро защищаться от вирусов мы не умеем. Не исключено, что не так уж сложно сделать заразу, которая будет одновременно очень вирулентна, имея соответствующие фрагменты из вируса гриппа, и в то же время на 100% летальна, получив часть, например, из Эболы. Для воплощения такого проекта хватит нескольких десятков образованных безумцев.

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

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

Если наша цивилизация проскочит через это бутылочное горлышко, то откроются два хороших сценария. Сценарий первый: мы — это тупиковая ветвь эволюции. Разум, превосходящий нас, будет развиваться дальше, а мы останемся забавными обезьянками, живущими в своем мире со своими страстями и интересами. В таком мире нам нечего будет делить с разумными машинами, как нечего делить с шимпанзе и гориллами. Наоборот, мы любим играть с приматами, снимать про них забавные фильмы. Возможно, ИИ будет снимать документальные сериалы про людей, и показывать своим отпочкованиям.

Второй сценарий: с определенного момента уровень развития технологии превысит сложность организации нашего организма. И с этого момента разница между нашими машинами, нашими инструментами и нами самими начнет неизбежно стираться. Мы станем вмешиваться в собственный организм, доращивать свои нейронные сети искусственными дополнениями, добавим постнеокортекс к мозгу.

Представьте, что мы склеиваем искусственную нейронную сеть с нашим мозгом. Искусственная нейронная сеть, например, в 10 тыс. раз больше нашей нейронной сети. Известно, что мозг — штука пластичная, и даже ранения мозга, вышибающие из него куски, часто не приводят к потерям личности, самоидентификации. Поэтому не исключено, что от системы склеенного мозга с искусственной сетью мясной мозг можно будет отрезать и выбросить без ущерба для личности.

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

Последние слова: ИИ как личность


Изображение: Machine Overlords

Возможно ли самосознание у искусственного интеллекта?

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



Зеркальные нейроны могут быть задействованы в освоении новых навыков путем имитации.

У человека в процессе эволюции появились зеркальные нейроны, используемые социальными организмами для прогнозирования поведения других особей. То есть нам где-то в голове нужна модель, которую мы можем применить к другому человеку, чтобы спрогнозировать его поведение. В какой-то момент зеркальные нейроны стали «рассматривать» и сами себя.

Если данная теория верна, то схожим образом, через побочные эффекты, возможно развитие искусственного интеллекта, неизбежно вырабатывающего у себя самосознание. Если нам потребуется, чтобы ИИ мог спрогнозировать поведение других ИИ или людей, у него появится модель для прогноза действий, и рано или поздно он применит эту модель к самому себе. Осознание — неизбежное следствие развития сложно организованной интеллектуальной системы.

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



Что касается копирования сознания на электронный носитель, то в этой истории тоже не все однозначно. Английский ученый Роджер Пенроуз утверждает, что человеческое сознание не является алгоритмическим, и в силу этого не может быть смоделировано с помощью обычного компьютера типа машины Тьюринга. По мнению Пенроуза, сознание связано с квантовыми эффектами, а значит, принцип неопределенности Гейзенберга не позволит получить точный снимок электронной активности мозга. Поэтому наше сознание, скопированное в машину, не будет точной копией. Большая часть исследователей с этим мнением не согласна, считая, что пороги сигналов в мозге очень далеки от квантового уровня.



Метод опорных векторов в машинном обучении был предложен Владимиром Вапником в 1995 г.

В завершение вспомним о нейронных сетях. На самом деле нейронные сети на практике в машинном обучении — это модели для ленивых. При отсутствии возможности правильно настроить метод опорных векторов (SVM) или построить random forest, мы берем нейронную сеть, загоняем в нее обучающую выборку, получаем какие-то характеристики модели и т.д.

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

Можно ли сделать универсальный ИИ не на нейронных сетях? Конечно! Просто мы начинаем с бионического подхода. Вначале пробуем улучшить то, что есть сейчас, а затем будем искать более совершенные методы.

Какой бы путь мы не выбрали, не стоит воспринимать его как человеческую драму по противостоянию человека и компьютера. Под каждым постом о победе ИИ в очередной игре кто-нибудь обязательно напишет комментарий про SkyNet и Судный день. Почему проигрыш машине воспринимают как проигрыш человека? Это выигрыш человека, только не того, который играл за доской, а того, который создал ИИ. И это гораздо более важное достижение: один из них научился двигать фигуры, а другой оказался на шаг впереди и написал программу, двигающую фигуры к победе.

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

Источник: geektimes.ru/company/mailru/blog/277064/