# Awalé Game

Awalé or Oware is a game of great antiquity, and has been played around the world in various forms for millenia. Currently it is the official board game of Africa.

Member of the mancala family of board games. There are many variants to the rules of this game, which is for two players.

Contents

- Quick Start
  - Launch
  - Command line options
- Command Line Interface
  - Commands
- Pygame User Interface
  - Introduction
  - Game panel
  - End game
- Abapa Rules
  - Board
  - Goal
  - The game
    - Maneuver
    - Omitting a house
    - Capturing seeds
    - Let the opponent play
    - End of game
- pyAwale AI
  - Breadth-First Search
  - MiniMax
  - Maximise
  - NegaMax algorithm
  - AlphaBeta

# Quick Start

## Launch

After being installed, simply launch:

    $ pyawale

See `--help` for more options.

## Command line options

`-a ALGO, --algo=ALGO`
| Choose the algorithm to use (bfs, minimax, maxi, negamax or alphabeta).
`-l LEVEL, --level=LEVEL`
| Set the difficulty level of the game.
`-c, --cli` | Switch to command-line interface (default if Pygame not installed).

# Command Line Interface

    mickey@bunny:~$ pyawale --cli

      pyAwale is a free software available under the terms of the GNU GPL.
      Refer to the file COPYING (which should be included in this distribution)
      for the specific terms of this licence.
      You can freely download pyAwale and enjoy to play with it.

    pyAwale> help

    Documented commands (type help <topic>):
    ========================================
    EOF  algo  display  info  level  sow

    Undocumented commands:
    ======================
    help

    pyAwale> display
                 f    e    d    c    b    a
    North ( 0) [ 4] [ 4] [ 4] [ 4] [ 4] [ 4]
               [ 4] [ 4] [ 4] [ 4] [ 4] [ 4] ( 0) South
                 A    B    C    D    E    F
    pyAwale>

## Commands

info: | Display engine settings/parameters.
algo: | Display/toogle to another algorithm (bfs, minimax, maxi, negamax or alphabeta).
level: | Display/set default level of the algorithm (1, 2 or 3).
display: | Show board state and score.
sow: | Sow and capture from given cup (A, B, C, D, E or F); Then, compute adversary move.
EOF: | Exit (C^D under *nix and C^Z under Windows).

So, to begin the game simply begin by sowing from the house of your choice and so on:

    pyAwale> sow E
    South player swon from 'E'
                 f    e    d    c    b    a
    North ( 0) [ 4] [ 4] [ 4] [ 5] [ 5] [ 5]
               [ 4] [ 4] [ 4] [ 4] [ 0] [ 5] ( 0) South
                 A    B    C    D    E    F
    North player swon from 'a' (in 0.010115s)
                 f    e    d    c    b    a
    North ( 0) [ 5] [ 5] [ 5] [ 6] [ 6] [ 0]
               [ 4] [ 4] [ 4] [ 4] [ 0] [ 5] ( 0) South
                 A    B    C    D    E    F
    pyAwale>

# Pygame User Interface

## Introduction

This panel show up the Terms of Use and current settings (algorithm/level used).

You can choose your algorithm and the associated level by using respectively `a` and `l` keys.

Remark: The `h` key show/hide a short usage summary.

Then, to start the game, click on the Awale board.

## Game panel

Simply click on the house to sow seeds.

Note: Hit `c` key (before clicking) for computer begins the game.

On the upper left corner you can see your last move, and the move of the computer.

Remark: When you capture, seeds are stored on the ground on your side.

## End game

When the end of the game is reached, or when you quit the game (with `ESC` key), this panel compute and show you the final score.

PS: Use `RETURN` key to replay or quit with `ESC` key.

# Abapa Rules

abstract: | This part describe the rules implemented by our game; And additionally, explain how to use the python `awale` module.

Our pyAwale game is an implementation of the Abapa Rules (from the Oware Society) as descibed bolow.

## Board

The Awalé consists of a tray dug by 2 rows of 6 pits or cavities called houses (also named holes or cups); the one will be the South camp (player), the other one the North camp (computer). Two extra houses used for storing captured seeds are placed at either side of the board in-between the two rows.

In the beginning of the game, each house receives four seeds:

    >>> from awale import *
    >>> awale = Awale()
    >>> awale
    {'board': [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], 'score': [0, 0]}

P.S. pyAwale libs are deployed with the package `pyawale` into the Python's site-packages.

## Goal

The goal of the game is to capture more seeds than one's opponent (he places them then in its reserve).

## The game

### Maneuver

At each move the player takes the content of one of the houses not empty of his own camp and sow the seeds one by one in the next cups, counter-clockwise.

Sow "D":

    >>> awale.sow_and_capture(3)
    >>> print awale
                 f    e    d    c    b    a
    North ( 0) [ 4] [ 4] [ 4] [ 4] [ 5] [ 5]
               [ 4] [ 4] [ 4] [ 0] [ 5] [ 5] ( 0) South
                 A    B    C    D    E    F

Knowing the number of seeds in each house is, of course, important to gameplay. When there are many seeds in a house, sometimes enough to make a full lap of the board or more, they cannot easily be counted by eye, and their number is often guarded by the player who controls that house. This may be done by repeatedly moving the seeds in the house. A player may count the seeds when contemplating a move; in such cases the last few are usually counted in the hand to avoid revealing their number.

### Omitting a house

In the course of a seedling, you have never to give seed in the square of departure.

