pyAwale AI
==========

:abstract: 
  This part describe the algorithms implemented by our game engine.


Breadth-First Search
--------------------

A simple BFS_ algorithm: 
For each nearest nodes, it explores their unexplored neighbour nodes,
and so on, until it finds the goal (ie. find a move that capture
seeds).

.. _BFS: http://en.wikipedia.org/wiki/Breadth-first_search

The *BFS* algorithm is limited to a depth of 6 (ie. 46 656
possibilities).

MiniMax
-------

The recursive algorithm minimax_ tries to find the best choice which
maximizes its benefit while minimizing those of its adversary.

We use a heuristic evaluation function (which takes into account the
benefit for the player and his adversary) to limit the minimax
algorithm to look only at a certain number of moves ahead.

.. _minimax: http://en.wikipedia.org/wiki/Minimax

This is the default algorithm used by our engine.

Maximise
--------

The *maxi* algorithm is a fork of minimax_ algorithm that try to
maximine the 'absolute' profits of the player (ie. do not try to
minimize profits of the adversary).

.. Give poor results.

NegaMax algorithm
-----------------

The negamax_ search is a slightly variant formulation of minimax
search that relies on the zero-sum property of a two-player game.

.. _negamax: http://en.wikipedia.org/wiki/Negamax

.. Better results at level=2

AlphaBeta
---------

Currently the alphabeta_ pruning is implemented with the `NegaMax
algorithm`_.

.. _alphabeta: http://en.wikipedia.org/wiki/Alpha-beta_pruning