[Ajedrez-FPGA] Alguien sabe si esto es posible?

El_RapEro escribió:Buenas, por no extenderme demasiado, diré que tengo que hacer "algo" con una FPGA, relativamente complicado, y que implique comunicación con el PC (esto no es obligatorio, pero es la mejor forma de "hablar" con ella, si no quieres usar los botones e interruptores que tiene). Esta comunicación sería por el puerto serie.
Se me había ocurrido un ajedrez, pero puede que sea imposible, no lo sé (la verdad es que nunca he intentado programar un PC, ni si quiera en software).
Implicaría una aplicación en java que haga uso del puerto serie y un tablero dibujado (por cutre que sea); el tablero tendría que estar sincronizado con el de la FPGA (que estaría en una memoria sin más) y básicamente tendrían que enviarse los movimientos a realizar.

Conforme lo digo se me quitan las ganas de intentarlo lo que más me preocupa evidentemente es la "inteligencia artificial" que habría que meter en la FPGA para decidir el siguiente movimiento; alguien conoce/tiene/sabe donde hay alguna implementación de un motor de ajedrez SIMPLE? no pueden ser cálculos ultracomplejos en coma flotante con logaritmos ni cosas enrevesadas, ya que en la FPGA se hará uso del código de un procesador ya hecho, y es bastante limitado, entre otras cosas su ancho de palabra es 8 bits así que ya os podéis imaginar.

Se aceptan otras ideas de todas formas. Saludos.

Lo más comùn a la hora de implementar un programa que juegue al ajedrez son los algoritmos de poda alfa-beta,http://en.wikipedia.org/wiki/Alpha-beta_pruning, o para más detalle http://aima.cs.berkeley.edu/ capítulo 5 apartado 3. No sé nada de FPGA, así que echale un vistazo a eso, y ya decidirás si es posible.

Un saludo.

PD: No son cálculos en coma flotante (según recuerdo), pero son algoritmos costosos en complejidad. Por otro lado el ancho 8 bits que comentas, limitará bastante la profundidad del arbol, por lo tanto la poda deberá ser mayor, y por ende, tu máquina juega peor al ajedrez, puesto que tiene menos "visión de futuro". Pero vamos, que no sé nada de FPGA, si yo fuese tu todos los cálculos se harían en el pc, y los dibujos se mandarían a la FPGA y que esta sólo se encargue de dibujar.

Muchas gracias 4eVaH por tu aporte, ahora mismo le echo un ojo.
El objetivo en realidad es hacer "algo" con la FPGA, que puede ser esto o puede ser un simple codificador; le envías datos por el puerto serie y te los devuelve de otra forma (claro que no estará igual de valorado algo muy simple o algo muy complejo).
Se me ha ocurrido lo del ajedrez con la idea de que la FPGA fuera el "cerebro" del juego, vamos que la GUI, dibujos, interacción con el usuario, todo estaría en el PC, la FPGA sería quien recibe los movimientos que yo hago y quien decide su propio movimiento.
Si veo que no es viable con todas estas limitaciones lo dejo de lado y pienso otras cosas...ya que si todos esos cálculos los hace el PC pierde un poco la gracia . Si pudiera hacerlo, aunque fuera a pocos niveles de profundidad (uno, o dos) me doy con un canto en los dientes, aunque se le gane fácilmente.

Lo dicho, voy a ver si leo un poco.

Si ves que se te complica mucho, siempre puedes hacer unas damas o un hundir la flota

Si haces algo como esto, te aseguras una matrícula de honor:

http://hackaday.com/2009/10/17/nes-proc ... on-a-fpga/

Lo de las damas es buena idea también. Por lo menos la complejidad computacional es mucho menor y no deja de ser un gran trabajo. Lo de hundir la flota lo había descartado porque no sería el primero, por lo visto es un recurso bastante socorrido , porque básicamente le envías la posición a la FPGA y ella (teniendo el tablero almacenado) te dice si lo has tocado o no.
Y no es que sea fácil tampoco, es sólo que estaba buscando algo que me motive un poco. Voy a mirar también lo de las damas.

Lo del procesador de la NES se lo dejo a los más freaks...menudo curro se habrán pegado.

