#! /usr/bin/python -O
# -*- coding: iso-8859-15 -*-
#
# A simple Awalé game.
# Copyright (C) 2007 MiKael NAVARRO
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#

"""A simple Awalé game.
Copyright (C) 2007 MiKael NAVARRO

The count-and-capture official board game of Africa.

"""

# Specific variables for pydoc
__author__ = "MiKael Navarro <klnavarro@gmail.com>"

# Include directives
import sys
import time

if __debug__:
    from pprint import pprint as pp
    import md5

# Global variables
BOARD_SIZE = 12  # default nb cups, "houses"
INITIAL_SEEDS = 4  # initial seeds by cups
ALL_SEEDS = BOARD_SIZE * INITIAL_SEEDS

SOUTH_PLAYER = 0  # player
NORTH_PLAYER = 1  # computer
SOUTH_CUPS = range(BOARD_SIZE / 2)
NORTH_CUPS = range(BOARD_SIZE / 2, BOARD_SIZE)
PLAYER_CUPS = (SOUTH_CUPS, NORTH_CUPS)

HUMAN_CUPS = ('A', 'B', 'C', 'D', 'E', 'F', 'G')  # south
COMPUTER_CUPS = ('a', 'b', 'c', 'd', 'e', 'f', 'g')  # north

ALGO_TYPES = ('bfs', 'minimax', 'maxi', 'negamax', 'alphabeta')
ALGO_DEPTH=3  # depth of the tree


#
# Awale Exceptions.
#
class AwaleError(Exception):
    """Base class for Awale exceptions."""

    pass

class InvalidSown(AwaleError):
    """Invalid input."""

    pass

class NoMoreMove(AwaleError):
    """No move available."""

    pass

class EndOfGame(AwaleError):
    """End of game?"""

    pass


