Dedicado a mis proyectos en Gambas ,un lenguaje de programación parecido al Visual Basic + Java pero ampliamente mejorado y...¡¡para gnu/linux!!.La potencia del gnu/linux sumada a la facilidad del Basic



Consultas, Desarrollo de programas y petición de presupuestos:



sábado, 15 de septiembre de 2012

Algoritmo MiniMax-Poda Alfa Beta: Creando la IA de los juegos



¿como piensa un ordenador que juega al ajedrez?
Esta es una de las cuestiones que siempre me plantee cuando tuve mi primer ordenador y empece a programar en Basic....

Pues bien, gracias a internet, he encontrado mucha información... el algoritmo que se usa es el minimax  (o variantes sobre este)...

En la wikipedia, en ingles,  encontre el algoritmo, ademas de varios enlaces interesantes... entre ellos uno que desarrolla gráficamente cualquier "arbol" que le demos...




Me hecho un pequeño esquema, con los pasos y los cambio de valores: Enlace

PseudoCódigo:

function alphabeta(node, depth, α, β, Player)         
    if  depth = 0 or node is a terminal node
        return the heuristic value of node
    if  Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Beta cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Alpha cut-off *)
        return β


(* Llamada INicial: *)
alphabeta(ORIGEN NODO, depth, -infinity, +infinity, MaxPlayer


Aqui teneis un código de ejemplo realizado en java:
intart/source/browse/trunk/juegos/base/_AgenteHeuristico.java?r=35





Enlaces:
http://en.wikipedia.org/wiki/Alpha-beta_pruning
http://homepage.ufp.pt/~jtorres/ensino/ia/alfabeta.html
http://joshi.ueuo.com/proyectoU1.php
Programacion de Ajedrez mediante minimax poda alfa beta.Pdf