En una FPGA medio decente puedes meter microprocesadores de 32 bit bastante decentes, como el microblaze si la fpga es de xilinx y relativamente reciente, o tambien tienes el OpenRISC o el OpenSPARC. con eso ya puedes hacer algún algoritmo decente.

de todas formas con 8 bit también puedes hacer algo majo. con ponerle algo de limite a la recursión.

prueba a enredar en C o java con tipos de datos de 1 byte como máximo e intenta implementarte el algoritmo solo con eso a ver si eres capaz.

demnim escribió:En una FPGA medio decente puedes meter microprocesadores de 32 bit bastante decentes, como el microblaze si la fpga es de xilinx y relativamente reciente, o tambien tienes el OpenRISC o el OpenSPARC. con eso ya puedes hacer algún algoritmo decente.

de todas formas con 8 bit también puedes hacer algo majo. con ponerle algo de limite a la recursión.

prueba a enredar en C o java con tipos de datos de 1 byte como máximo e intenta implementarte el algoritmo solo con eso a ver si eres capaz.

Sí, por ahí es por donde comenzaré, centrándome en software. Y sí, tienes razón, pero hay algo que no he comentado (más que nada porque no creía que la gente fuera a conocerlo) y es que estamos obligados a usar picoblaze, imagino que una versión reducida del que tú comentas, y éste es de 8 bits.

Saludos!

Rapero, cualquier juego de turnos que se te ocurra, la mejor idea "algoritmos de poda alfa beta".
Lo bueno es que hay juegos para los que la profundidad necesaria del arbol es mucho menor que la del ajedrez, por ejemplo el 3 en ralla, 4 en ralla...

Respecto a las damas: piensa en la cantidad de jugadas posibles en una partida de damas... piensa en que algoritmo más o menos decide la mejor jugada siguiendo este razonamiento: "Posibles jugadas que tengo, para cada una miro las posibles jugadas de mi oponente si la hiciese, para cada una de mi ponente miro las mias... y ahora valoro lo positivo de la situación desde el final hasta arriba, y cojo el camino que más valoré.... evidentemente cuanto mas profundo sea ese árbol, más probabilidad de cojer la jugada correcta, pero cuanto más posibilidades haya por cada nivel del árbol, más complejo es el algoritmo tanto en tiempo como en espacio, y es precisamente en espacio lo que te preocupa, porque sólo dispones de 8 bits, lo que limita la cantidad de memoria direccionable, no sé si tanto como para que unas damas no funcionen.

Teniendo eso en cuenta piensa juegos que no sean demasiado complejos; hay cantidad de juegos pensados sólo para el estudio de este tipo de algoritmos, por ejemplo el mancala, que sin ser juegos complejos, es interesante su estudio para evaluar la bondad de este tipo de algoritmos.

El mancala creo que en tu fpga va de sobra. Saludos.

Edit: Joder que fallo, confundí el sokoban con el mancala, que si es un juego por turnos sencillo, que se puede hacer con poda alfa-beta; se me cruzaron los cables con otro juego que se puede resolver usando algoritmos típicos de IA.

coincido con 4eVaH en cuanto a la poda alfa-beta.

otra posibilidad sería complementar el algoritmo minimax con alguna muy buena heurística para la decisión.

un saludo

Jaja, pues yo me puse a buscar información del sokoban y hasta me planteé un algoritmo "resolvedor" de sokobans, pero efectivamente no me cuadraba eso con lo que hablábamos. Miraré el mancala.
Respecto a las damas, en el hipotético caso de que fuera viable (aunque fuese con sólo un par de niveles de profundidad) he visto algo que me solucionaría la parte gráfica. Hay una implementación de las damas cuya GUI está separada del motor, de forma que cumpliendo una interfaz específica puedes hacer funcionar cualquier motor con esa GUI. Yo tendría que implementar una dll (en el caso de un entorno windows, como es el caso porque es obligatorio) que se comunicara con la FPGA por un lado, y por el otro con esa GUI, abstrayéndola del todo de la existencia de la FPGA. Parece bastante cómodo porque te quitas el trabajo sucio de encima, aunque la implementación del algoritmo en la FPGA es el verdadero reto...no sólo por ancho de palabra, sino por cantidad de instrucciones e incluso de memoria, tengo que hablar con el profesor para ver qué opina.