#
# Awale board.
#
class Awale(object):
    """Awale board class.
	
    Usage:
    >>> awale = Awale()
    >>> awale
    {'board': [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], 'score': [0, 0]}
    >>> awale.sow_and_capture(3)
    >>> awale.sow_and_capture(6)
    >>> awale.sow_and_capture(2)
    >>> awale.sow_and_capture(6)
    >>> print awale
                 f    e    d    c    b    a
    North ( 0) [ 5] [ 5] [ 5] [ 5] [ 7] [ 0]
               [ 4] [ 4] [ 0] [ 1] [ 6] [ 6] ( 0) South
                 A    B    C    D    E    F
    >>> awale.sow_and_capture(1)
    >>> awale.best_sown(1)
    10
    >>> awale.sow_and_capture(10)
    >>> print awale
                 f    e    d    c    b    a
    North ( 5) [ 6] [ 0] [ 5] [ 5] [ 7] [ 0]
               [ 5] [ 1] [ 0] [ 0] [ 7] [ 7] ( 0) South
                 A    B    C    D    E    F
    """

    def __init__(self, board=[INITIAL_SEEDS]*BOARD_SIZE, score=[0, 0], algo=ALGO_TYPES[1], depth=ALGO_DEPTH):
        """Initialize the board game and player scores.

        By default BOARD_SIZE cups with INITIAL_SEEDS inside each houses;
        South (human) and north (computer) players begin with a score of 0.
        """
        
	# Awale board
	self.board = board
        self.score = score
        self.turn = 0  # store nb turns
        
	# Params/settings
	self.algo_type = algo
	self.algo_depth = depth

    def __repr__(self):
        """Friendly representation of Awale data: board + score."""

        #return str(self.__dict__)
        return "{'board': %s, 'score': %s}" % (str(self.board), str(self.score))
        
    def __str__(self):
        """Display Awale board."""

        s = ""
        
        # North player (computer)
        s += "             "
        s += "    ".join( [c for c in reversed(COMPUTER_CUPS[:BOARD_SIZE/2])] ) 
        s += "\n"
        
        s += "North (%2d) " % self.score[NORTH_PLAYER]
        s += " ".join( ["[%2d]" % i for i in reversed(self.board[-BOARD_SIZE/2:])] )
        s += "\n"

        # South player (player)
        s += "           "
        s += " ".join( ["[%2d]" % i for i in self.board[:BOARD_SIZE/2]] )
        s += " (%2d) South" % self.score[SOUTH_PLAYER]

        s += "\n"
        s += "             "
        s += "    ".join( [c for c in HUMAN_CUPS[:BOARD_SIZE/2]] ) 

        return s

    #
    # Internal functions.
    #

    def _who_play(self, idx):
        """Determine who play given index."""

        assert(idx in range(len(self.board)))

        player = None

        if idx in SOUTH_CUPS:
            player = SOUTH_PLAYER
        elif idx in NORTH_CUPS:
            player = NORTH_PLAYER

        return player

    def _valid(self, idx):
        """Check if sowing seeds from given index is authorized?"""

        assert(idx in range(len(self.board)))

        player = self._who_play(idx)  # who play?

        # Cup must not be empty!
        if self.board[idx] == 0:
            return False

        # You must feed the adversary?
        if max( [ self.board[i] for i in PLAYER_CUPS[1-player] ] ) == 0:
            status = False  # feed the adversary?
            
            nb_seeds = self.board[idx]
            i = 0
            while nb_seeds:
                if (idx+i+1)%len(self.board) == idx:
                    pass  # do not take into account the departure cup!
                else:
                    if (idx+i+1)%len(self.board) in PLAYER_CUPS[1-player]:
                        status = True
                        break  # okey, you feed him:)
                    nb_seeds -= 1
                i += 1

            if not status:  # ko, you must feed him!
                return False
        
        return True  # all Okey
            
    def _sow(self, idx):
        """Sow seeds from given index (counter-clockwise).

        Update board cups;
        And, return the last position."""

        assert(idx in range(len(self.board)))

        if not self._valid(idx):
            raise InvalidSown, "Invalid cup!"

        # First, get seeds from cup idx
        nb_seeds = self.board[idx]
        self.board[idx] = 0  # empty cup

        # Then, sow seeds (counter-clockwise)
        i = 0
        while nb_seeds:
            if (idx+i+1)%len(self.board) == idx:
                pass  # do not give seed to departure cup!
            else:
                self.board[(idx+i+1)%len(self.board)] += 1
                nb_seeds -= 1
            i += 1

        return (idx+i)%len(self.board)  # last cup position

    def _capture(self, idx):
        """Capture seeds from given index (clockwise).

        Update board cups and player score;
        And, return the number of seeds captured."""

        assert(idx in range(len(self.board)))

        camp = self._who_play(idx)  # determine camp

        board_sav = self.board[:]  # save current board

        nb_seeds = 0
        # Try capturing seeds (clockwise)
        for i in range((idx%(len(self.board)/2))+1):
            if 2 <= self.board[idx-i] <= 3:
                nb_seeds += self.board[idx-i]
                self.board[idx-i] = 0
            else:
                break  # stop here

        # "Grand Slam" rule: Oware Society (no capture)
        if sum( [ self.board[idx] for idx in PLAYER_CUPS[camp] ] ) == 0:  # not starve!
            self.board = board_sav[:]  # restore initial board
            nb_seeds = 0

        return nb_seeds

    def _end(self):
        """Check if end game is reached?"""
    
        # 25 seeds captured
        if self.score[SOUTH_PLAYER] > (len(self.board)*INITIAL_SEEDS)/2:
            raise EndOfGame, "South player wins!"
        elif self.score[NORTH_PLAYER] > (len(self.board)*INITIAL_SEEDS)/2:
            raise EndOfGame, "North player wins!"

        # No enough seeds
	if sum(self.board) < 6:
            raise EndOfGame, "No enough seeds!"

        return False  # continue

    #
    # BFS algorithm.
    # (http://en.wikipedia.org/wiki/Breadth-first_search)
    #
    def bfs(node, player, depth):
    	"""Simple BFS algorithm."""

        lvl = 0
        max_note = -(len(node.board)*INITIAL_SEEDS)
        best_idx = None
        nodes = [ ([], node), ]  # start at current node

        # depth=3 =>        216 
        # depth=6 =>     46 656 
        # depth=9 => 10 077 696
        # So, we limit the depth to 6 for the 'bfs' algo!
        if depth > 6: depth = 6

        while lvl < depth:
            childs = []  # reinit
            
            for idx_path, node in nodes:  # loop on all nodes
                
                if __debug__:  # GraphViz Node infos
                    node_id = md5.new(repr(node)).hexdigest()
                    north_board = node.board[-len(node.board)/2:]
                    north_board.reverse()
                    south_board = node.board[:len(node.board)/2]
                    node_label = "{ depth%d | %s | %s | %s }" % (lvl,
                                                                 repr(north_board),
                                                                 repr(south_board),
                                                                 repr(node.score))
                    print '"%s" [ label="%s", shape="record" ];' % (node_id, node_label)
                    
                # Visit all childs
                for i in range(len(node.board)/2):
                    idx = i + player * len(node.board)/2

                    if node._valid(idx):
                        # Initialize the child awale from the current
                        child = Awale(board=node.board[:], score=node.score[:],
                                      algo=node.algo_type, depth=node.algo_depth)
        
                        # Try a play ...
                        try:
                            child.sow_and_capture(idx)
                        except AwaleError, msg:
                            pass  # do not catch exception here!
        
                        if __debug__:  # GraphViz Node (child) infos
                            child_id = md5.new(repr(child)).hexdigest()
                            north_board = child.board[-len(child.board)/2:]
                            north_board.reverse()
                            south_board = child.board[:len(child.board)/2]
                            child_label = "{ depth%d | %s | %s | %s }" % (lvl + 1,
                                                                          repr(north_board),
                                                                          repr(south_board),
                                                                          repr(child.score))
                            print '"%s" [ label="%s", shape="record" ];' % (child_id, child_label)

                        if __debug__:  # GraphViz Edge relation
                            node_id = md5.new(repr(node)).hexdigest()
                            child_id = md5.new(repr(child)).hexdigest()
                            print '"%s" -> "%s" [ label="idx=%d" ];' % (node_id, child_id, idx)
                            
                        new_idx_path = idx_path[:]
                        new_idx_path.append(idx)
                        childs.append( (new_idx_path, child) )

            note = None
            for i, n in childs:  # determine max benefit
                note = n.score[1] - node.score[1]
                if note > max_note:
                    max_note = note
                    best_idx = i[0]
            if note:
                return (best_idx, max_note)
            # else: try next level
            lvl += 1
            nodes = childs[:]
            player = 1 - player
                
        return (best_idx, max_note)

    #
    # Minimax algorithm.
    # (http://en.wikipedia.org/wiki/Minimax)
    #
    # node = { 'board': [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4],
    #          'score': [0, 0] }
    #
    def minimax(node, player, depth):
    	"""Minimax algorithm.

    	Return the tuple (best_idx, note)."""

    	if __debug__:  # GraphViz Node infos
            node_id = md5.new(repr(node)).hexdigest()
            north_board = node.board[-len(node.board)/2:]
            north_board.reverse()
            south_board = node.board[:len(node.board)/2]
            node_label = "{ depth%d | %s | %s | %s }" % (node.algo_depth - depth,
                                                         repr(north_board),
                                                         repr(south_board),
                                                         repr(node.score))
            print '"%s" [ label="%s", shape="record" ];' % (node_id, node_label)

    	# Current node is a terminal node?
    	if (node.score[SOUTH_PLAYER] + node.score[NORTH_PLAYER] == ALL_SEEDS) or depth == 0 or \
               node.score[SOUTH_PLAYER] > ALL_SEEDS/2 or node.score[NORTH_PLAYER] > ALL_SEEDS/2:
            # Return the heuristic value of node (from the NORTH_PLAYER view)
            if node.score[NORTH_PLAYER] > ALL_SEEDS/2:
                note = 25  # I win!
            else:
                note = node.score[NORTH_PLAYER] - node.score[SOUTH_PLAYER]
            return (-1, note)

        note = None  # alpha
        if player == NORTH_PLAYER:
            note = -(len(node.board)*INITIAL_SEEDS)
        elif player == SOUTH_PLAYER:
            note = +(len(node.board)*INITIAL_SEEDS)
        best_idx = None

        # Visit all childs
        for i in range(len(node.board)/2):
            idx = i + player * len(node.board)/2

            if node._valid(idx):
                # Initialize the child awale from the current
                child = Awale(board=node.board[:], score=node.score[:],
                              algo=node.algo_type, depth=node.algo_depth)

                # Try a play ...
                try:
                    child.sow_and_capture(idx)
                except AwaleError, msg:
                    pass  # do not catch exception here!

                if __debug__:  # GraphViz Edge relation
                    node_id = md5.new(repr(node)).hexdigest()
                    child_id = md5.new(repr(child)).hexdigest()
                    print '"%s" -> "%s" [ label="idx=%d" ];' % (node_id, child_id, idx)
            
                curr_idx, curr_note = Awale.minimax(child, 1 - player, depth - 1)

                if player == NORTH_PLAYER:
                    if curr_note > note:
                        note = curr_note
                        best_idx = idx
                elif player == SOUTH_PLAYER:
                    if curr_note < note:
                        note = curr_note
                        best_idx = idx
            
        return (best_idx, note)
    
    #
    # Minimax algorithm.
    # (http://en.wikipedia.org/wiki/Minimax)
    #
    # With ponderations.
    #
    def maxi(node, player, depth):
    	"""Minimax algorithm with ponderation.

    	Return the tuple (best_idx, max_note)."""

    	if __debug__:  # GraphViz Node infos
            node_id = md5.new(repr(node)).hexdigest()
            north_board = node.board[-len(node.board)/2:]
            north_board.reverse()
            south_board = node.board[:len(node.board)/2]
            node_label = "{ depth%d | %s | %s | %s }" % (node.algo_depth - depth,
                                                         repr(north_board),
                                                         repr(south_board),
                                                         repr(node.score))
            print '"%s" [ label="%s", shape="record" ];' % (node_id, node_label)

    	# Current node is a terminal node?
    	if (node.score[SOUTH_PLAYER] + node.score[NORTH_PLAYER] == ALL_SEEDS) or depth == 0 or \
               node.score[SOUTH_PLAYER] > ALL_SEEDS/2 or node.score[NORTH_PLAYER] > ALL_SEEDS/2:
            # Return score status (from the NORTH_PLAYER view)
            if node.score[NORTH_PLAYER] > ALL_SEEDS/2:
                note = 25  # I win!
            else:
                note = node.score[NORTH_PLAYER] - node.score[SOUTH_PLAYER]
            return (-1, note)

        max_note = -(len(node.board)*INITIAL_SEEDS)
        best_idx = None

        # Visit all childs
        for i in range(len(node.board)/2):
            idx = i + player * len(node.board)/2

            if node._valid(idx):
                # Initialize the child awale from the current
                child = Awale(board=node.board[:], score=node.score[:],
                              algo=node.algo_type, depth=node.algo_depth)

                # Try a play ...
                try:
                    child.sow_and_capture(idx)
                except AwaleError, msg:
                    pass  # do not catch exception here!

                if __debug__:  # GraphViz Edge relation
                    node_id = md5.new(repr(node)).hexdigest()
                    child_id = md5.new(repr(child)).hexdigest()
                    print '"%s" -> "%s" [ label="idx=%d" ];' % (node_id, child_id, idx)
            
                curr_idx, note = Awale.maxi(child, 1 - player, depth - 1)

                if note > max_note:
                    max_note = note
                    best_idx = idx
            
        return (best_idx, max_note)

    #
    # Negamax algorithm.
    # (http://en.wikipedia.org/wiki/Negamax)
    #
    def negamax(node, player, depth, alpha=-ALL_SEEDS, beta=ALL_SEEDS):
    	"""Variant formulation of minimax search: Negamax algorithm."""
    
    	if __debug__:  # GraphViz Node infos
            node_id = md5.new(repr(node)).hexdigest()
            north_board = node.board[-len(node.board)/2:]
            north_board.reverse()
            south_board = node.board[:len(node.board)/2]
            node_label = "{ depth%d | %s | %s | %s }" % (node.algo_depth - depth,
                                                         repr(north_board),
                                                         repr(south_board),
                                                         repr(node.score))
            print '"%s" [ label="%s", shape="record" ];' % (node_id, node_label)

    	# Current node is a terminal node?
    	if (node.score[SOUTH_PLAYER] + node.score[NORTH_PLAYER] == ALL_SEEDS) or depth == 0 or \
               node.score[SOUTH_PLAYER] > ALL_SEEDS/2 or node.score[NORTH_PLAYER] > ALL_SEEDS/2:
            # Return the heuristic value of node (from the NORTH_PLAYER view)
            if node.score[NORTH_PLAYER] > ALL_SEEDS/2:
                note = 25  # I win!
            else:
                note = node.score[NORTH_PLAYER] - node.score[SOUTH_PLAYER]
            return (-1, note)

        #note = alpha
        best_idx = None

        # Visit all childs
        for i in range(len(node.board)/2):
            idx = i + player * len(node.board)/2

            if node._valid(idx):
                # Initialize the child awale from the current
                child = Awale(board=node.board[:], score=node.score[:],
                              algo=node.algo_type, depth=node.algo_depth)

                # Try a play ...
                try:
                    child.sow_and_capture(idx)
                except AwaleError, msg:
                    pass  # do not catch exception here!

                if __debug__:  # GraphViz Edge relation
                    node_id = md5.new(repr(node)).hexdigest()
                    child_id = md5.new(repr(child)).hexdigest()
                    print '"%s" -> "%s" [ label="idx=%d" ];' % (node_id, child_id, idx)
            
                curr_idx, curr_note = Awale.negamax(child, 1 - player, depth - 1, -beta, -alpha)

                if -curr_note > alpha:
                    alpha = -curr_note
                    best_idx = idx
                
                # Alpha-beta pruning
                if alpha >= beta:
                    return (best_idx, beta)
                    
        return (best_idx, alpha)
    
    #
    # Alpha-beta pruning.
    # (http://en.wikipedia.org/wiki/Alpha-beta_pruning)
    #
    def alphabeta(node, player, depth):
    	"""Alpha-beta pruning."""

 	node.algo_type = ALGO_TYPES[3]  # implemented with negamax
        return Awale.negamax(node, player, depth)
        
    #
    # Play!
    #

    def sow_and_capture(self, idx):
        """Sow seeds from given index (counter-clockwise);
        and, capture seeds (clockwise) if possible.

        Update scores and return game status."""

        assert(idx in range(len(self.board)))

        player = self._who_play(idx)  # determine who is playing

        # Sowing ...
        capt_idx = self._sow(idx)

        # Capturing ...
        if capt_idx in PLAYER_CUPS[1-player]:  # if adversary cups
            self.score[player] += self._capture(capt_idx)

        self.turn += 1  # incr counter (if sow is valid, cf self._sow)
        
        # End of game?
        self._end()  # raise AwaleErrors

    def best_sown(self, player):
        """Compute the best move for given player."""

        if __debug__:  # output a GraphViz graph
            print "\r",
            print 'digraph "best sown" {'
            print 'label="Best Sown (algo=\'%s\', depth=%d)";' % (self.algo_type, self.algo_depth)
            print 'node [ style="rounded" ];'

        # Call AI/algo
        idx, gain = eval("Awale.%s(self, player, self.algo_depth)" % self.algo_type)

        if __debug__:
            print '}'  # end GraphViz data

        if idx == None:
            raise NoMoreMove, "No move available!"

        return idx


#
# Main test function.
#
def _test():
    import doctest
    doctest.testmod(sys.modules[__name__])


#
# External entry point.
#
if __name__ == "__main__":
    _test()