#!/usr/bin/python
# -*- coding: utf-8 -*-

# Copyright (C) 2018 Rod Engerstad

"""
The Model class is adapted with only trivial changes from
code written by Daniel Connelly. (http://dhconnelly.com).
He in turn states: This implementation follows chapter 18 of Peter Norvig's
"Paradigms of Artificial Intelligence".

Daniel's copyright:

Copyright (c) 2015, Daniel Connelly
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
"""

import Tkinter as tk
import tkColorChooser
import time
import random

from pzl_lib import PzlG
from pzl_lib import SettingsB
from pzl_lib import Preferences
from pzl_lib import MenuItem
from pzl_lib import Flasher
from pzl_lib import OpenFileI
from pzl_lib import ViewB
from pzl_lib import Menu
from pzl_lib import Toolbar
from pzl_lib import ClockBox
from pzl_lib import ScoreBox

class Sgg(object):
    """
    Game globals
    """
    grid_width = 8
    grid_size = grid_width * grid_width
    WHITE = 'o'
    BLACK = '@'
    VACANT = '.'


class Settings(SettingsB):

    def __init__(self):
        SettingsB.__init__(self)
        self.dic = {}
        self.dic['font_size'] = '4'
        self.dic['move_pause'] = '2'
        self.dic['game_type'] = 'human_v_machine'
        self.dic['black_look_ahead'] = '4'
        self.dic['white_look_ahead'] = '4'
        self.dic['humans_colour'] = Sgg.BLACK
        self.dic['game_time'] = '30'
        self.dic['board_colour'] = '#0B8804'
        self.dic['grid_colour'] = 'black'
        self.dic['highlight_colour'] = 'yellow'
        self.dic['set_colour'] = 'board_colour'
        self.dic['black_algorithm'] = 'random'
        self.dic['white_algorithm'] = 'random'
        self.original_square_size = 30
        self.square_size = self.original_square_size
        self.clock_box_width = 6
        self.score_box_width = 6
        self.tick_interval = 1
        self.menu_items = []
        self.preferences = Preferences(self.dic)
        self.preferences.load()
        self.max_time = int(self.dic['game_time']) * 60
        self.load_menus()
        self.count = len(self.menu_items)
        self.set_fonts()
        self.make_help()
        self.make_tooltip()
        self.make_alg_help()

    def make_alg_help(self):
        self.alg_text = []

    def make_help(self):
        self.help_text = _("The aim is to finish with more tiles of your colour on the board than those of your opponent. Game Type: you can play against the computer 'Human v Machine' or watch the computer play with itself ('Machine v Machine'). Human's Colour: choose your colour. This determines whether you play first, which algorithm will be used for hints and how far ahead the algorithm will look. Move Pause: to give players time to see the square the machine is going to use the program highlights the square for Move Pause seconds before playing and flipping the tiles. Black Look Ahead: for some algorithms the program checks all the possible moves for several turns to come. If Black is using one of these algorithms, this is the number of turns ahead it is examining. White Look Ahead: see Black Look Ahead. Black Algorithm: which of the 7 algorithms will be used by Black. White Algorithm: which of the 7 algorithms will be used by White. Save Board: at any time you can save the current state of the board to a file. Load Board: you can load a saved board and continue playing a game or have the machine play both colours (depending on Game Type). Save Transcript: you can save to a file a record of all the moves played during a game. Load Transcript: you can load a file containing a record of all the moves played during a game and the program will replay each move as you click the wand. Font Size: the size of the board can be set. Set Colour: the colours of the board, grid and highlight can be chosen. Save Settings: save the current configuration to a file that will be loaded next time you start the game. When playing Human versus Machine it is your turn if the clock is ticking. Legal moves will be highlighted when the cursor enters the corresponding squares. Left click to place a tile. Click the wand for a hint; click again to make that move. When playing Machine versus Machine or replaying a transcript execute each move by clicking on the wand.")

    def make_tooltip(self):
        self.tooltip_text = [
            _('Start game'),
            _('Give hint, Apply hint, Step machine'),
            ]

    def load_menus(self):
        self.menu_items.append(MenuItem(
            _('Game Type'),
            [_('Human v Machine'),
             _('Machine v Machine')],
            '',
            ['human_v_machine',
             'machine_v_machine'],
            'game_type'
            ))
        self.menu_items.append(MenuItem(
            _('Humans Colour'),
            [_('Black'),
             _('White')],
            '',
            [Sgg.BLACK,
             Sgg.WHITE],
            'humans_colour'
            ))
        self.menu_items.append(MenuItem(
            _('Black algorithm'),
            [_('random'),
             _('max-diff'),
             _('max-weighted-diff'),
             _('minimax-diff'),
             _('minimax-weighted-diff'),
             _('ab-diff'),
             _('ab-weighted-diff')],
            '',
            ['random',
             'max-diff',
             'max-weighted-diff',
             'minimax-diff',
             'minimax-weighted-diff',
             'ab-diff',
             'ab-weighted-diff'],
            'black_algorithm'
            ))
        self.menu_items.append(MenuItem(
            _('White algorithm'),
            [_('random'),
             _('max-diff'),
             _('max-weighted-diff'),
             _('minimax-diff'),
             _('minimax-weighted-diff'),
             _('ab-diff'),
             _('ab-weighted-diff')],
            '',
            ['random',
             'max-diff',
             'max-weighted-diff',
             'minimax-diff',
             'minimax-weighted-diff',
             'ab-diff',
             'ab-weighted-diff'],
            'white_algorithm'
            ))
        self.menu_items.append(MenuItem(
            _('Black Look Ahead'),
            ['1',
             '2',
             '3',
             '4',
             '5',
             '6',
             '7',
             '8',
             '9'],
            '',
            ['1',
             '2',
             '3',
             '4',
             '5',
             '6',
             '7',
             '8',
             '9'],
            'black_look_ahead'
            ))
        self.menu_items.append(MenuItem(
            _('White Look Ahead'),
            ['1',
             '2',
             '3',
             '4',
             '5',
             '6',
             '7',
             '8',
             '9'],
            '',
            ['1',
             '2',
             '3',
             '4',
             '5',
             '6',
             '7',
             '8',
             '9'],
            'white_look_ahead'
            ))
        self.menu_items.append(MenuItem(
            _('Move Pause'),
            ['0',
             '1',
             '2',
             '3',
             '4',
             '5'],
            '',
            ['0',
             '1',
             '2',
             '3',
             '4',
             '5'],
            'move_pause'
            ))
        self.menu_items.append(MenuItem(
            _('Save Board'),
            '',
            '',
            '',
            'save_board'
        ))
        self.menu_items.append(MenuItem(
            _('Load Board'),
            '',
            '',
            '',
            'load_board'
        ))
        self.menu_items.append(MenuItem(
            _('Save Transcript'),
            '',
            '',
            '',
            'save_transcript'
        ))
        self.menu_items.append(MenuItem(
            _('Load Transcript'),
            '',
            '',
            '',
            'load_transcript'
        ))
        self.menu_items.append(MenuItem(
            _('Font Size'),
            ['2',
             '4',
             '6',
             '8',
             '10',
             '12'],
            '',
            ['2',
             '4',
             '6',
             '8',
             '10',
             '12'],
            'font_size'
            ))
        self.menu_items.append(MenuItem(
            _('Set Colour'),
            [_('Board'),
             _('Grid'),
             _('Highlight')],
            'N',
            ['board_colour',
             'grid_colour',
             'highlight_colour'],
            'set_colour'
        ))
        self.menu_items.append(MenuItem(
            _('Save Settings'),
            '',
            '',
            '',
            'save_settings'
        ))
        self.menu_items.append(MenuItem(
            _('Help'),
            '',
            '',
            '',
            'help'
        ))
        self.menu_items.append(MenuItem(
            _('About'),
            '',
            '',
            '',
            'about'
        ))

    def do_scaling(self):
        inc = 0.1
        mult = int(self.dic['font_size'])
        factor = 0.8 + mult * inc
        self.square_size = 50
        self.square_size = int(self.square_size * factor)