Saludos.

Es algo más complicado que mancala, pero otro juego con no muchos movimientos es Gatos y ratón, y deberías poder usar xboard/winboard, una gui para ajedrez con la que te puedes comunicar desde fuera.

Yo hice esas mismas prácticas hará como 2 años creo.

Teniendo en cuenta que el código que va a ejecutar el picoblaze tienes que programarlo en ensamblador y que, segun creo recordad, hay un límite de instrucciones debido a la cantidad de memoria, se te va hacer bastante complicado implementar cuanlquier cosa medio complicada. Además, la chicha de la práctica no esta en el código del software, lo cual no deja de ser programar en ensamblador y poco más, aún menos en la interfaz java/matlab/o lo que tu quieras, la chicha esta en que hay que currarse 2 módulos externos al microprocesador utilizando la interfaz I/O de este, si lo que quieres es clavar la práctica, tienes muchas más posibilidades de obtener una nota cojonuda haciendo un módulo externo de puta madre, creo que la placa tiene una salida VGA y cosas así. Según recuerdo también era obligatorio añadir una instrucción propia al conjunto de instrucciones del microprocesador.

Bueno, ahi dejo esto dicho, por si mi experiencia te sirve de algo.

P.D. Yo hice unos barquitos con unos 10 mapas aleatorios metidos en una ROM con una RAM para la partida actual. Si no recuerdo mal lo hice operando a nivel de bit (1 barco, 0 agua) y con una interfaz en modo texto a base de comandos de terminal. Nada del otro mundo, pero para aprobar la asignatura sobraba.

Sertinell escribió:Yo hice esas mismas prácticas hará como 2 años creo.

Teniendo en cuenta que el código que va a ejecutar el picoblaze tienes que programarlo en ensamblador y que, segun creo recordad, hay un límite de instrucciones debido a la cantidad de memoria, se te va hacer bastante complicado implementar cuanlquier cosa medio complicada. Además, la chicha de la práctica no esta en el código del software, lo cual no deja de ser programar en ensamblador y poco más, aún menos en la interfaz java/matlab/o lo que tu quieras, la chicha esta en que hay que currarse 2 módulos externos al microprocesador utilizando la interfaz I/O de este, si lo que quieres es clavar la práctica, tienes muchas más posibilidades de obtener una nota cojonuda haciendo un módulo externo de puta madre, creo que la placa tiene una salida VGA y cosas así. Según recuerdo también era obligatorio añadir una instrucción propia al conjunto de instrucciones del microprocesador.

Bueno, ahi dejo esto dicho, por si mi experiencia te sirve de algo.

P.D. Yo hice unos barquitos con unos 10 mapas aleatorios metidos en una ROM con una RAM para la partida actual. Si no recuerdo mal lo hice operando a nivel de bit (1 barco, 0 agua) y con una interfaz en modo texto a base de comandos de terminal. Nada del otro mundo, pero para aprobar la asignatura sobraba.

Sirve de mucho, gracias
La idea es cargar todo o prácticamente todo el proceso sobre uno o varios componentes externos, dejando al picoblaze y su código ensamblador como un mero intermediario entre éstos, realizando operaciones de escritura y lectura sobre ellos (y por supuesto comunicándose con el PC), porque como dices hay un límite de instrucciones, y no es que sea muy grande. Lo que más me preocupa es la memoria, porque imagino que esos componentes no pueden acceder a ella directamente, por lo menos no de forma común.
De todas formas como digo sólo estamos divagando un poco, dedicaremos esta semana a valorar la posibilidad y a hablar con el profesor, si vemos que va a ser imposible o tremendamente difícil hacerlo, a otra cosa y listo.
En cualquier caso en una semana tenemos que tenerlo claro ya para empezar a trabajar en semana santa.

Saludos.

¿Tiene que ser FPGA por obligación? ¿O simplemente tiene que ser una implementación en hardware? Porque si es lo 2º, te recomiendo un Arduino que se comunica por puerto serie-usb y es mucho mucho mas fácil de programar....aparte que es de lejos mas barato que una FPGA .