• Author / Uploaded
• jt18_149723

• Categories
• Algoritmos
• Ingeniería informática
• Áreas de la informática
• Informática
• Tecnología

Citation preview

Implementación del juego tres en línea empleando FPGA Freddy Alexánder Castillo Forero Nelson Galvis Villalobos Diego Alejandro Rincón Wilches Wílmer Javier Arias Páez Elkin Giovanni Chinome Andrés Esteban Vela Cristian Camilo Bernal Ariza George Michael Salcedo Jiménez Iván Darío Bernal Nieto

*

[email protected] [email protected] [email protected] [email protected] [email protected] [email protected] [email protected] [email protected] [email protected]

Grupo espacio académico Circuitos Digitales II quinto semestre.

*

AGOSTO··2010··3 ISSN··1909-9142

coningenio Resumen

Grupo espacio académico Circuitos Digitales II Quinto Semestre

…

Implementación del juego tres en línea empleando FPGA

…

pp. 158-167

El juego tres en la línea es un juego agradable, cuando se tiene la opción de ganar, por el contrario en esta versión el juego tiene un camino diferente, alcanzando que la máquina siempre gana o empata cuyo procedimiento es explicado con atención en este informe.

Palabras Clave: Quartus, altera, Gate, Input, Output, compilador, projecto, archivo, simulación, asignación, pin.

Implementation of three online game using FPGA

Abstract

The game three in line it is an enjoyable game, when one has the option of winning, by the contrary in this version the game have a different way, achieving that the machine always wins or tie whose procedure is explained attentively in this report.

Key Words: Quartus, altera, Gate, Input, Output, compilator, project, file, simulation, assignment, pin.

159 AGOSTO··2010··3

ISSN 1909-9142

Grupo espacio académico Circuitos Digitales II Quinto Semestre

…

Implementación del juego tres en línea empleando FPGA

C

INTRODUCCIÓN

…

pp. 158-167

coningenio

una línea de tres de sus símbolos: la línea puede ser horizontal, vertical o diagonal.

Como se sabe, el juego tres en línea que para muchos países se conoce con otro

Esta partida la gana el primer jugador, X:

nombre, es un juego de destreza mental de grado fácil, ya que es un juego que se plantea en una matriz de tres por tres por lo cual su dificultad no es compleja, como el caso del ajedrez o sudoku. Este juego consiste en ubicar tres caracteres iguales en

Esta partida termina en empate:

una posición horizontal, vertical y/o diagonal, para ganar el juego. Por lo tanto a lo largo de este informe se plantea un diseño característico del jue-

Los jugadores no tardan en descubrir que el juego perfecto ter-

go tres en línea, el cual consiste en que el

mina en empate sin importar con qué juega el primer jugador.

usuario no le podrá ganar a la máquina.

OBJETIVOS

La misma simplicidad del juego de tres en raya lo hacen ideal como herramienta pedagógica para enseñar los conceptos de teoría de juegos y la rama de inteligencia artificial que se

Diseñar y optimizar el juego tres en línea

encarga de la búsqueda de árboles de juego. Por lo tanto se

identificando todas las jugadas posibles

puede escribir un programa informático que juegue perfecta-

que el usuario pueda hacer para encontrar

mente al tres en raya y que enumere las 765 posiciones esen-

una secuencia que lleve a la máquina a

cialmente distintas o las 26.830 partidas posibles (compleji-

empatar o ganar y así prevenir las posibles

dad del árbol de juego).

jugadas del usuario que lleven a la máquina a perder.

Mini-Max y Máquina de Estado Mini-max es un método de decisión para minimizar la pérdi-

Visualizar el video juego en una VGA me-

da máxima esperada en juegos con adversario y con informa-

diante el uso de un dispositivo (FPGA) que

ción perfecta. Mini-max es un algoritmo recursivo.

contiene bloques de lógica cuya interconexión y funcionalidad se puede progra-

El funcionamiento de Mini-max puede resumirse como elegir

mar, de un periférico bidireccional (Tecla-

el mejor movimiento suponiendo que el contrincante esco-

do) que realiza la interacción con el sistema

gerá el peor.

permitiendo al usuario introducir datos.

MARCO TEÓRICO

Este método nos permite realizar una secuencia basada en el diseño de un árbol y así encontrar los caminos de alto riesgo. Por lo tanto este diseño nos permite encontrar toda la se-

Tres En Línea

cuencia ganadora del juego a diseñar.

El tres en línea, también conocido como tres en raya, es un juego de lápiz y papel

Las máquinas de estados se definen como un conjunto de es-

entre dos jugadores: O y X, que marcan los

tados que sirve de intermediario en esta relación de entradas

espacios de un tablero de 3×3 alternada-

y salidas, haciendo que el historial de señales de entrada de-

mente. Un jugador gana si consigue tener

termine, para cada instante, un estado para la máquina, de

160 AGOSTO··2010··3 ISSN··1909-9142

coningenio

Grupo espacio académico Circuitos Digitales II Quinto Semestre

…

Implementación del juego tres en línea empleando FPGA

…

pp. 158-167

forma tal que la salida depende únicamente del estado y las