class OSquare(object):
    def __init__(self, canvas, settings, square_id, x0, y0, x1, y1):
        self.settings = settings
        self.canvas = canvas
        self.square_id = square_id
        self.active = False
        self.callback = None
        outline = self.settings.dic['grid_colour']
        fill = self.settings.dic['board_colour']
        active = self.settings.dic['grid_colour']
        self.w_id = self.canvas.create_rectangle(x0, y0, x1, y1,
                                                 outline=outline,
                                                 fill=fill,
                                                 width=1,
                                                 activeoutline=active)

    def add_bindings(self):
        self.canvas.tag_bind(self.w_id, "<ButtonRelease-1>", self.command)
        self.canvas.tag_bind(self.w_id, "<ButtonRelease-3>", self.command)
        self.canvas.tag_bind(self.w_id, "<Enter>", self.command)
        self.canvas.tag_bind(self.w_id, "<Leave>", self.command)

    def command(self, event):
        self.callback(event, self.square_id)


class Board(tk.Frame):
    def __init__(self, parent, settings):
        self.settings = settings
        self.model = None
        self.square_size = self.settings.square_size
        self.widgets = [None for x in range(Sgg.grid_size)]

        self.grid_margin = 0
        self.delta = 2
        self.line_width = 1
        self.circle_width = 0
        bg = self.settings.green
        tk.Frame.__init__(self, parent, relief='flat',
                          highlightbackground=self.settings.grey,
                          highlightthickness=0,
                          bd=2, bg=bg)
        self.board_size = Sgg.grid_width * (self.square_size + 1)
        self.canvas_size = 2 * self.grid_margin + self.board_size
        self.canvas_size = self.board_size
        self.tk_focusFollowsMouse()
        bg = self.settings.dic['board_colour']
        self.canvas = tk.Canvas(self, width=self.canvas_size,
                                height=self.canvas_size)

        self.board = self.canvas.create_rectangle(0, 0, self.board_size,
                                                  self.board_size,
                                                  fill=bg)
        self.draw_grid()
        self.canvas.grid()
        self.grid()

    def update_board(self, square_id, job):
        widget = self.widgets[square_id]
        colour = self.settings.dic['grid_colour']
        if job == 0:
            colour = self.settings.dic['highlight_colour']
        widget.canvas.itemconfig(widget.w_id, activeoutline=colour)

    def my_destroy(self):
        self.canvas.destroy()
        self.destroy()

    def add_callbacks(self, func):
        for widget in self.widgets:
            widget.callback = func
            widget.add_bindings()

    def draw_grid(self):
        outline_width = 1
        unit = self.settings.square_size
        unit2 = unit / 2
        square_id = 0
        for y in range(1, Sgg.grid_width + 1):
            fudge = y * outline_width
            yc = y * unit + fudge - unit2
            y0 = yc - unit2
            y1 = yc + unit2
            for x in range(1, Sgg.grid_width + 1):
                fudge = x * outline_width
                xc = x * unit + fudge - unit2
                x0 = xc - unit2
                x1 = xc + unit2
                square = OSquare(self.canvas, self.settings,
                                 square_id, x0, y0, x1, y1)
                self.widgets[square_id] = square
                square_id += 1

    def draw_tile(self, x_centre, y_centre, datum):
        # ie a circle centred at x_centre, y_centre in booard coords
        colour = 'red'
        if datum == Sgg.BLACK:
            colour = 'black'
        elif datum == Sgg.WHITE:
            colour = 'white'
        radius = self.square_size / 2
        x0 = x_centre - radius + self.delta
        x1 = x_centre + radius - self.delta
        y0 = y_centre - radius + self.delta
        y1 = y_centre + radius - self.delta
        circle = self.canvas.create_oval(x0, y0, x1, y1,
                                         width=self.circle_width,
                                         fill=colour)

    def draw_tiles(self):
        outline_width = 1
        square_id = 0
        for y in range(Sgg.grid_width):
            for x in range(Sgg.grid_width):
                datum = self.model.datum[square_id]
                if datum != Sgg.VACANT:
                    x0 = x * self.square_size
                    y0 = y * self.square_size
                    x_fudge = outline_width * int(x0 / self.square_size)
                    y_fudge = outline_width * int(y0 / self.square_size)
                    x_centre = x0 + self.square_size / 2
                    y_centre = y0 + self.square_size / 2
                    x_centre += x_fudge + 1
                    y_centre += y_fudge + 1
                    self.draw_tile(x_centre, y_centre, datum)
                square_id += 1

    def highlight_square(self, square_id):
        widget = self.widgets[square_id]
        colour = self.settings.dic['highlight_colour']
        widget.canvas.itemconfig(widget.w_id, outline=colour)

    def unhighlight_square(self, square_id):
        widget = self.widgets[square_id]
        colour = self.settings.dic['grid_colour']
        widget.canvas.itemconfig(widget.w_id, outline=colour)


