PDF de programación - Aplicación de inteligencia artificial en videojuegos

GRADO EN INGENIERÍA DEL SOFTWARE (PLAN 2009)

PROYECTO FIN DE GRADO

Curso 2016/2017

APLICACIÓN DE INTELIGENCIA
ARTIFICIAL EN VIDEOJUEGOS

USO DE LA VARIANTE DEL ALGORITMO MINIMAX

PODA ALPHA-BETA PARA SU DESARROLLO



ALUMNO: PABLO LUIS GUTIÉRREZ UTANDE
TUTOR: ÁNGEL ARROYO CASTILLO


Aplicación de inteligencia artificial en videojuegos…



ÍNDICE



Resumen ............................................................................................................................ 3
Capítulo I. OBJETO Y METODOLOGÍA DE LA INVESTIGACIÓN ......................................... 4
Introducción ................................................................................................................... 4
Objeto del proyecto ....................................................................................................... 5
Tema de investigación................................................................................................ 6
Objetivos del proyecto ............................................................................................... 6
Estado de la cuestión ................................................................................................. 7
Metodología de la investigación .................................................................................... 7
Fuentes ........................................................................................................................... 9
Estructura del trabajo .................................................................................................... 9
Capítulo II. HISTORIA DE LOS VIDEOJUEGOS DE ESTRATEGIA ...................................... 11
Estrategia en tiempo real ............................................................................................. 11
Táctica en tiempo real ................................................................................................. 13
Estrategia por turnos ................................................................................................... 13
Táctica por turnos ........................................................................................................ 14
Ejemplos ....................................................................................................................... 15
Capítulo III. INTELIGENCIA ARTIFICIAL EN LOS JUEGOS DE ESTRATEGIA ...................... 19
Comienzos .................................................................................................................... 21
Primeros pasos con MiniMax ....................................................................................... 24
El reto del ajedrez ........................................................................................................ 28
Redes neuronales ......................................................................................................... 37
Primer programa prácticamente imbatible: Deep Blue .............................................. 41
Un contrincante de Go completamente imbatible ...................................................... 49
Capítulo IV. ProjectAI ...................................................................................................... 54
Introducción a ProjectAI .............................................................................................. 54
Arquitectura general .................................................................................................... 56
Diseño general ............................................................................................................. 57



1

Proyecto Fin de Grado – Ingeniería del Software

Capítulo V. MiniMax ....................................................................................................... 62
Introducción a MiniMax ............................................................................................... 62
Pseudocódigo ............................................................................................................... 66
Diseño y desarrollo ...................................................................................................... 67
Capítulo VI. RECOPILACIÓN DE DATOS Y RESULTADOS ................................................ 76
Conclusiones ................................................................................................................... 79
Bibliografía y recursos web ............................................................................................ 81
Índice de figuras .............................................................................................................. 86



2


Aplicación de inteligencia artificial en videojuegos…


RESUMEN

Actualmente, los videojuegos forman parte del día a día de un gran porcentaje de
personas, con
independencia de su edad, sexo, etc. Estos videojuegos, cuya
complejidad puede variar desde unas pocas líneas de código a proyectos de varios
años que involucran un alto número de programadores y diseñadores no habrían
tenido tal éxito de no haber sido por un factor determinante: el desarrollo de la
inteligencia artificial en ellos. Por ello, en este proyecto se presentará brevemente la
historia de la inteligencia artificial en los videojuegos desde sus comienzos, definiendo
los hitos más relevantes y desarrollando un pequeño juego que sirve como ejemplo
para definir los puntos importantes a la hora de desarrollar una inteligencia artificial en
un videojuego.

Palabras clave: inteligencia artificial, MiniMax, Alpha-Beta, ProjectAI, videojuegos


ABSTRACT

Nowadays, video games take part of the routine of a wide range of people, regardless
of their age, gender, etc. These video games, whose complexity can range from a few
lines of code to a several years project involving a large number of programmers and
designers would not have had such success if it was not for a determining factor: the
development of artificial intelligence. Therefore, in this project it will be briefly
presented the history of artificial intelligence in video games from the beginning,
defining the most relevant milestones and developing a small game that serves as an
example to explain the most important points to take into account when the artificial
intelligence of a videogame is being developed.

Keywords: artificial intelligence, MiniMax, Alpha-Beta, ProjectAI, videogames



3

Proyecto Fin de Grado – Ingeniería del Software

Capítulo I. OBJETO Y METODOLOGÍA DE LA INVESTIGACIÓN


INTRODUCCIÓN. - OBJETO DEL PROYECTO. - METODOLOGÍA DE LA INVESTIGACIÓN. - FUENTES. -
ESTRUCTURA DEL TRABAJO.


Introducción

La inteligencia artificial (IA) es uno de los campos de la Ingeniería del Software que más
impacto está teniendo en los últimos años en la sociedad y en el cual se están
invirtiendo gran cantidad de recursos1. El hecho de desarrollar sistemas que sean
capaces de manejar situaciones de manera autónoma y decidir por sí mismos que
opción tomar sin interacción de ningún humano es un reto de gran magnitud en el
que, cada vez más, se ven resultados satisfactorios.

Este desarrollo tiene a su vez unas connotaciones éticas y morales —las cuales tienen
su propia rama de estudio en la ética2—. Si se consigue desarrollar una inteligencia
artificial tan potente como para razonar como un humano deben de plantearse una
serie de cuestiones éticas que abarcan diferentes puntos, tanto que las máquinas no

1 Como muestra sirven algunas noticias publicadas en los últimos tiempos, entre ellas: “Inteligencia
artificial: una inversión atractiva para el capital de riesgo” (Expansión, 13/04/2017. Accesible desde:
http://www.expansion.com/economia-
digital/innovacion/2017/04/13/58ef5788ca4741445d8b45a0.html); “Inversión en robótica e inteligencia
artificial”
desde:
http://www.vozpopuli.com/el_blog_de_paula_mercado/Inversion-robotica-inteligencia-
artificial_7_995670426.html). De hecho, desde enero a junio de 2016, las más de 250 startups dedicadas
a la inteligencia artificial que recoge la base de datos Crunchbase habían recaudado más de 600 millones
de dólares gracias a la inversión en ésta. Fuente: https://nexo.club/la-inteligencia-artificial-en-cifras-
estas-son-las-diez-startups-que-est%C3%A1n-conquistando-el-7731ebf47496
consulta:
01/12/2016]
2 La ética en la inteligencia artificial se divide, a su vez, en otras dos ramas: roboética y ética de las
máquinas.

Paula Mercado,

02/02/2017.

[Fecha de

(El

blog

de

VozPópuli,

Accesible

4


Aplicación de inteligencia artificial en videojuegos…


lastimen a seres humanos o seres vivos en general3, como el estatus moral propio de la
máquina4.

De hecho, los videojuegos y la inteligencia artificial son dos elementos que siempre
han estado fuertemente ligados5. Desde el inicio de la computación, la idea de
conseguir que un ordenador tenga un comportamiento similar al de una persona
humana de una manera principalmente autónoma ha supuesto un gran reto.

Una de las maneras empleadas para conseguir esto es comprobar si la máquina es
capaz de realizar tareas humanas, como por ejemplo, mantener una conversación
sobre cualquier tema sin que la persona que participa sepa si está conversando con
otro humano o con una máquina. Para ello, se realiza el test de Turing. Otro ejemplo
posible es mediante el trading, donde mucha gente trabaja desarrollando software
que sea capaz de invertir en bolsa de manera