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.

domingo, outubro 03, 2010

Design of Design @ InfoQ

Do you have a short list, say six bullet point items, that would summarize the most important lessons your book offers to designers?
  1. Study your predecesssors' works intently, to see how they solved problems.
  2. Try to figure out why they made the design choices they did; this is the most illuminating question to ask yourself.
  3. Study your predecessors' styles closely. This is best done by trying to sketch something in their several styles.
  4. Keep a "sketch book" in which you put ideas, designs, and pieces of designs, whatever your medium.
  5. When starting a design, write down your assumptions about the users and the uses.
  6. Design, design, design!
What other areas of study would improve a graduate's ability to be a great software designer?
  1. Algorithms and data structures is the most essential study.
  2. Computer hardware architecture.
  3. Application areas, especially business data processing, database techniques and data mining.
  4. Psychology, especially perceptual psychology, since the user is all-important.
Can you identify 3 Master Designers (any field) and 3 Master Software Designers, and 4 or five Master Designs. Exemplars we should all be studying and a short idea of why they are what they are?
  • J.S. Bach, compositions
  • Rembrandt, paintings and drawings
  • Seymour Cray, supercomputers
  • Christopher Wren, buildings, especially his London churches.
  • Nicholas Wirth, programming languages
  • Donald Knuth, algorithms

domingo, setembro 26, 2010

Resolvendo UKP em Erlang.

Comecei a estudar Scala e foi batendo uma saudade de Erlang.
Resolvi atualizar a versão instalada no meu notebook da 11B pra 14B e pesquisei se já havia um plugin pra Eclipse pra Erlang e felizmente existe: Erlide. Se alguém conhecer um plugin melhor peço que me enviem, mas por enquanto o Erlide está me atendendo.

Após um revisão da linguagem aproveitei o clima de nostalgia e resolvi testar meus conhecimentos implementando o algoritmo de Garfinkel e Nemhauser para resolução de Unbounded Knapsack Problems (aka: UKP) ou em bom português: Problema da Mochila Ilimitada.












Para rodar basta executar no console do Eclipse (ou no shell do Erlang):
 ukpGN({{1,1,1},{2,3,4},{3,3,5}}, 5).
(Ou seja, resolva o problema para o cenário com:
Objeto 1 - peso 1 e valor 1
 Objeto 2 - peso 3 e valor 4
 Objeto 3 - peso 3 e valor 5
e "mochila" com capacidade para suportar peso de até 5)
Resposta:
[{1,2},{3,1}]
(Ou seja, objeto 1 aparece 2 vezes  e objeto 3 aparece 1 vez na solução ótima encontrada).

Da próxima vez quero ver se implemento algum algoritmo para computação distribuída em Erlang, já que esse é o grande appeal da linguagem.

quinta-feira, setembro 23, 2010

The Design of Design.

Resolvi dar uma passeada hoje após o trabalho na Livraria Cultura do Conjunto Nacional e ao passar os olhos pelos livros de IT me deparei com um livro que me despertou o interesse (a ponto de comprá-lo):

The Design of Design : Essays from a computer scientist  -- Frederick P. Brooks, Jr.

Making Sense of Design
Effective design is at the heart of everything from software development to engineering to architecture. But what do we really know about the design process? What leads to effective, elegant designs? The Design of Design addresses these questions.


Ou seja, aguardem posts futuros sobre minhas viagens na (lenta) leitura do mesmo.

segunda-feira, fevereiro 01, 2010

Fracassa suicídio homeopático de céticos britânicos

Leia reportagem completa em:
http://www.sedentario.org/colunas/duvida-razoavel/fracassa-suicidio-homeopatico-24162

"Precisamente às 10:23 da manhã do último dia 30 de janeiro, mais de 400 céticos britânicos ingeriram quantidades maciças de remédios homeopáticos buscando uma “overdose” que, se a homeopatia funcionasse, deveria ter causado sérias consequências. Felizmente, como se queria demonstrar, todos saíram ilesos deste protesto público contra a venda de “remédios” homeopáticos que não possuem qualquer efeito comprovado além do placebo. Uma overdose de pílulas de açúcar não tem efeito maior do que uma bala."