class View(ViewB):
    """
    Stick blobs on the screen and respond to callbacks
    """

    def __init__(self, master, settings):
        ViewB.__init__(self, master, settings)
        self.model = None
        self.board = None
        self.show_connections = False
        self.image_dic = {}
        self.make_image_dic()
        self.do_layout(self)

    def make_board(self):
        """
        draw the squares
        """
        if self.board is not None:
            self.board.my_destroy()
        self.board = Board(self.top_frame, self.settings)

    def draw_board(self):
        self.board.draw_tiles()
        self.board.update_idletasks()

    def update_clock_box(self, algorithm):
        value = '  '
        if algorithm is not None:
            self.clock.box.set_text(value)

    def make_image_dic(self):
        """
        image, button_index, start
        """
        dic = {}
        dic['start'] = [self.images.start_othello, 0, True]
        dic['hint'] = [self.images.hint, 1, True]
        dic['hint_on'] = [self.images.hint_on, 1, False]
        dic['length'] = [None, 2, False]
        self.image_dic = dic

    def do_layout(self, root):
        bg = self.settings.grey
        self.outer_frame = tk.Frame(root, bg=bg)
        self.outer_frame.grid()
        bg = self.settings.green
        self.control_frame = tk.Frame(self.outer_frame,
                                      bd=2, bg=bg, relief='raised')
        self.control_frame.grid(row=0, column=0, sticky='EW')
        self.menu_bar = tk.Frame(self.control_frame, relief='raised',
                                 bd=1, bg=bg)
        self.menu_bar.grid(row=0, column=0, sticky='W')
        self.menu = Menu(self.settings, self.menu_bar, self.images.file)
        self.toolbar = Toolbar(self.settings, self.image_dic,
                               self.control_frame)
        self.toolbar.grid(row=0, column=1, sticky='W')
        self.number_frame = tk.Frame(self.control_frame, relief='raised',
                                     bg=bg)
        self.number_frame.grid(row=0, column=2, sticky='NS')
        self.clock_box = ClockBox(self, self.number_frame)
        self.clock_box.grid(row=0, column=0, sticky='NSEW')
        self.score_box = ScoreBox(self.settings, self.number_frame)
        self.score_box.grid(row=0, column=1, sticky='NSEW')
        self.top_frame = tk.Frame(self.outer_frame, relief='flat',
                                  bd=1, bg=bg)
        self.top_frame.grid(row=1, column=0, sticky='NW')
        self.board = None

    def hint_available(self):
        self.toolbar.key_on('hint')

    def sg_open_file(self, write, title):
        """
        Use gui to open and file for reading or writing
        """
        init_dir = PzlG.app_saves
        filetypes = [('All files', '*')]
        this_file = OpenFileI(self, init_dir, filetypes, write, title)
        return this_file.my_file