Sow "E":

    >>> awale.board = [3, 1, 0, 0, 14, 2, 3, 3, 3, 5, 3, 3]
    >>> awale
    {'board': [3, 1, 0, 0, 14, 2, 3, 3, 3, 5, 3, 3], 'score': [0, 0]}

    >>> awale.sow_and_capture(4)
    >>> print awale
                 f    e    d    c    b    a
    North ( 0) [ 4] [ 4] [ 6] [ 4] [ 5] [ 5]
               [ 4] [ 2] [ 1] [ 1] [ 0] [ 4] ( 0) South
                 A    B    C    D    E    F

### Capturing seeds

If the last sown seed falls in an adverse square containing 1 or 2 seeds, the player captures the content of this square (including the last seed that it comes to sow). It takes equally the content of preceding adverse squares if the former contain then 2 or 3 seeds. These squares allowing supplementary plugs have to form a uninterrupted chain. All plugs are definitive; they constitute the gain of the player.

Sow "D"; Capture "d" and "c":

    >>> awale.board = [0, 3, 0, 6, 1, 2, 0, 0, 2, 1, 0, 3]
    >>> awale
    {'board': [0, 3, 0, 6, 1, 2, 0, 0, 2, 1, 0, 3], 'score': [0, 0]}

    >>> awale.sow_and_capture(3)
    >>> print awale
                 f    e    d    c    b    a
    North ( 0) [ 3] [ 0] [ 0] [ 0] [ 1] [ 1]
               [ 0] [ 3] [ 0] [ 0] [ 2] [ 3] ( 5) South
                 A    B    C    D    E    F

However, if a move would capture all an opponent's seeds, the capture is forfeited, and the seeds are instead left on the board, since this would prevent the opponent from continuing the game (the adversary should not be starved):

    >>> awale.board = [1, 2, 3, 4, 5, 6, 1, 1, 1, 2, 2, 1]
    >>> awale.score = [0, 0]
    >>> awale
    {'board': [1, 2, 3, 4, 5, 6, 1, 1, 1, 2, 2, 1], 'score': [0, 0]}

    >>> awale.sow_and_capture(5)
    >>> print awale
                 f    e    d    c    b    a
    North ( 0) [ 2] [ 3] [ 3] [ 2] [ 2] [ 2]
               [ 1] [ 2] [ 3] [ 4] [ 5] [ 0] ( 0) South
                 A    B    C    D    E    F

### Let the opponent play

The proscription against capturing all an opponent's seeds is related to a more general idea, that one ought to make a move that allows the opponent to continue playing. If an opponent's houses are all empty, the current player must make a move that gives the opponent seeds ("to feed him"):

    >>> awale.board = [0, 0, 0, 0, 0, 0, 5, 1, 1, 2, 2, 1]
    >>> awale.score = [0, 0]
    >>> awale
    {'board': [0, 0, 0, 0, 0, 0, 5, 1, 1, 2, 2, 1], 'score': [0, 0]}

    >>> awale.best_sown(1)
    10
    >>> awale.sow_and_capture(10)
    >>> print awale
                 f    e    d    c    b    a
    North ( 0) [ 2] [ 0] [ 2] [ 1] [ 1] [ 5]
               [ 1] [ 0] [ 0] [ 0] [ 0] [ 0] ( 0) South
                 A    B    C    D    E    F

The player that infringes this prescription, in gathering all seeds on its side, depriving thus its partner the possibility to play, is punished: its adversary gathers then to its profit all resting seeds.

If no such move is possible, the current player captures all seeds in his/her own territory, ending the game:

    >>> awale.board = [0, 0, 0, 0, 0, 0, 1, 3, 1, 0, 1, 0]
    >>> awale.score = [23, 23]
    >>> awale
    {'board': [0, 0, 0, 0, 0, 0, 1, 3, 1, 0, 1, 0], 'score': [23, 23]}

    >>> awale.best_sown(1)
    Traceback (most recent call last):
    ...
    NoMoreMove: No move available!
    >>> print awale
                 f    e    d    c    b    a
    North (23) [ 0] [ 1] [ 0] [ 1] [ 3] [ 1]
               [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] (23) South
                 A    B    C    D    E    F

### End of game

Since the game has only 48 seeds, capturing 25 is sufficient to accomplish this:

    >>> awale.board = [1, 1, 3, 3, 1, 1, 0, 5, 0, 3, 3, 0]
    >>> awale.score = [4, 23]
    >>> awale
    {'board': [1, 1, 3, 3, 1, 1, 0, 5, 0, 3, 3, 0], 'score': [4, 23]}

    >>> awale.best_sown(1)
    7
    >>> awale.sow_and_capture(7)
    Traceback (most recent call last):
    ...
    EndOfGame: North player wins!
    >>> print awale
                 f    e    d    c    b    a
    North (25) [ 1] [ 4] [ 4] [ 1] [ 0] [ 0]
               [ 0] [ 1] [ 3] [ 3] [ 1] [ 1] ( 4) South
                 A    B    C    D    E    F

Rk: Since there are an even number of seeds, it is possible for the game to end in a draw.

The end of game is also reached if less than 6 seeds left on board:

    >>> awale.board = [0, 1, 0, 0, 3, 0, 0, 1, 0, 1, 0, 0]
    >>> awale.score = [22, 18]
    >>> awale
    {'board': [0, 1, 0, 0, 3, 0, 0, 1, 0, 1, 0, 0], 'score': [22, 18]}

    >>> awale.sow_and_capture(4)
    Traceback (most recent call last):
    ...
    EndOfGame: No enough seeds!
    >>> print awale
                 f    e    d    c    b    a
    North (18) [ 0] [ 0] [ 1] [ 0] [ 0] [ 1]
               [ 0] [ 1] [ 0] [ 0] [ 0] [ 1] (24) South
                 A    B    C    D    E    F

# 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).

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.

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).

## 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.

## AlphaBeta

Currently the alphabeta pruning is implemented with the NegaMax algorithm.

-- MiKael NAVARRO