sexta-feira, novembro 19, 2010

AlphaBetaNegaMax em Erlang.

Faz algum tempo fui no Ludus Luderia onde conheci muitos jogos novos e bastante interessantes.
Um jogo de regras bastante simples mas de estratégia não trivial é o Hasami Shogi. Como sempre gostei de implementar jogos de estratégia, fiz uma versão em Java do mesmo para me divertir e treinar algumas idéias e nessa semana pensei: esse jogo pode ser um bom exercício pra comparar um sistema desenvolvido em Java com um sistema em Erlang, e então comecei a portar o jogo. Segue um módulo Erlang com o algoritmo mais interessante de qualquer IA para jogos de estratégia: a busca na árvore de jogos. Dentre os diversos algoritmos resolvi implementar dessa vez um dos mais tradicionais: o Alpha-Beta NegaMax.




%% Author: flavio
%% Created: 18/11/2010
%% Description: Main IA algorithm for strategic games.
-module(engine).

-define(INFINITY, 1000).
-define(MAX_DEPTH, 10).

%%
%% Include files
%%
-include("hasami.hrl").
%%
%% Exported Functions
%%
-export([machineMove/2]).

%%
%% API Functions
%%

machineMove(Board, Color) -> {Move, Eval} = abNegamax(Board, Color, 0, -?INFINITY, ?INFINITY), 
        io:format("Computer eval: ~p~n", [Eval]),
        Move.

%%
%% Local Functions
%%

abNegamax(Board, Player, CurrentDepth, Alpha, Beta)-> 
 IsGameOver = board:isGameOver(Board),
 if 
  IsGameOver -> Eval = board:evaluate(Board, Player, CurrentDepth), {nil, Eval};
  CurrentDepth >= ?MAX_DEPTH -> Eval = board:evaluate(Board, Player, CurrentDepth), {nil, Eval};
  true -> search(Board, board:getMoves(Board),Player, CurrentDepth, -?INFINITY , nil, Alpha, Beta)
 end.

search(Board, [Move| Tail], Player, CurrentDepth, BestScore, BestMove, Alpha, Beta) -> 
 B1 = board:makeMove(Board, Move),
 {CurrentMove, CurrentVal} = abNegamax(B1, Player, CurrentDepth+1, -Beta, -max(Alpha, BestScore)),
 CurrentScore = -CurrentVal,
 if CurrentScore > BestScore -> 
     if CurrentScore >= Beta -> board:undoMove(B1, Move),
           {CurrentMove, CurrentScore};
        true -> B2 = board:undoMove(B1, Move), 
          search(B2, Tail, Player, CurrentDepth, CurrentScore, Move, Alpha, Beta)
     end;
    true ->  B2 = board:undoMove(B1, Move),
    search(B2, Tail, Player, CurrentDepth, BestScore, BestMove, Alpha, Beta)
 end;

search(Board, [], Player, CurrentDepth, BestScore, BestMove, Alpha, Beta) -> {BestMove, BestScore}.




Em termos de quantidade de linhas de código não há muita diferença nesse módulo... bem, pra ser honesto em Erlang ficou um pouquinho menor :-) mas nada significativo. Vamos ver como ficará o balanço final.