class Model(object):
    def __init__(self):
        self.EMPTY = '.'
        self.BLACK = '@'
        self.WHITE = 'o'
        self.OUTER = '?'
        self.PIECES = (self.EMPTY, self.BLACK, self.WHITE, self.OUTER)
        self.PLAYERS = {self.BLACK: 'Black', self.WHITE: 'White'}
        # To refer to neighbor squares we can add a direction to a square.
        self.UP = -10
        self.DOWN = 10
        self.LEFT = -1
        self.RIGHT = 1
        self.UP_RIGHT = -9
        self.DOWN_RIGHT = 11
        self.DOWN_LEFT = 9
        self.UP_LEFT = -11
        self.DIRECTIONS = (self.UP, self.UP_RIGHT, self.RIGHT,
                           self.DOWN_RIGHT, self.DOWN, self.DOWN_LEFT,
                           self.LEFT, self.UP_LEFT)
        self.SQUARE_WEIGHTS = [
            0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
            0, 120, -20,  20,   5,   5,  20, -20, 120,   0,
            0, -20, -40,  -5,  -5,  -5,  -5, -40, -20,   0,
            0,  20,  -5,  15,   3,   3,  15,  -5,  20,   0,
            0,   5,  -5,   3,   3,   3,   3,  -5,   5,   0,
            0,   5,  -5,   3,   3,   3,   3,  -5,   5,   0,
            0,  20,  -5,  15,   3,   3,  15,  -5,  20,   0,
            0, -20, -40,  -5,  -5,  -5,  -5, -40, -20,   0,
            0, 120, -20,  20,   5,   5,  20, -20, 120,   0,
            0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
        ]
        # Values for endgame boards are big constants.
        self.MAX_VALUE = sum(map(abs, self.SQUARE_WEIGHTS))
        self.MIN_VALUE = -self.MAX_VALUE
        self.squares = [i for i in range(11, 89) if 1 <= (i % 10) <= 8]
        self.lookup = [i for i in range(11, 89) if 1 <= (i % 10) <= 8]
        # Sort squares so that where applicable we try the best squares first
        # paip 18.9 pages 630-631
        self.squares.sort(key=lambda x: self.SQUARE_WEIGHTS[x], reverse=True)
        self.datum = [Sgg.VACANT for x in range(Sgg.grid_size)]
        self.transcript = [0 for x in range(Sgg.grid_size)]
        self.move_index = 0

    def initial_board(self):
        """
        Create a new board with the initial black and white positions filled.
        """
        board = [self.OUTER] * 100
        for square in self.squares:
            board[square] = self.EMPTY
        # The middle four squares should hold the initial piece positions.
        board[44] = self.WHITE
        board[45] = self.BLACK
        board[54] = self.BLACK
        board[55] = self.WHITE
        self.datum[27] = Sgg.WHITE
        self.datum[36] = Sgg.WHITE
        self.datum[28] = Sgg.BLACK
        self.datum[35] = Sgg.BLACK
        return board

    def print_board(self, board):
        """
        Get a string representation of the board.
        """
        rep = ''
        rep += '  %s\n' % ' '.join(map(str, list(range(1, 9))))
        for row in range(1, 9):
            begin, end = 10*row + 1, 10*row + 9
            rep += '%d %s\n' % (row, ' '.join(board[begin:end]))
        return rep

    def get_board(self, board):
        """
        Get a string representation of the board.
        """
        rep = ''
        for row in range(1, 9):
            begin, end = 10*row + 1, 10*row + 9
            rep += ''.join(board[begin:end])
        return rep

    def is_valid(self, move):
        """
        Is move a square on the board?
        """
        return isinstance(move, int) and move in self.squares

    def opponent(self, player):
        """
        Get player's opponent piece.
        """
        return self.BLACK if player is self.WHITE else self.WHITE

    def find_bracket(self, square, player, board, direction):
        """
        Find a square that forms a bracket with `square` for `player`
        in the given `direction`.  Returns None if no such square exists.
        """
        bracket = square + direction
        if board[bracket] == player:
            return None
        opp = self.opponent(player)
        while board[bracket] == opp:
            bracket += direction
        return None if board[bracket] in (self.OUTER, self.EMPTY) else bracket

    def is_legal(self, move, player, board):
        """
        Is this a legal move for the player?
        """
        hasbracket = lambda direction: self.find_bracket(move, player,
                                                         board, direction)
        return board[move] == self.EMPTY and any(map(hasbracket,
                                                     self.DIRECTIONS))

    def make_move(self, move, player, board):
        """
        Update the board to reflect the move by the specified player.
        """
        board[move] = player
        for direction in self.DIRECTIONS:
            self.make_flips(move, player, board, direction)
        return board

    def update_transcript(self, move):
        self.move_index += 1
        self.transcript[self.lookup.index(move)] = self.move_index

    def make_flips(self, move, player, board, direction):
        """
        Flip pieces in the given direction as a result of the move
        by player.
        """
        bracket = self.find_bracket(move, player, board, direction)
        if not bracket:
            return
        square = move + direction
        while square != bracket:
            board[square] = player
            square += direction

    def legal_moves(self, player, board):
        """
        Get a list of all legal moves for player.
        """
        return [sq for sq in self.squares if self.is_legal(sq, player, board)]

    def any_legal_move(self, player, board):
        """
        Can player make any moves?
        """
        return any(self.is_legal(sq, player, board) for sq in self.squares)

    def play(self, black_strategy, white_strategy):
        """
        Play a game of Othello and return the final board and score.
        """
        board = self.initial_board()
        player = self.BLACK
        strategy = lambda who: black_strategy if who == self.BLACK\
                   else white_strategy
        while player is not None:
            move = self.get_move(strategy(player), player, board)
            self.make_move(move, player, board)
            player = self.next_player(board, player)
        return board, self.score(self.BLACK, board)

    def next_player(self, board, prev_player):
        """
        Which player should move next?  Returns None if no legal moves exist.
        """
        opp = self.opponent(prev_player)
        if self.any_legal_move(opp, board):
            return opp
        elif self.any_legal_move(prev_player, board):
            return prev_player
        return None

    def get_move(self, strategy, player, board):
        """
        Call strategy(player, board) to get a move.
        """
        copy = list(board)
        move = strategy(player, copy)
        return move

    def score(self, player, board):
        """
        Compute player's score (number of player's pieces minus opponent's).
        """
        mine, theirs = 0, 0
        opp = self.opponent(player)
        for sq in self.squares:
            piece = board[sq]
            if piece == player:
                mine += 1
            elif piece == opp:
                theirs += 1
        return mine - theirs

    def random_strategy(self, player, board):
        """
        A strategy that always chooses a random legal move.
        """
        ret = None
        choices = self.legal_moves(player, board)
        if choices:
            ret = random.choice(choices)
        return ret

    def maximizer(self, evaluate):
        """
        Construct a strategy that chooses the best move by maximizing
        evaluate(player, board) over all boards resulting from legal moves.
        """
        def strategy(player, board):
            def score_move(move):
                return evaluate(player, self.make_move(move, player,
                                                       list(board)))
            moves = self.legal_moves(player, board)
            if moves:
                return max(moves, key=score_move)
        return strategy

    def weighted_score(self, player, board):
        """
        Compute the difference between the sum of the weights of player's
        squares and the sum of the weights of opponent's squares.
        """
        opp = self.opponent(player)
        total = 0
        for sq in self.squares:
            if board[sq] == player:
                total += self.SQUARE_WEIGHTS[sq]
            elif board[sq] == opp:
                total -= self.SQUARE_WEIGHTS[sq]
        return total

    def minimax(self, player, board, depth, evaluate):
        """
        Find the best legal move for player, searching to the specified depth.
        Returns a tuple (move, min_score), where min_score is the guaranteed
        minimum score achievable for player if the move is made.
        """

        # We define the value of a board to be the opposite of its value to our
        # opponent, computed by recursively applying `minimax` for our opponent.
        def value(board):
            return -self.minimax(self.opponent(player), board,
                                 depth-1, evaluate)[0]

        # When depth is zero, don't examine possible moves--just determine
        # the value of this board to the player.
        if depth == 0:
            return evaluate(player, board), None

        # We want to evaluate all the legal moves by considering their
        # implications `depth` turns in advance.  First, find all the
        # legal moves.
        moves = self.legal_moves(player, board)

        # If player has no legal moves, then either:
        if not moves:
            # the game is over, so the best achievable score is victory
            # or defeat;
            if not self.any_legal_move(self.opponent(player), board):
                return self.final_value(player, board), None
            # or we have to pass this turn, so just find the value of
            # this board.
            return value(board), None

        # When there are multiple legal moves available, choose the best
        # one by maximizing the value of the resulting boards.
        return max((value(self.make_move(m, player, list(board))), m)
                   for m in moves)

    def final_value(self, player, board):
        """
        The game is over--find the value of this board to player.
        """
        diff = self.score(player, board)
        if diff < 0:
            return self.MIN_VALUE
        elif diff > 0:
            return self.MAX_VALUE
        return diff

    def minimax_searcher(self, depth, evaluate):
        """
        Construct a strategy that uses `minimax` with the specified leaf board
        evaluation function.
        """
        def strategy(player, board):
            return self.minimax(player, board, depth, evaluate)[1]
        return strategy

    def alphabeta(self, player, board, alpha, beta, depth, evaluate):
        """
        Find the best legal move for player, searching to the specified depth.
        Like minimax, but uses the bounds alpha and beta to prune branches.
        """
        if depth == 0:
            return evaluate(player, board), None

        def value(board, alpha, beta):
            """
            Like in `minimax`, the value of a board is the opposite of
            its value to the opponent.  We pass in `-beta` and `-alpha`
            as the alpha and beta values, respectively, for the opponent,
            since `alpha` represents the best score we know we can
            achieve and is therefore the worst score achievable by the
            opponent.  Similarly, `beta` is the worst score that
            our opponent can hold us to, so it is the best score that they can
            achieve.
            """
            return -self.alphabeta(self.opponent(player), board, -beta,
                                   -alpha, depth-1, evaluate)[0]

        moves = self.legal_moves(player, board)
        if not moves:
            if not self.any_legal_move(self.opponent(player), board):
                return self.final_value(player, board), None
            return value(board, alpha, beta), None

        best_move = moves[0]
        for move in moves:
            if alpha >= beta:
                # If one of the legal moves leads to a better score than
                # beta, then the opponent will avoid this branch, so we
                # can quit looking.
                break
            val = value(self.make_move(move, player, list(board)),
                        alpha, beta)
            if val > alpha:
                # If one of the moves leads to a better score than the
                # current best achievable score, then replace it with this one.
                alpha = val
                best_move = move
        return alpha, best_move

    def alphabeta_searcher(self, depth, evaluate):
        def strategy(player, board):
            return self.alphabeta(player, board, self.MIN_VALUE,
                                  self.MAX_VALUE, depth, evaluate)[1]
        return strategy

    def load_board(self, my_file):

        def in_legal(char):
            legal = ['@', 'o', '.']
            ret = False
            if char in legal:
                ret = True
            return ret
        board = []
        player = '.'
        tmp_board = []
        if my_file:
            lines = my_file.read()
            for line in lines:
                for item in line:
                    if in_legal(item):
                        tmp_board.append(item)
            if len(tmp_board) == 65:
                board = [self.OUTER] * 100
                item = 0
                jtem = 11
                for row in range(1, 9):
                    jtem = 10 * row + 1
                    for column in range(8):
                        board[jtem] = tmp_board[item]
                        jtem += 1
                        item += 1
                player = tmp_board[64]
        return board, player

    def load_transcript_file(self, my_file):
        """
        Handle 3 formats:
        1. move number on board
        2. board positions concatenated in single string
        3. board positions, 1 per record
        """
        chars = "ABCDEFGH"
        transcript = []
        if my_file:
            lines = my_file.read()
            if any(x.isupper() for x in lines or
                   any(x.islower() for x in lines)):
                text = ''.join([x for x in lines if x.isalnum()])
                for move_index in range(0, len(text), 2):
                    x = text[move_index]
                    y = text[move_index + 1]
                    try:
                        row = int(y)
                        column = chars.index(x.upper()) + 1
                        item = row * 10 + column
                        transcript.append(item)
                    except ValueError:
                        return transcript
            else:
                lines = lines.splitlines()
                lines_tmp = []
                for line in lines:
                    lin = line[1:].split()
                    for item in lin:
                        try:
                            jtem = int(item)
                            lines_tmp.append(jtem)
                        except ValueError:
                            return transcript
                pos_tmp = []
                for row in range(1, 9):
                    begin, end = 10*row + 1, 10*row + 9
                    for column in range(begin, end):
                        pos_tmp.append(column)
                tmp = list(zip(lines_tmp, pos_tmp))
                tmp = sorted(tmp, key=lambda tmp: tmp[0])
                for start in range(len(tmp)):
                    if tmp[start][0] != 0:
                        break
                for item in tmp[start:]:
                    transcript.append(item[1])
        return transcript