los centros (2,4,6,8) y finalmente la ca-

entradas actuales.

silla del centro.

ESPECIFICACIONES

•

Después de generar las posibilidades de juego para cada ubicación del table-

Diseñar un sistema que garantice que la máquina siempre

ro de tres en línea, se analiza el table-

gane o empate, demostrando que en cada jugada el sistema

ro, de forma que con un solo árbol se

tenga la capacidad de identificar la posición de él y del juga-

pueda responder a todas las demás ju-

dor y así realizar la jugada más óptima para ganar.

gadas, esto es posible si se realiza una rotación ordenada del tablero del tres

El usuario siempre comenzará realizando la primera jugada

en línea, de manera que se ubique la

lo cual hace que el sistema reconozca el movimiento y así

casilla de inicio de la jugada del usua-

responda adecuadamente.

rio, como la casilla de inicio de nuestro árbol, dado que este resuelve cada

Visualizar en la pantalla la forma física del tres en línea y

jugada para tener como resultado una

mediante la interacción del teclado dibujar las posiciones que

victoria o un empate, nunca una de-

el usuario y el sistema asignan.

rrota. Este proceso se repite para cada esquina, cada casilla del centro de las

PROCEDIMIENTO

filas y las columnas externas del tablero, teniendo en cuenta que para la

ALGORITMO TRES EN LÍNEA

casilla del centro utilizaremos un ár-

El algoritmo es la parte esencial para el desarrollo del jue-

bol independiente, después de esto, se

go, con la cual se interpreta cada movimiento del jugador y

procede a la programación en VHDL,

se responde de manera que se puedan optimizar las posibi-

esta programación se realiza en ins-

lidades de ganar y de impedir que el usuario tenga alguna

tancias por aparte, de manera que se

posibilidad de conseguir una jugada con la cual pueda de-

pueda aplicar las tres programaciones

rrotar la máquina.

a un bloque que escogerá el algoritmo a utilizar y cuál será el valor a repre-

El desarrollo de las posibilidades de las jugadas aumenta expo-

sentar en la VGA.

nencialmente a medida que avanza el juego, para esto decidimos reducir las posibilidades del juego de la siguiente manera:

•

Al programar las tres instancias las cuales son los tres árboles, estas re-

•

•

Generar árboles con las cuales se analiza cada posibili-

suelven las jugadas por medio de es-

dad de juego que se pueda presentar, respondiendo a los

tados presentes en cada posibilidad de

diferentes movimientos que el usuario realice de mane-

juego y así se generan unos bloques

ra práctica, de tal forma que se puedan bloquear todas

que integran todos los comandos de

las posibilidades de que el usuario gane y de facilitar las

entrada y mediante las demás instan-

oportunidades de victoria de la máquina.

cias este resultado se entrega a la VGA.

En los árboles se observó un comportamiento de simetría

•

Una de estas instancias es la encarga-

en el tablero del tres en línea, ya que si se comienza a ana-

da de recibir las señales de entrada y

lizar las jugadas desde las esquinas (1,3,7,9) siempre serán

convertirlas según la rotación ordena-

los mismos movimientos a si se empezará en una misma

da a números que el árbol pueda solu-

esquina, lo mismo funciona para las casillas ubicadas en

cionar, en cada caso según correspon-

161 AGOSTO··2010··3

ISSN 1909-9142

Grupo espacio académico Circuitos Digitales II Quinto Semestre

…

Implementación del juego tres en línea empleando FPGA

…

pp. 158-167

coningenio

da, estos números serán tomados por

haber ingresado cada dato a los árboles y de haber sido

cada uno de los árboles y serán contes-

procesado se diseñó una instancia que según el árbol que

tados con la mejor jugada, con aquella

estuviera habilitado escogería qué salidas deberían visua-

que no nos permita perder. Las salidas

lizarse en VGA. En otras palabras en una misma instancia

de cada uno de los tres algoritmos tie-

se controlarían las salidas de los tres árboles, estas serían

ne que ser seleccionados por una ins-

entradas y darían una sola salida, que es la que se podrá

tancia, que revertirá la rotación hecha

visualizar luego de hacer el proceso inverso de la primera

antes de entrar a los árboles para su

rotación, realizada para que se pudieran resolver en los

interpretación y respuesta. Después de

árboles programados.

DISEÑO JERÁRQUICO

162 AGOSTO··2010··3 ISSN··1909-9142

coningenio

Grupo espacio académico Circuitos Digitales II Quinto Semestre

…

CÓDIGOS DISEÑADOS (INSTANCIAS)

Implementación del juego tres en línea empleando FPGA

…

pp. 158-167

CONTROL DE ESTADOS

KEYBOARD

Lee cuatro entradas binarias las cuales Permite la interacción del usuario con el programa, el cual

son controladas por el pulso del reloj y un

funciona con un reloj de 25MHz y nos entrega una salida de

reset que devuelve un estado inicial. De

8 bits codificada en hexadecimal de acuerdo con la tecla que

acuerdo con las entradas se entrega a la

se oprima.

salida un dato binario que activa el res-

DECODIFICADOR

