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.