class Controller(object):
    """
    Set up and control
    """

    def __init__(self, root):
        self.strategies_dic = {}
        self.VIRTUAL_EVENT = "<<VirtualEvent>>"
        self.settings = Settings()
        self.master = root
        self.flasher = None
        self.model = None
        self.active = False
        self.hint_requested = False
        self.this_hint = None
        self.board_clicked = False
        self.finished = False
        self.scores = ''
        self.player = Sgg.BLACK
        self.humans_colour = self.settings.dic['humans_colour']
        self.white_depth = None
        self.white_strategy = None
        self.black_strategy = None
        self.black_depth = None
        self.legal_human_moves = None
        self.legal_human_board_moves = None
        self.this_move = None
        self.move_requested = False
        self.transcript_index = None
        self.loaded_transcript = []
        self.view = View(root, self.settings)
        self.board = None
        self.start_game()

    def is_human(self):
        human = False
        if self.settings.dic['game_type'] == 'human_v_machine':
            if self.player == self.model.BLACK:
                if self.humans_colour == self.model.BLACK:
                    human = True
            else:
                if self.humans_colour == self.model.WHITE:
                    human = True
        return human

    def is_finished(self):
        # finished if neither player can move
        finished = True
        if self.model.legal_moves(self.model.BLACK, self.board) or\
           self.model.legal_moves(self.model.WHITE, self.board):
            finished = False
        self.finished = finished
        return finished

    def start_game(self):
        self.view.clock_init()
        self.flasher = Flasher(self.view.clock.box.label,
                               self.master, self.settings)
        self.model = Model()
        self.view.make_board()
        self.view.board.model = self.model
        self.view.draw_board()
        self.add_callbacks()
        self.view.game_over()

    def init_game(self):
        self.model = Model()
        self.view.clock_init()
        self.view.clock_restart()
        self.view.make_board()
        self.view.board.model = self.model
        self.view.draw_board()
        self.add_callbacks()
        self.add_event()
        self.finished = False
        self.board_clicked = False
        self.this_move = None
        self.this_hint = None
        self.move_requested = False
        self.transcript_index = None
        self.loaded_transcript = []
        self.set_strategies()
        self.board = self.model.initial_board()
        if self.settings.dic['game_type'] == 'human_v_machine':
            self.active = True
        else:
            self.active = False
        self.view.game_on()
        self.view.draw_board()
        self.generate_virtual_event()

    def get_legal_human_moves(self):
        moves = self.model.legal_moves(self.humans_colour,
                                       self.board)
        tmp = [self.model.lookup.index(move) for move in moves]
        self.legal_human_moves = moves
        self.legal_human_board_moves = tmp

    def generate_virtual_event(self):
        self.master.event_generate(self.VIRTUAL_EVENT, when="tail")

    def start_turn(self):
        PzlG.logger.logger.info("start_turn")
        if self.is_finished():
            self.end_game()
        else:
            self.this_move = None
            if self.is_human():
                self.view.clock_restart()
                self.hint_requested = False
                self.view.game_on()
                self.view.hint_off()
                self.get_legal_human_moves()
                if not self.legal_human_moves:
                    self.swap_player()
                    self.generate_virtual_event()
            else:
                if self.settings.dic['game_type'] == 'human_v_machine':
                    PzlG.logger.logger.info("machine_turn")
                    moves = self.model.legal_moves(self.player,
                                                   self.board)
                    if moves:
                        self.view.hint_off()
                        self.view.config(cursor="watch")
                        self.view.board.update_idletasks()
                        # do move
                        strategy = self.strategies_dic[self.player]
                        move = self.model.get_move(strategy,
                                                   self.player,
                                                   self.board)
                        square = self.model.lookup.index(move)
                        self.view.board.highlight_square(square)
                        self.view.board.update_idletasks()
                        self.wait_move()
                        self.view.board.unhighlight_square(square)
                        self.view.board.update_idletasks()
                        self.model.make_move(move, self.player, self.board)
                        self.model.update_transcript(move)
                        rep = self.model.get_board(self.board)
                        self.draw_board(rep)
                        self.get_scores()
                        self.view.update_score_box(self.scores)
                        self.view.config(cursor="arrow")
                        self.view.board.update_idletasks()
                    self.swap_player()
                    self.generate_virtual_event()
                else:
                    # must be machine v machine
                    PzlG.logger.logger.info("machine_v_machine_turn")
                    self.move_requested = False
                    moves = self.model.legal_moves(self.player,
                                                   self.board)
                    if not moves:
                        self.swap_player()
                        self.generate_virtual_event()

    def end_turn(self):
        PzlG.logger.logger.info("end_turn")
        if self.is_human():
            self.tidy_hint()
            self.hint_requested = False
            self.board_clicked = False
            self.view.clock_stop()
        else:
            self.move_requested = False
        self.get_scores()
        self.view.update_score_box(self.scores)
        if self.finished:
            self.end_game()
        else:
            self.swap_player()
            self.generate_virtual_event()

    def draw_board(self, board):
        for i in range(Sgg.grid_size):
            j = Sgg.VACANT
            if board[i] == self.model.BLACK:
                j = Sgg.BLACK
            if board[i] == self.model.WHITE:
                j = Sgg.WHITE
            self.model.datum[i] = j
        self.view.draw_board()
        self.view.board.update_idletasks()

    def event_handler(self, *args):
        """
        Handle all events, real or generated here.
        args[0] gives event type:
        0 square_event event, square_index
        2 toolbar button_index, mouse_index
        self.VIRTUAL_EVENT generated
        """
        if args[0] == 0:
            # square event
            self.apply_humans_move()
        elif args[0] == 2:
            # toolbar
            if args[1] == 1:
                # hint button
                if self.hint_requested:
                    # accepting hint
                    if self.board_clicked:
                        self.apply_humans_move()
        elif args[0] == self.VIRTUAL_EVENT:
            self.start_turn()
        else:
            PzlG.logger.logger.error("event_handler error" + str(args[0]))

    def add_event(self):
        # To enable the player to control the action need to
        # define a virtual event that can be added to the event loop
        self.master.bind(self.VIRTUAL_EVENT, self.virtual_event)

    def tidy_hint(self):
        if self.this_hint is not None:
            square = self.model.lookup.index(self.this_hint)
            self.view.board.unhighlight_square(square)

    def give_hint(self):
        if not self.hint_requested:
            self.view.config(cursor="watch")
            self.view.board.update_idletasks()
            self.view.hint_on()
            self.hint_requested = True
            strategy = self.strategies_dic[self.player]
            self.this_hint = self.model.get_move(strategy,
                                                 self.player,
                                                 self.board)
            if self.this_hint is not None:
                self.this_move = self.this_hint
                square = self.model.lookup.index(self.this_hint)
                self.view.board.highlight_square(square)
                self.view.hint_available()
                PzlG.logger.logger.info("give_hint " + str(self.this_hint))
        else:
            if self.this_hint:
                self.apply_humans_move()

    def apply_humans_move(self):
        PzlG.logger.logger.info("apply_humans_move " + str(self.this_move))
        self.model.make_move(self.this_move, self.player, self.board)
        self.model.update_transcript(self.this_move)
        rep = self.model.get_board(self.board)
        self.tidy_hint()
        self.draw_board(rep)
        self.end_turn()

    def get_machines_move(self):
        if not self.move_requested:
            self.move_requested = True
            if self.transcript_index is None:
                self.view.config(cursor="watch")
                self.view.board.update_idletasks()
                # try regular machine move
                strategy = self.strategies_dic[self.player]
                move = self.model.get_move(strategy,
                                           self.player,
                                           self.board)
                if move is not None:
                    square = self.model.lookup.index(move)
                    self.view.board.highlight_square(square)
                    self.this_move = move
                    PzlG.logger.logger.info("machine move " + str(move))
            else:
                # displaying transcript
                moves = self.model.legal_moves(self.player, self.board)
                if moves:
                    move = self.next_transcript_move()
                    if move is not None:
                        square = self.model.lookup.index(move)
                        self.view.board.highlight_square(square)
                        self.this_move = move
        else:
            if self.this_move:
                self.apply_machines_move()

    def apply_machines_move(self):
        self.model.make_move(self.this_move, self.player, self.board)
        self.model.update_transcript(self.this_move)
        square = self.model.lookup.index(self.this_move)
        self.view.board.unhighlight_square(square)
        rep = self.model.get_board(self.board)
        self.draw_board(rep)
        self.view.config(cursor="arrow")
        self.view.board.update_idletasks()
        self.this_move = None
        self.end_turn()

    def virtual_event(self, *args):
        """
        Respond to generated event
        """
        self.event_handler(self.VIRTUAL_EVENT)

    def wait_move(self):
        seconds = int(self.settings.dic['move_pause'])
        time.sleep(seconds)

    def swap_player(self):
        if self.player == Sgg.BLACK:
            self.player = Sgg.WHITE
        else:
            self.player = Sgg.BLACK

    def add_callbacks(self):
        self.view.add_menu_callback(self.service_menu)
        self.view.add_toolbar_callback(self.service_toolbar)
        self.view.board.add_callbacks(self.square_event)

    def service_menu(self, *args):
        """
        Respond to menu choices
        """

        strargs = ''
        for item in args:
            strargs += ' ' + item
        PzlG.logger.logger.info("service_menu " + strargs)
        name = args[0]
        if name == 'font_size':
            self.set_font_size()
        elif name == 'load_board':
            self.load_board()
        elif name == 'save_board':
            self.save_board()
        elif name == 'load_transcript':
            self.load_transcript()
        elif name == 'save_transcript':
            if any(x != 0 for x in self.model.transcript):
                self.save_transcript()
        elif name == 'humans_colour':
            self.set_humans_colour()
        elif name == 'set_colour':
            choice = args[1]
            self.set_colour(choice)
        elif name == 'save_settings':
            self.settings.preferences.save()
        elif name == 'about':
            self.view.about()
        elif name == 'help':
            self.view.help()

    def service_toolbar(self, button_index, mouse_index):
        PzlG.logger.logger.info("service_toolbar " +
                                str(button_index) +
                                ' ' +
                                str(mouse_index))
        if mouse_index == 2:
            alg_index = None
            self.view.do_tooltip(button_index, alg_index)
        elif mouse_index == 1:
            if button_index == 0:
                self.init_game()
            elif button_index == 1:
                if not self.finished:
                    if self.settings.dic['game_type'] == 'human_v_machine':
                        self.give_hint()
                    else:
                        self.get_machines_move()
            # nb, unlike other programs, here we go to
            # the event_handler
            # which controls the overall execution of the game
            self.event_handler(2, button_index)

    def square_event(self, event, square_id):
        if self.active and square_id in self.legal_human_board_moves:
            if event.type == "7":
                # 'enter'
                job = 0
                self.view.board.update_board(square_id, job)
            if event.type == "8":
                # 'leave'
                job = 1
                self.view.board.update_board(square_id, job)
            if event.type == "5":
                mouse_index = event.num
                PzlG.logger.logger.info("square_event " +
                                        str(square_id))
                self.board_clicked = True
                square = self.legal_human_board_moves.index(square_id)
                item = self.legal_human_moves[square]
                # square_event square overrides any current hint
                self.this_move = item
                self.event_handler(0)

    def end_game(self):
        PzlG.logger.logger.info("end_game")
        self.view.clock_stop()
        self.view.config(cursor="arrow")
        self.get_scores()
        self.view.update_score_box(self.scores)
        self.view.board.update_idletasks()
        self.view.game_over()
        self.flasher.flash()

    def get_scores(self):
        human_score = 0
        machine_score = 0
        for square_id in range(Sgg.grid_size):
            datum = self.model.datum[square_id]
            if datum == self.humans_colour:
                human_score += 1
            elif datum != Sgg.VACANT:
                machine_score += 1
        self.scores = str(human_score) + ' ' + str(machine_score)

    def set_black_depth(self):
        self.black_depth = int(self.settings.dic['black_look_ahead'])

    def set_white_depth(self):
        self.white_depth = int(self.settings.dic['white_look_ahead'])

    def set_strategies(self):
        depth = int(self.settings.dic['black_look_ahead'])
        name = self.settings.dic['black_algorithm']
        self.black_strategy = self.set_strategy(name, depth)
        depth = int(self.settings.dic['white_look_ahead'])
        name = self.settings.dic['white_algorithm']
        self.white_strategy = self.set_strategy(name, depth)
        self.strategies_dic[self.model.BLACK] = self.black_strategy
        self.strategies_dic[self.model.WHITE] = self.white_strategy

    def set_strategy(self, name, depth):
        if name == 'random':
            strategy = self.model.random_strategy
        elif name == 'max-diff':
            strategy = self.model.maximizer(self.model.score)
        elif name == 'max-weighted-diff':
            strategy = self.model.maximizer(self.model.weighted_score)
        elif name == 'minimax-diff':
            strategy = self.model.minimax_searcher(depth, self.model.score)
        elif name == 'minimax-weighted-diff':
            strategy = self.model.minimax_searcher(depth,
                                                   self.model.weighted_score)
        elif name == 'ab-diff':
            strategy = self.model.alphabeta_searcher(depth,
                                                     self.model.score)
        elif name == 'ab-weighted-diff':
            strategy = self.model.alphabeta_searcher(depth,
                                                     self.model.weighted_score)
        return strategy

    def set_humans_colour(self):
        self.humans_colour = self.settings.dic['humans_colour']

    def set_font_size(self):
        self.settings.do_scaling()
        self.start_game()

    def set_colour(self, choice):
        try:
            bg_colour = self.settings.dic[choice]
            result = tkColorChooser.askcolor(bg_colour)
            if result[1] is not None:
                self.settings.dic[choice] = result[1]
                self.start_game()
        except KeyError:
            PzlG.logger.logger.error("set_colour " + choice)

    def save_board(self):
        my_file = self.view.sg_open_file(True, _('Output file'))
        if my_file:
            item = 0
            for y in range(8):
                line = ''
                for x in range(8):
                    line += self.model.datum[item]
                    item += 1
                line += '\n'
                my_file.write(line)
            # assume we can only interrupt the game on human's turn
            line = self.humans_colour + '\n'
            my_file.write(line)
            my_file.close()

    def load_board(self):
        self.active = False
        self.model = Model()
        self.view.make_board()
        self.view.board.model = self.model
        self.view.draw_board()
        self.view.update()
        self.add_event()
        self.finished = False
        self.board_clicked = False
        self.this_hint = None
        board, player = self.load_board_file()
        if board:
            self.board = board
            self.player = player
            self.view.config(cursor="arrow")
            self.view.update()
            self.set_strategies()
            rep = self.model.get_board(self.board)
            self.draw_board(rep)
            self.add_callbacks()
            self.active = False
            if self.settings.dic['game_type'] == 'human_v_machine':
                self.active = True
            self.start_turn()
        else:
            self.init_game()

    def load_board_file(self):
        board = []
        player = '.'
        my_file = self.view.sg_open_file(False, _('Input file'))
        if my_file:
            board, player = self.model.load_board(my_file)
        return board, player

    def save_transcript(self):
        my_file = self.view.sg_open_file(True, _('Output file'))
        if my_file:
            item = 0
            for y in range(8):
                for x in range(8):
                    my_file.write('{:3d}'.format(self.model.transcript[item]))
                    item += 1
                my_file.write('\n')
            my_file.close()

    def load_transcript(self):
        self.active = False
        self.model = Model()
        self.view.make_board()
        self.view.board.model = self.model
        self.view.draw_board()
        self.view.update()
        self.add_event()
        self.finished = False
        self.board_clicked = False
        self.this_hint = None
        transcript = self.load_transcript_file()
        if transcript:
            self.board = self.model.initial_board()
            self.view.draw_board()
            self.player = self.model.BLACK
            self.play_transcript(transcript)
        else:
            self.init_game()

    def load_transcript_file(self):
        transcript = []
        my_file = self.view.sg_open_file(False, _('Input file'))
        if my_file:
            transcript = self.model.load_transcript_file(my_file)
        return transcript

    def next_transcript_move(self):
        self.transcript_index += 1
        if self.transcript_index < len(self.loaded_transcript):
            return self.loaded_transcript[self.transcript_index]
        else:
            self.finished = True
            self.end_game()

    def play_transcript(self, transcript):
        self.transcript_index = -1
        self.loaded_transcript = transcript
        self.view.game_on()
        self.settings.dic['game_type'] = 'machine_v_machine'
        self.start_turn()


INITIALISE = PzlG()
if __name__ == '__main__':
    try:
        ROOT = tk.Tk()
        ROOT.withdraw()
        APP = Controller(ROOT)
        ROOT.mainloop()
        PzlG.logger.logger.info("Stop program")
    except:
        PzlG.logger.logger.info("Failure!")
        PzlG.logger.logger.exception("Unhandled exception during main")