pectivo Algoritmo.

DIVISOR DE RELOJ DE 25MHZ Y 1HZ

Recibe una señal de 8 bits codificada en ASCII, el cual decodifica la señal para entregar cuatro salidas binarias, estas representan el número de la casilla del juego tres en línea.

Estas dos instancias dividen el período del reloj de 50Mhz que se encuentra incluido

(Por Ejemplo 01110011 => 0101 => 5).

de la tarjeta FPGA para realizar correctamente la sincronización de la VGA y Algoritmos, respectivamente.

163 AGOSTO··2010··3

ISSN 1909-9142

Grupo espacio académico Circuitos Digitales II Quinto Semestre

…

Implementación del juego tres en línea empleando FPGA

HABILITADOR

…

pp. 158-167

coningenio

ALGORITMO 5

Recibe la señal de entrada generada por el teclado y habilita las instancias de los árboles según

Lee las cuatro salidas binarias que nos entrega el con-

la posición en la que juega el usuario y su respec-

versor y estas son controladas por el reloj de 1Hz, el

tiva transpuesta según la casilla seleccionada.

cual permite que el algoritmo pueda responder adecuadamente y así ejecutar la secuencia de las jugadas que

CONVERSOR

realiza el usuario cuando comienza con la tecla cinco.

ALGORTIMO 2

Recibe las señales que entrega el habilitador y el teclado (SCAN_CODE) para generar las rotaciones respectivas de acuerdo con las señales de entrada y así entregar cuatro salidas binarias que sean legibles para los árboles programados.

164 AGOSTO··2010··3 ISSN··1909-9142

coningenio

Grupo espacio académico Circuitos Digitales II Quinto Semestre

Lee las cuatro salidas binarias que nos entrega el conversor y estas son controladas por el reloj de 1Hz, el

…

Implementación del juego tres en línea empleando FPGA

…

pp. 158-167

DEMUX

cual permite que el algoritmo pueda responder adecuadamente y así ejecutar la secuencia de las jugadas que realiza el usuario cuando comienza con la tecla dos.

ALGORITMO 7

Lee las cuatro salidas binarias que nos entrega el conversor y estas son controladas por el reloj de 1Hz, el cual permite que el algoritmo pueda responder adecuadamente y así ejecutar la secuencia de las jugadas que realiza el usuario cuando comienza con la tecla siete.

Recibe las señales de los tres algoritmos y del habilitador e identifica la traspuesta que hay que realizar para entregar los datos a la instancia de VGA seleccionando las salidas del árbol activo que está resolviendo.

165 AGOSTO··2010··3

ISSN 1909-9142

Grupo espacio académico Circuitos Digitales II Quinto Semestre

…

Implementación del juego tres en línea empleando FPGA

VGA

…

pp. 158-167

coningenio

En este diagrama encontramos la representación gráfica del juego tres en línea, el cual mediante una matriz de tres por tres se dibuja la posición en la que el usuario juega, siendo el color rojo la jugada por la máquina y el azul la jugada por el usuario.

CONCLUSIONES Por medio del estudio de circuitos digitales podemos describir comportamientos de sistemas reales tan complejos en su desarrollo como lo es un juego que exige cierto nivel de destreza mental y utilizando los conocimientos adquiridos presentar una posible solución e implementación. La implementación de sistemas de análisis como los algoritmos Minimax y la heurística son muy útiles para la identificación de soluciones que permiten mejorar la visión de la estructura temática del programa, generando mejores Muestra la visualización del juego máquina vs jugador, la cual funciona con una frecuencia de 25 MHz para poder realizar el sincronismo horizontal-vertical y así ver los movimientos realizados en el transcurso del juego.

REPRESENTACIÓN GRÁFICA

alternativas de respuesta, dando como resultado un sistema solución por medio de la aplicación discreta o por diseño de jerarquías. Es necesario tener en cuenta la distribución de las partes que componen el sistema con respecto a la jerarquía establecida, pues esta permite tener una mejor manipulación de rutas de cada instancia, provocando una mejor eficiencia en el resultado y optimización del circuito. A través de cada uno de los obstáculos que se presentan en el diseño y programación de cierto sistema hay que aprender de ellos para que se conviertan en una fortaleza del sistema y lograr un excelente desarrollo del programa o de la solución planteada.

166 AGOSTO··2010··3 ISSN··1909-9142

coningenio REFERENCIAS

with VHDL. MIT press. 2004 4. Wakerly, John F. Diseño Digital

1. Pedroni, Volnei A. Digital Electronics and design with VHDL. Morgan Kaufman Publishers. 2008 2. Mano, M. Morris y KIME., Charles R. Fundamentos de diseño lógico y de computadoras. Pearson Educación. Tercera edición. 2005 3. Pedroni, Volnei A. Circuit Design

“Principios y prácticas”. Pearson Educación. 2001 5. Tocci, Ronald J y WIDMER., Neal. Sistemas Digitales. Pearson Educación. 2003 6. Vyemura, John P. Diseño de Sistemas

Digitales.

Internacional

Thomson editores, 2000

167 AGOSTO··2010··3

ISSN 1909-9142