#--------------------------------------------------------------------------
#Copyright 2002, Jyrki Alakuijala and Hannu Helminen.
#This program is free software; you can redistribute it and/or modify
#it under the terms of the GNU General Public License version 2 
#as published by the Free Software Foundation.
#
#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.
#--------------------------------------------------------------------------
from math import atan, pi

knightMovesBoardLookup = [None] * 64
kingMovesBoardLookup = [None] * 64
rookMovesBoardLookup0 = [None] * 64
rookMovesBoardLookup1 = [None] * 64
rookMovesBoardLookup2 = [None] * 64
rookMovesBoardLookup3 = [None] * 64
bishopMovesBoardLookup0 = [None] * 64
bishopMovesBoardLookup1 = [None] * 64
bishopMovesBoardLookup2 = [None] * 64
bishopMovesBoardLookup3 = [None] * 64
pawnAttackBoardLookupWhite = [None] * 64
pawnAttackBoardLookupBlack = [None] * 64

white=1
black=-1

# lockdir: { 0: "no lock", 1: "up-right", 2: "up-left", 3: "right", 4: "up"}

bishopMovesBoardLookups = (
# lut, dx, dy, lockdir, attackthroughpawn
      (bishopMovesBoardLookup0, 1, 1, 1, white),
      (bishopMovesBoardLookup1, 1, -1, 2, black),
      (bishopMovesBoardLookup2, -1, 1, 2, white),
      (bishopMovesBoardLookup3, -1, -1, 1, black)
)

rookMovesBoardLookups = (
      (rookMovesBoardLookup0, 1, 0, 3),
      (rookMovesBoardLookup1, -1, 0, 3),
      (rookMovesBoardLookup2, 0, 1, 4),
      (rookMovesBoardLookup3, 0, -1, 4),
)

(free,pawn,knight,bishop,rook,queen,king)=range(7)

pieceSymbols = " PNBRQKkqrbnp"


knightMoves = ((2, 1), (1, 2), 
               (-2, 1), (-1, 2), 
               (2, -1), (1, -2), 
               (-2, -1), (-1, -2))


centerMap = (
0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00,
0.07, 0.10, 0.07, 0.02, 0.02, 0.07, 0.10, 0.07,
0.14, 0.20, 0.30, 0.35, 0.35, 0.30, 0.20, 0.04,
0.22, 0.32, 0.45, 0.55, 0.55, 0.45, 0.32, 0.22,
0.22, 0.32, 0.45, 0.55, 0.55, 0.45, 0.32, 0.22,
0.14, 0.20, 0.30, 0.35, 0.35, 0.30, 0.20, 0.04,
0.07, 0.10, 0.07, 0.02, 0.02, 0.07, 0.10, 0.07,
0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00,
)

bishopDirections = ((1,1),(-1,1),(1,-1),(-1,-1))
rookDirections = ((1,0),(-1,0),(0,-1),(0,-1))
kingMoves = ((-1,-1), (0,-1), (1,-1), (-1,0), (1,0), (-1,1), (0,1), (1,1))

def KingRowForColor(color): 
  return (None,0,7)[color]

def IndexToPosition(i):
  if i == None:
    return "None"
  return "abcdefgh"[i & 7] + "12345678"[i / 8]

class Move:
  castlingSideQueen = "O-O-O"
  castlingSideKing = "O-O"
  capture = "%sx%s"
  normal = "%s-%s"
  def __init__(m,fromIx=None,toIx=None,mode=normal,promotion=None):
    m.fromIx = fromIx
    m.toIx = toIx
    m.mode = mode
    m.promotion = promotion
  def __repr__(m):
    promostr = ""
    if m.promotion:
      promostr = pieceSymbols[abs(m.promotion)]
    if m.mode == m.castlingSideQueen or m.mode == m.castlingSideKing:
      return m.mode
    return m.mode % (
      IndexToPosition(m.fromIx),
      IndexToPosition(m.toIx)
    ) + promostr
  def __hash__(m):
    return hash(tuple(m.fromIx, m.toIx, m.promotion))

class Board:
  def CastlingTuple(m):
    return (m.castlingWhiteKing,
	    m.castlingWhiteQueen,
	    m.castlingBlackKing,
	    m.castlingBlackQueen);

  def Setup(m):
    m.killermoves = [None, [], []]
    m.useOpeningLib = 1
    m.gamename = ""
    m.turn = white
    m.castlingWhiteKing = 0
    m.castlingWhiteQueen = 0
    m.castlingBlackKing = 0
    m.castlingBlackQueen = 0
    m.board = [0] * 64
    m.enpassant = -99
    order=(rook,knight,bishop,queen,king,bishop,knight,rook)
    m.castlingBonus = 0
    for i in range(8):
      m.board[0 * 8 + i] = order[i]
      m.board[1 * 8 + i] = pawn
      m.board[6 * 8 + i] = -pawn
      m.board[7 * 8 + i] = -order[i]
    m.movesWithOutHittingOrMovingPawns = 0
    m.attackMapHistory = []
    m.moveCount = 0
    m.movesForPlayerInTurn = []
    m.boardHistory = []
    m.moveHistory = []
    m.kingMobility = [None, None, None]
    m.StoreBoard()
    m.UpdateKingAndQueenIndex()
    m.pondering = 0
    m.evalDepth = 0
    m.progressEstimate = None
#    m.PushLockedAndAttackMaps(None, None, None)

  def Clear(m):
    m.board = [0] * 64

  def Equal(m, p):
    return (
      m.turn == p.turn and
      m.board == p.board and
      m.castlingWhiteKing == p.castlingWhiteKing and
      m.castlingWhiteQueen == p.castlingWhiteQueen and
      m.castlingBlackKing == p.castlingBlackKing and
      m.castlingBlackQueen == p.castlingBlackQueen and
      m.enpassant == p.enpassant 
    )

  def LightPositionCopyFrom(m, p):
    import copy
    m.board = copy.copy(p.board)
    m.castlingWhiteKing = p.castlingWhiteKing
    m.castlingWhiteQueen = p.castlingWhiteQueen
    m.castlingBlackKing = p.castlingBlackKing 
    m.castlingBlackQueen = p.castlingBlackQueen
    m.turn = p.turn
    m.enpassant = p.enpassant
    m.evalDepth = p.evalDepth
      
  def __hash__(m):
#    return hash(tuple(m.board))
    j = hash(tuple(m.board)) * 11L + hash((m.enpassant * 0x121, m.turn * 0x123451,
              m.castlingWhiteKing,
              m.castlingWhiteQueen,
              m.castlingBlackKing,
              m.castlingBlackQueen))
    for i in range(64):
      j = j + m.board[i] * (i + 11) * (i + 53) * i * 53198111L
    return hash(j)

  def RetractMove(m):
    m.evalIsCurrent = 0
    move = m.moveHistory[-1]
#    print "RAT retracting", move, len(m.movesForPlayerInTurn), m.moveCount, m.moveHistory

    m.lockmap = m.attackMapHistory[-1][0]
    m.lockmapQueen = m.attackMapHistory[-1][1]
    m.attackmap = m.attackMapHistory[-1][2]
    m.attackmapFromLocked = m.attackMapHistory[-1][3]

    del m.boardHistory[-1]
    del m.moveHistory[-1]

    if len(m.attackMapHistory) == m.moveCount + 1:
      del m.attackMapHistory[-1]

    if len(m.movesForPlayerInTurn) == m.moveCount + 1:
      del m.movesForPlayerInTurn[-1]

    m.moveCount = m.moveCount - 1

    m.castlingBonus = move.historyCastlingBonus
    m.castlingWhiteKing = move.historyCastlingOkWhiteKing
    m.castlingWhiteQueen = move.historyCastlingOkWhiteQueen
    m.castlingBlackKing = move.historyCastlingOkBlackKing 
    m.castlingBlackQueen = move.historyCastlingOkBlackQueen

    m.movesWithOutHittingOrMovingPawns = move.historyMoves
    m.enpassant = move.historyEnpassant
    if hasattr(move, "historyCastling"):
      m.board[move.historyCastling[1]] = m.board[move.historyCastling[0]]
      m.board[move.historyCastling[0]] = 0
    m.turn = -m.turn
    if move.fromIx != None and move.toIx != None:
      m.board[move.fromIx] = m.board[move.toIx]
      if move.promotion:
        m.board[move.fromIx] = m.turn * pawn
      m.board[move.toIx] = move.historyCapture
      if (move.mode == Move.capture and move.historyCapture == 0): # enpassant
        m.board[(move.fromIx & ~7) + m.enpassant] = -m.turn * pawn
      m.UpdateKingAndQueenIndex()


  # returns 2 for sure block, 1 for unsure and 0 for sure no
  # unsure is caused by the fact that an undefended blocker
  # may create more (unattacked) space for the king to move into
  def CanBlockACheck(m, ix):
    t = m.turn
    am = m.attackmap[ix]
    ac = am[t * knight] + am[t * bishop] + am[t * rook] + am[t * queen]
    defence = am[t * king] + am[t * pawn]
    if ac >= 1 and ac + defence >= 2: # can move a blocker and defend it
      return 2
    if ac + defence == 0:
      return 0
    # check pawns, our last resort for blocking
    pawndir = m.turn * 8
    # test single move:
    try:
      ixp = ix - pawndir
      if m.board[ixp] == t * pawn and not m.lockmap[ixp]:
        if ac + defence >= 1:
          return 2
      elif m.board[ixp] == 0:
        ixp = ix - 2 * pawndir
        if m.board[ixp] == t * pawn and not m.lockmap[ixp]:
          if ac + defence >= 1:
            return 2
    except IndexError:
      pass # the pawn could be there, anyway
    if ac == 0:
      return 0
    return 1

  def IsAttacked(m, pos):
    try:
      if not (m.moveCount == (len(m.attackMapHistory) - 1)):
        print "isattacked", m.moveCount, len(m.attackMapHistory) - 1
        for mov in m.moveHistory:
          print "move", mov
        raise ("isattacked %d %d" % (m.moveCount, len(m.attackMapHistory) - 1))

      assert(m.moveCount == (len(m.attackMapHistory) - 1))
      t = -m.turn
      am = m.attackmap[pos]
      return (m.attackmapFromLocked[pos][t] or
        am[t * pawn] or am[t * knight] or am[t * bishop] or
        am[t * rook] or am[t * queen] or am[t * king])
    except TypeError,a:
      print "m.attackmap", m.attackmap
      print type(m.attackmap)
      print m.attackmap[pos]
      print type(m.attackmap[pos])
      print m.attackmapFromLocked
      print type(m.attackmapFromLocked)
      print pos
      print type(pos)
      print t
      print type(t)
      raise TypeError,a

  def IsDefended(m, pos):
    assert m.moveCount == len(m.attackMapHistory) - 1
    t = m.turn
    am = m.attackmap[pos]
    return (m.attackmapFromLocked[pos][t] or
        am[t * pawn] or am[t * knight] or am[t * bishop] or
        am[t * rook] or am[t * queen] or am[t * king])

  def PushLockedAndAttackMaps(m, lockmap, lockmapQueen, attackmap, attackmapFromLocked):
#    print "PUSH", m, len(m.attackMapHistory), attackmap[0] 
    m.lockmap = lockmap
    m.lockmapQueen = lockmapQueen
    m.attackmap = attackmap
    m.attackmapFromLocked = attackmapFromLocked
    m.attackMapHistory.append((m.lockmap, m.lockmapQueen, m.attackmap, m.attackmapFromLocked))
    assert(len(m.attackMapHistory) == len(m.moveHistory) + 1)

  def PopLockedAndAttackMaps(m):
#    print "POP", m, len(m.attackMapHistory)
    del m.attackMapHistory[-1]
    try:
      m.lockmap = m.attackMapHistory[-1][0]
      m.lockmapQueen = m.attackMapHistory[-1][1]
      m.attackmap = m.attackMapHistory[-1][2]
      m.attackmapFromLocked = m.attackMapHistory[-1][3]
    except IndexError:
      m.lockmap = None
      m.lockmapQueen = None 
      m.attackmap = None
      m.attackmapFromLocked = None

  def CountRepetitions(m):
    # vertically locked enpassant captures are not correctly 
    # managed for board reps... 
    # however, even fritz 6 and 7 fail in this
    boardfind = (tuple(m.board), m.turn, 
		 (m.castlingWhiteKing,
		  m.castlingWhiteQueen,
		  m.castlingBlackKing,
		  m.castlingBlackQueen), m.enpassant) 
    return m.boardHistory.count(boardfind)

  def UpdateKingAndQueenIndex(m):
    m.kingIx = [None, None, None]
    try:
      m.kingIx[1] = m.board.index(king)
    except ValueError:
      pass # king not found
    try:
      m.kingIx[-1] = m.board.index(-king)
    except ValueError:
      pass # king not found
    m.queenIx = [None, None, None]
    try:
      m.queenIx[1] = m.board.index(queen)
    except ValueError:
      pass # queen not found
    try:
      m.queenIx[-1] = m.board.index(-queen)
    except ValueError:
      pass # queen not found

  def CalculateGameName(m):
    if (m.useOpeningLib):
      from openinglibrary import gameName
      m.gamename = gameName(m.moveHistory)
      print "GAMENAME", m.gamename
    else:
      m.gamename = "no opening lib"

  def Move(m, move):
    m.evalIsCurrent = 0
#    print "NAT moving", move, m.moveCount, len(m.attackMapHistory)

    if move.fromIx != None or move.toIx != None:
      if (m.board[move.fromIx] * m.turn <= 0):
	if (repr(move) == repr(m.moveHistory[-1])):
          print "moving twice the same move"
        elif m.board[move.fromIx] == 0:
          print "moving empty square"
        if m.board[move.fromIx] * m.turn < 0:
          print "moving opponents piece"
	PrintBoard(m)
	PrintBoardDebug(m)
        print "moving", move, m.moveCount, len(m.attackMapHistory)
        raise ("%s %d %s %d" % ("turn is", m.turn, ", moving piece", m.board[move.fromIx]))
    if type(move) == type(""):
      print move
      m.boardHistory.append(None)
      m.moveHistory.append(move)
      return

    m.moveCount = m.moveCount + 1
    
    import copy

    move.historyCastlingOkWhiteKing = m.castlingWhiteKing
    move.historyCastlingOkWhiteQueen = m.castlingWhiteQueen
    move.historyCastlingOkBlackKing  = m.castlingBlackKing
    move.historyCastlingOkBlackQueen = m.castlingBlackQueen
    move.historyCastlingBonus = m.castlingBonus
    move.historyEnpassant = m.enpassant
    move.historyMoves = m.movesWithOutHittingOrMovingPawns

    if move.toIx == None and move.fromIx == None: # null move
      m.enpassant = -99
    else:
      move.historyCapture = m.board[move.toIx]
    
      if (abs(m.board[move.fromIx]) == pawn and
          abs(move.fromIx - move.toIx) == 16):
        m.enpassant = move.fromIx & 0x7
      else:
        m.enpassant = -99

      if (abs(m.board[move.fromIx]) == pawn or
	      abs(m.board[move.toIx]) != 0):
         m.movesWithOutHittingOrMovingPawns = 0
      else:
        m.movesWithOutHittingOrMovingPawns = m.movesWithOutHittingOrMovingPawns + 1

      # test for "en passant" capture
      if move.mode == Move.capture and m.board[move.toIx] == 0:
        m.board[move.toIx - 8 * m.turn] = 0

      m.board[move.toIx] = m.board[move.fromIx]
      m.board[move.fromIx] = 0
      # test for castlings
      if move.mode == Move.castlingSideQueen:
        m.board[move.fromIx & ~7] = 0
        m.board[(move.fromIx & ~7) + 3] = rook * m.turn
        move.historyCastling = ((move.fromIx & ~7) + 3, (move.fromIx & ~7) + 0)
        if m.turn > 0:
          m.castlingWhiteKing = 1
          m.castlingWhiteQueen = 1
        else:
          m.castlingBlackKing = 1
          m.castlingBlackQueen = 1
        m.castlingBonus = m.castlingBonus + m.turn * 0.3;
      elif move.mode == Move.castlingSideKing:
        m.board[(move.fromIx & ~7) + 7] = 0
        m.board[(move.fromIx & ~7) + 5] = rook * m.turn
        move.historyCastling = ((move.fromIx & ~7) + 5, (move.fromIx & ~7) + 7)
        if m.turn > 0:
          m.castlingWhiteKing = 1
          m.castlingWhiteQueen = 1
        else:
          m.castlingBlackKing = 1
          m.castlingBlackQueen = 1
        m.castlingBonus = m.castlingBonus + m.turn * 0.4;
      if m.turn == white:
        if move.fromIx == 0 or move.fromIx == 4:
          m.castlingWhiteQueen = 1
        if move.fromIx == 7 or move.fromIx == 4:
          m.castlingWhiteKing = 1
      else:
        if move.fromIx == 7*8 or move.fromIx == 7*8+4:
          m.castlingBlackQueen = 1
        if move.fromIx == 7*8+7 or move.fromIx == 7*8+4:
          m.castlingBlackKing = 1
      if m.turn == black:
        if move.toIx == 0:
          m.castlingWhiteQueen = 1
        if move.toIx == 7:
          m.castlingWhiteKing = 1
      else:
        if move.toIx == 7*8:
          m.castlingBlackQueen = 1
        if move.toIx == 7*8+7:
          m.castlingBlackKing = 1
      # promotions
      if move.promotion:
        m.board[move.toIx] = move.promotion
    m.turn = -m.turn
    m.boardHistory.append((tuple(m.board), m.turn, 
			   (m.castlingWhiteKing,
			    m.castlingWhiteQueen,
			    m.castlingBlackKing,
			    m.castlingBlackQueen),
			   m.enpassant))
    m.moveHistory.append(move)
    m.UpdateKingAndQueenIndex()

  def StoreBoard(m):
    m.boardHistory.append((tuple(m.board), m.turn, 
			   (m.castlingWhiteKing,
			    m.castlingWhiteQueen,
			    m.castlingBlackKing,
			    m.castlingBlackQueen),
			   m.enpassant))
  def LastMoveColor(m):
    return -m.turn

def GenerateMovesForSinglePoint(board, pos, moves, dx, dy):
  curx = (pos & 7) + dx
  cury = (pos / 8) + dy
  if ((curx & 31) >= 8 or (cury & 31) >= 8):
    return
  ix = curx + cury * 8
  if board.board[ix] == 0:
    moves.append(Move(pos, ix, Move.normal))
  elif board.board[ix] * board.board[pos] < 0:
    moves.append(Move(pos, ix, Move.capture))
  
def GenerateMovesForRow(board, pos, dx, dy, moves):
  x = pos & 7
  y = pos / 8
  for i in range(1,8):
    (curx, cury) = (x + i * dx, y + i * dy)
    if ((curx & 31) >= 8 or (cury & 31) >= 8):
      return
    ix = curx + cury * 8
    if board.board[ix] == 0:
      moves.append(Move(pos, ix, Move.normal))
    elif board.board[ix] * board.board[pos] < 0:
      moves.append(Move(pos, ix, Move.capture))
      return
    else:
      return

def GenerateMovesForLookupList(board, pos, lut, moves):
  for i in lut:
    if board.board[i] == 0:
      moves.append(Move(pos, i, Move.normal))
    elif board.board[i] * board.board[pos] < 0:
      moves.append(Move(pos, i, Move.capture))

def GenerateMovesForLookupRow(board, pos, lut, moves):
  for i in lut:
    if board.board[i] == 0:
      moves.append(Move(pos, i, Move.normal))
    elif board.board[i] * board.board[pos] < 0:
      moves.append(Move(pos, i, Move.capture))
      return
    else:
      return

def GenerateMovesForRook(board, pos, moves, lockmap):
  for (lut, dx, dy, lockdir) in rookMovesBoardLookups:
    if not lockmap[pos] or lockmap[pos] == lockdir:
      GenerateMovesForLookupRow(board, pos, lut[pos], moves)

def GenerateMovesForBishop(board, pos, moves, lockmap):
  for (lut, dx, dy, lockdir, atp) in bishopMovesBoardLookups:
    if not lockmap[pos] or lockmap[pos] == lockdir:
      GenerateMovesForLookupRow(board, pos, lut[pos], moves)

def GenerateMovesForQueen(board, pos, moves, lockmap):
  GenerateMovesForBishop(board, pos, moves, lockmap)
  GenerateMovesForRook(board, pos, moves, lockmap)

def TryCastlingSideKing(board, pos, moves):
  if (board.board[pos+1] != 0 or board.board[pos+2] != 0 or 
      board.IsAttacked(pos) or board.IsAttacked(pos + 1) or board.IsAttacked(pos + 2)):
    return
  moves.append(Move(pos, pos + 2, Move.castlingSideKing))

def TryCastlingSideQueen(board, pos, moves):
  if (board.board[pos-1] != 0 or board.board[pos-2] != 0 or board.board[pos-3] != 0 or
      board.IsAttacked(pos) or board.IsAttacked(pos - 1) or board.IsAttacked(pos - 2)):
    return
  moves.append(Move(pos, pos - 2, Move.castlingSideQueen))
  
def GenerateDestinationListForCheckedKing(board, pos):
  retval = []
  for i in kingMovesBoardLookup[pos]:
    if (board.IsAttacked(i) or board.board[i] * board.board[pos] > 0):
      continue
    retval.append(i) # free square or capture a non-defended piece
  return retval

def GenerateMovesForKing(board, pos, moves, lockmap):
  for i in kingMovesBoardLookup[pos]:
    if (board.IsAttacked(i)):
      continue
    if board.board[i] == 0:
      moves.append(Move(pos, i, Move.normal))
    elif board.board[i] * board.board[pos] < 0:
      moves.append(Move(pos, i, Move.capture))

  if board.turn > 0:
    if not board.castlingWhiteKing:
      TryCastlingSideKing(board, pos, moves)
    if not board.castlingWhiteQueen:
      TryCastlingSideQueen(board, pos, moves)
  else:
    if not board.castlingBlackKing:
      TryCastlingSideKing(board, pos, moves)
    if not board.castlingBlackQueen:
      TryCastlingSideQueen(board, pos, moves)

def GenerateMovesForKnight(board, pos, moves, lockmap):
  if (lockmap[pos]):
    return
  GenerateMovesForLookupList(board, pos, knightMovesBoardLookup[pos], moves)

def GenerateMovesForPawn(board, pos, moves, lockmap):
  if (lockmap[pos] == 3): # pawn cannot move at all, not even by capturing a piece
    return
  x = (pos & 7)
  y = (pos / 8)
  homerow = (None, 1, 6)[board.turn]
  promotionfromrow = (None, 6, 1)[board.turn]
  enpassantfromrow = (None, 4, 3)[board.turn]
  if not lockmap[pos] or lockmap[pos] == 4:
    if (y == homerow):
      ix = pos + 16 * board.turn
      if board.board[ix] == 0 and board.board[pos + 8 * board.turn] == 0:
        moves.append(Move(pos, ix, Move.normal))
  if (y == enpassantfromrow and abs(board.enpassant - x) == 1):
    ix = pos + 8 * board.turn - x + board.enpassant
    diff = abs(pos - ix)
    locked = lockmap[pos]
    keeplock = (diff == 7 and locked == 2) or (diff == 9 and locked == 1)
    if not locked or keeplock:
      moves.append(Move(pos, ix, Move.capture))

  ix = pos + 8 * board.turn
  promotionList = (None,)
  if y == promotionfromrow:
    promotionList = (None, (knight, bishop, rook, queen), (-knight, -bishop, -rook, -queen))[board.turn]
  for promotion in promotionList:
    if not lockmap[pos] or lockmap[pos] == 4:
      if board.board[ix] == 0:
        moves.append(Move(pos, ix, Move.normal, promotion)) 
    if x > 0:
      ix2 = pos + 8 * board.turn - 1
      if board.board[ix2] * board.turn < 0:
        diff = abs(pos - ix2)
        locked = lockmap[pos]
        keeplock = (diff == 7 and locked == 2) or (diff == 9 and locked == 1)
        if not locked or keeplock:
          moves.append(Move(pos, ix2, Move.capture, promotion))
    if x < 7:
      ix2 = pos + 8 * board.turn + 1
      if board.board[ix2] * board.turn < 0:
        diff = abs(pos - ix2)
        locked = lockmap[pos]
        keeplock = (diff == 7 and locked == 2) or (diff == 9 and locked == 1)
        if not locked or keeplock:
          moves.append(Move(pos, ix2, Move.capture, promotion))

# calculate a list of attackers:
# each attacker is a tuple of the index of the attacker
# and a sequence of squares betwen the attacker and the king
def CalculateKingAttackers(board, kingIx):
  b = board.board
  color = 1
  if b[kingIx] < 0:
    color = -1
  attacker = []
  
  x = kingIx & 7
  y = kingIx / 8
  pawnhitdir = color * 8
  if y + color >= 0 and y + color < 7:
    if x < 7 and b[kingIx + pawnhitdir + 1] == -color * pawn:
      attacker.append((kingIx + pawnhitdir + 1,()))
    if x > 0 and b[kingIx + pawnhitdir - 1] == -color * pawn:
      attacker.append((kingIx + pawnhitdir - 1,()))
  for ix in knightMovesBoardLookup[kingIx]:
    if board.board[ix] == -color * knight:
      attacker.append((ix,()))
  
  oppositeQueen = -color * queen
  oppositeRook = -color * rook
  oppositeBishop = -color * bishop
  for (lut, dx, dy, lockdir, atp) in bishopMovesBoardLookups:
    between = []
    for ix in lut[kingIx]:
      if b[ix] == oppositeQueen or b[ix] == oppositeBishop:
        attacker.append((ix, between))
      if (b[ix] != 0):
        break
      between.append(ix)
  for (lut, dx, dy, lockdir) in rookMovesBoardLookups:
    between = []
    for ix in lut[kingIx]:
      if b[ix] == oppositeQueen or b[ix] == oppositeRook:
        attacker.append((ix, between))
      if (b[ix] != 0):
        break
      between.append(ix)
  return attacker

def IsKingCheckedFast(board, color):
  if not board.kingIx[color]:
    return 1 # the king has been captured (which is a trick to enable mate detection in search)
  return board.IsAttacked(board.kingIx[color])

def IsKingChecked(board, color):
  
  b = board.board
  kingIx = board.kingIx[color]
  if kingIx == None:
    return 1
  assert b.count(king * color) == 1
  x = kingIx & 7
  y = kingIx / 8
  # pawns
  pawnhitdir = color * 8
  if y + color >= 0 and y + color < 7:
    if x < 7 and b[kingIx + pawnhitdir + 1] == -color * pawn:
      return -color * pawn
    if x > 0 and b[kingIx + pawnhitdir - 1] == -color * pawn:
      return -color * pawn
  for ix in knightMovesBoardLookup[kingIx]:
    if board.board[ix] == -color * knight:
      return -color * knight
  for ix in kingMovesBoardLookup[kingIx]:  
    if board.board[ix] == -color * king:
      return board.board[ix]
  oppositeQueen = -color * queen
  oppositeRook = -color * rook
  oppositeBishop = -color * bishop
  for (lut, dx, dy, lockdir, atp) in bishopMovesBoardLookups: # bishop (and queen)
    for ix in lut[kingIx]:
      if b[ix] == oppositeQueen or b[ix] == oppositeBishop:
        return b[ix]
      if (b[ix] != 0):
        break
  for (lut, dx, dy, lockdir) in rookMovesBoardLookups: # bishop (and queen)
    for ix in lut[kingIx]:
      if b[ix] == oppositeQueen or b[ix] == oppositeRook:
        return b[ix]
      if (b[ix] != 0):
        break
  return 0

def CanKingBeChecked(board, color):
  import copy
  
  b = board.board
  kingIx = board.kingIx[color]
  # no pawn check here...
  for ix in knightMovesBoardLookup[kingIx]:  # knight
    a = board.attackmap[ix]
    if a[-color * knight]:
      amc = copy.copy(a)
      amc[-color * knight] = amc[-color * knight] - 1
      cost = EvalSingleSquare(-color * knight, amc, board.turn, 0)
      if -cost * board.turn > 0.5:
        # cannot capture the attacker without cost
        return 1
  oppositeQueen = -color * queen
  oppositeRook = -color * rook
  oppositeBishop = -color * bishop
  for (lut, dx, dy, lockdir, atp) in bishopMovesBoardLookups: # bishop (and queen)
    for ix in lut[kingIx]:
      a = board.attackmap[ix]
      for p in (oppositeQueen, oppositeBishop):
        if a[p]:
          amc = copy.copy(a)
          amc[p] = amc[p] - 1
          cost = EvalSingleSquare(p, amc, board.turn, 0)
          if -cost * board.turn > 0.5:
            # cannot capture the attacker without cost
            return 1
      if (b[ix] != 0):
        break
  for (lut, dx, dy, lockdir) in rookMovesBoardLookups: # bishop (and queen)
    for ix in lut[kingIx]:
      a = board.attackmap[ix]
      for p in (oppositeQueen, oppositeRook):
        if a[p]:
          amc = copy.copy(a)
          amc[p] = amc[p] - 1
          cost = EvalSingleSquare(p, amc, board.turn, 0)
          if -cost * board.turn > 0.5:
            # cannot capture the attacker without cost
            return 1
  return 0

def CanQueenBeAttacked(board, color):
  import copy
  b = board.board
  queenIx = board.queenIx[color]
  if queenIx == None:
    return 0
  # no pawn check here...
  for ix in knightMovesBoardLookup[queenIx]:  # knight
    a = board.attackmap[ix]
    if a[-color * knight]:
      amc = copy.copy(a)
      amc[-color * knight] = amc[-color * knight] - 1
      cost = EvalSingleSquare(-color * knight, amc, board.turn, 0)
      if -cost * board.turn > 0.5:
        # cannot capture the attacker without cost
        return 1
  oppositeRook = -color * rook
  oppositeBishop = -color * bishop
  p = oppositeBishop
  for (lut, dx, dy, lockdir, atp) in bishopMovesBoardLookups: # bishop (and queen)
    for ix in lut[queenIx]:
      a = board.attackmap[ix]
      if a[p]:
        amc = copy.copy(a)
        amc[p] = amc[p] - 1
        cost = EvalSingleSquare(p, amc, board.turn, 0)
        if -cost * board.turn > 0.5:
          # cannot capture the attacker without cost
          return 1
      if (b[ix] != 0):
        break
  p = oppositeRook
  for (lut, dx, dy, lockdir) in rookMovesBoardLookups: # bishop (and queen)
    for ix in lut[queenIx]:
      a = board.attackmap[ix]
      if a[p]:
        amc = copy.copy(a)
        amc[p] = amc[p] - 1
        cost = EvalSingleSquare(p, amc, board.turn, 0)
        if -cost * board.turn > 0.5:
          # cannot capture the attacker without cost
          return 1
  return 0

def GenerateLockMapForKing(board, color, lockmap):
  ix = board.kingIx[color]
  if ix == None:
    return
  b = board.board
  oppositeQueen = -color * queen
  oppositeRook = -color * rook
  oppositeBishop = -color * bishop
  for (lut, dx, dy, lockdir, atp) in bishopMovesBoardLookups:
    lockpos = None
    for i in lut[ix]:
      if (b[i] == oppositeQueen or b[i] == oppositeBishop) and lockpos:
        lockmap[lockpos] = lockdir
        break
      if (b[i] * color < 0):
        break
      if (b[i] * color > 0):
        if lockpos:
          break
        else:
          lockpos = i
  for (lut, dx, dy, lockdir) in rookMovesBoardLookups:
    lockpos = None
    for i in lut[ix]:
      if (b[i] == oppositeQueen or b[i] == oppositeRook) and lockpos:
        lockmap[lockpos] = lockdir
        break
      if (b[i] * color < 0):
        break
      if (b[i] * color > 0):
        if lockpos:
          break
        else:
          lockpos = i

def GenerateLockMapForQueen(board, color, attackmap, lockmap):
  queenIx = board.queenIx[color]
  if queenIx == None:
    return
  oppositeQueen = -color * queen
  t = color
  am = attackmap[queenIx]
  queenisdefended = (am[t * pawn] or am[t * knight] or am[t * bishop] or
                     am[t * rook] or am[t * queen] or am[t * king])
  if queenisdefended:
    oppositeQueen = "Don't lock due to the opposite queen, since my queen is defended"
  oppositeRook = -color * rook
  oppositeBishop = -color * bishop
  b = board.board
  for (lut, dx, dy, lockdir, atp) in bishopMovesBoardLookups:
    lockpos = None
    for i in lut[queenIx]:
      if (b[i] == oppositeQueen or b[i] == oppositeBishop) and lockpos:
        lockmap[lockpos] = lockdir
        break
      if (b[i] * color < 0):
        break
      if (b[i] * color > 0):
        if lockpos:
          break
        else:
          lockpos = i
  for (lut, dx, dy, lockdir) in rookMovesBoardLookups:
    lockpos = None
    for i in lut[queenIx]:
      if (b[i] == oppositeQueen or b[i] == oppositeRook) and lockpos:
        lockmap[lockpos] = lockdir
        break
      if (b[i] * color < 0):
        break
      if (b[i] * color > 0):
        if lockpos:
          break
        else:
          lockpos = i

generateMoves = {
pawn : GenerateMovesForPawn,
knight : GenerateMovesForKnight,
bishop : GenerateMovesForBishop,
rook : GenerateMovesForRook,
queen : GenerateMovesForQueen,
king : GenerateMovesForKing,
}

def GenerateMoves(board):
  lockmap = board.lockmap
  moves = []
  # this ordering cut down ab search from a 2-level search of 134 to 80
  for x in (3, 4, 2, 5, 1, 6, 0, 7):
    for y in (3, 4, 2, 5, 1, 6, 0, 7):
      i = y * 8 + x
      piece = board.board[i]
      if (piece != 0 and piece * board.turn > 0):
        generateMoves[abs(piece)](board, i, moves,lockmap)
  return moves

def LegalMoves(board, moves):
  legalmoves = []
  for move in moves:
    board.Move(move)
    # the following check evaluation cannot be done from attackmaps, because
    # the attack maps are not yet calculated.
    checker = IsKingChecked(board, board.LastMoveColor()) # full test
    board.RetractMove()
    if not checker:
      legalmoves.append(move)
  return legalmoves

def GenerateAttacksForPawn(board, pos, lockmap, attackmap, attackmapFromLocked):
  cp = board.board[pos]
  locked = lockmap[pos]
  if (locked == 3): # pawn cannot move at all, not even by capturing a piece
    return
  x = (pos & 7)
  y = (pos / 8)
  if cp > 0:
    if (y == 4 and abs(board.enpassant - x) == 1):
      ix = pos + 8 + x + board.enpassant
      diff = ix - pos
      keeplock = (diff == 7 and locked == 2) or (diff == 9 and locked == 1)
      if not locked or keeplock:
        attackmap[ix][pawn] = attackmap[ix][pawn] + 1
        attackmap[ix - 8][pawn] = attackmap[ix - 8][pawn] + 4 
        # +4 pawns to make sure it captures without getting captured 
        # from that square (helps the evaluator a bit from the confusion 
        # that it seems that there is no actual pawn at the enpassant 
        # destination square)  ((Is this necessary?))
      else:
        attackmapFromLocked[ix][pawn] = attackmapFromLocked[ix][pawn] + 1
    if x > 0:
      ix = pos + 7
      if not locked or (locked == 2):
        attackmap[ix][cp] = attackmap[ix][cp] + 1
      else:
        attackmapFromLocked[ix][cp] = attackmapFromLocked[ix][cp] + 1
    if x < 7:
      ix = pos + 9
      if not locked or (locked == 1):
        attackmap[ix][cp] = attackmap[ix][cp] + 1
      else:
        attackmapFromLocked[ix][cp] = attackmapFromLocked[ix][cp] + 1
  else:
    if (y == 3 and abs(board.enpassant - x) == 1):
      ix = pos - 8 + x + board.enpassant
      diff = pos - ix
      keeplock = (diff == 7 and locked == 2) or (diff == 9 and locked == 1)
      if not locked or keeplock:
        attackmap[ix][-pawn] = attackmap[ix][-pawn] + 1
        attackmap[ix + 8][-pawn] = attackmap[ix + 8][-pawn] + 4 
# to make sure it captures without getting captured from that square (helps the evaluator a bit)
      else:
        attackmapFromLocked[ix][-pawn] = attackmapFromLocked[ix][-pawn] + 1
    if x > 0:
      ix = pos - 9
      if not locked or (locked == 1):
        attackmap[ix][cp] = attackmap[ix][cp] + 1
      else:
        attackmapFromLocked[ix][cp] = attackmapFromLocked[ix][cp] + 1
    if x < 7:
      ix = pos - 7
      if not locked or (locked == 2):
        attackmap[ix][cp] = attackmap[ix][cp] + 1
      else:
        attackmapFromLocked[ix][cp] = attackmapFromLocked[ix][cp] + 1


def GenerateAttacksForLookupList(board, pos, lut, attackmap):
  cp = board.board[pos]
  for i in lut:
    attackmap[i][cp] = attackmap[i][cp] + 1

def GenerateAttacksForLookupListFromLocked(board, pos, lut, attackmapFromLocked):
  color = 1
  if board.board[pos] < 0:
    color = -1
  for i in lut:
    attackmapFromLocked[i][color] = attackmapFromLocked[i][color] + 1

def GenerateAttacksForLookupRow(board, pos, lut, attackmap, nostop):
  color = 1
  if board.board[pos] < 0:
    color = -1
  oking = -color * king
  for i in lut:
    p = board.board[i]
    attackmap[i][board.board[pos]] = attackmap[i][board.board[pos]] + 1
    if p != 0 and p != nostop and p != oking:
      break

def GenerateAttacksForLookupRowThroughBishopAndOneStepOverPawn(board, pos, lut, attackmap, lockmap, lockdir, color):
  oking = -color * king
  stopOverPawn = None
  nostop = bishop * color
  cp = board.board[pos]
  for i in lut:
    p = board.board[i]
    attackmap[i][cp] = attackmap[i][cp] + 1
    if stopOverPawn:
      break
    if p != 0 and p != nostop and p != oking:
      if p == color * pawn:
        if lockmap[i]:
          break
        stopOverPawn = 1
        continue
      break

def GenerateAttacksForLookupRowFromLocked(board, pos, lut, attackmapFromLocked):
  color = 1
  if board.board[pos] < 0:
    color = -1
  for i in lut:
    attackmapFromLocked[i][color] = attackmapFromLocked[i][color] + 1
    if board.board[i] != 0:
      break

def GenerateAttacksForRook(board, pos, lockmap, attackmap, attackmapFromLocked):
  owncolor = 1
  if (board.board[pos] < 0):
    owncolor = -1
  for (lut, dx, dy, lockdir) in rookMovesBoardLookups:
    if not lockmap[pos] or lockmap[pos] == lockdir:
      GenerateAttacksForLookupRow(board, pos, lut[pos], attackmap, owncolor * rook)
    else:
      GenerateAttacksForLookupRowFromLocked(board, pos, lut[pos], attackmapFromLocked)

def GenerateAttacksForBishop(board, pos, lockmap, attackmap, attackmapFromLocked):
  owncolor = 1
  if (board.board[pos] < 0):
    owncolor = -1
  for (lut, dx, dy, lockdir, atp) in bishopMovesBoardLookups:
    if not lockmap[pos] or lockmap[pos] == lockdir:
      if atp == owncolor:
        GenerateAttacksForLookupRowThroughBishopAndOneStepOverPawn(board, pos, lut[pos], attackmap, lockmap, lockdir, owncolor)
      else:
        GenerateAttacksForLookupRow(board, pos, lut[pos], attackmap, owncolor * bishop)
    else:
      GenerateAttacksForLookupRowFromLocked(board, pos, lut[pos], attackmapFromLocked)

def GenerateAttacksForQueen(board, pos, lockmap, attackmap, attackmapFromLocked):
  GenerateAttacksForBishop(board, pos, lockmap, attackmap, attackmapFromLocked)
  GenerateAttacksForRook(board, pos, lockmap, attackmap, attackmapFromLocked)

def GenerateAttacksForKing(board, pos, lockmap, attackmap, attackmapFromLocked):
  # king can never be locked
  GenerateAttacksForLookupList(board, pos, kingMovesBoardLookup[pos], attackmap)

def GenerateAttacksForKnight(board, pos, lockmap, attackmap, attackmapFromLocked):
  if lockmap[pos]:
    GenerateAttacksForLookupListFromLocked(board, pos, knightMovesBoardLookup[pos], attackmapFromLocked)
  else:
    GenerateAttacksForLookupList(board, pos, knightMovesBoardLookup[pos], attackmap)

attacks = (
  None,
  GenerateAttacksForPawn,
  GenerateAttacksForKnight,
  GenerateAttacksForBishop,
  GenerateAttacksForRook,
  GenerateAttacksForQueen,
  GenerateAttacksForKing
)

def GenerateAllAttacks(board, lockmap, attackmap, attackmapFromLocked):
  for i in range(64):
    attackmap[i] = [0] * 13 # for signed piece
    attackmapFromLocked[i] = [None, 0, 0]
  for pos in range(64):
    v = board.board[pos]
    if v:
      attacks[abs(v)](board, pos, lockmap, attackmap, attackmapFromLocked)

def GenerateAttackMaps(board):
  if len(board.moveHistory) == len(board.attackMapHistory) - 1:
    return # the attackmap is already calculated

  lockmap = [None] * 64
  lockmapQueen = [None] * 64
  GenerateLockMapForKing(board, board.turn, lockmap)
  GenerateLockMapForKing(board, -board.turn, lockmap)
  attackmap = [None] * 64
  attackmapFromLocked = [None] * 64
  GenerateAllAttacks(board, lockmap, attackmap, attackmapFromLocked)

  GenerateLockMapForQueen(board, board.turn, attackmap, lockmapQueen)
  GenerateLockMapForQueen(board, -board.turn, attackmap, lockmapQueen)

  board.PushLockedAndAttackMaps(lockmap, lockmapQueen, attackmap, attackmapFromLocked)
  
# own pieces -1
# attacked squares -2
# others None
def GenerateKingMovementLimitMap(board, t):
  retval = []
  b = board.board
  o = -t
  for pos in range(64):
    if b[pos] * t > 0:
      retval.append(-1)
      continue
    am = board.attackmap[pos]
    if (board.attackmapFromLocked[pos][o] or
        am[o * pawn] or am[o * knight] or am[o * bishop] or
        am[o * rook] or am[o * queen] or am[o * king]):
      retval.append(-2)
    else:
      retval.append(None)
  return retval
        
# floodfill the limitmap with king movement to see how many
# moves it takes to move to a particular place
# if king is at a3, own pawns at a4 and b4, and opponents rook at d7
# the following map will be built (N is None)
"""
[ N,  N,  N, -2,  N,  N,  N,  N,
 -2, -2, -2, -2, -2, -2, -2, -2,
  4,  4,  4, -2,  N,  N,  N,  N,
  4,  3,  3, -2,  N,  N,  N,  N,
 -1, -1,  2, -2,  N,  N,  N,  N,
  0,  1,  2, -2,  N,  N,  N,  N,
  1,  1,  2, -2,  N,  N,  N,  N,
  2,  2,  2, -2,  N,  N,  N,  N]
"""

def KingMovement(limitmap, ix, v):
  for i in kingMovesBoardLookup[ix]:
    lm = limitmap[i]
    if lm == None or lm > v + 1:
      limitmap[i] = v + 1
      KingMovement(limitmap, i, v + 1)

def GenerateKingStepsMap(board, t):
  if board.kingIx[t] == None:
    board.kingMobility[t] = [None] * 64
    return 
  limitmap = GenerateKingMovementLimitMap(board, t)
  limitmap[board.kingIx[t]] = 0
  KingMovement(limitmap, board.kingIx[t], 0)
  board.kingMobility[t] = limitmap

def GenerateAllLegalMoves(board):
  if (len(board.movesForPlayerInTurn) == board.moveCount + 1):
    return board.movesForPlayerInTurn[-1]
  kingIx = board.kingIx[board.turn]
  assert kingIx >= 0
  check = 0
  GenerateAttackMaps(board)
  if IsKingCheckedFast(board, board.turn):
    check = 1
  moves = GenerateMoves(board)
  if check:
    moves = LegalMoves(board, moves)
  board.movesForPlayerInTurn.append(moves)
  return moves

#  moves = GenerateMoves(board)
#  return LegalMoves(board, moves)
  
def InitializeLookup():
  board = Board()
  board.Setup()
  for i in range(64):
    knightMovesBoardLookup[i] = []
    board.Clear()
    moves = []
    for (dx, dy) in knightMoves:
      GenerateMovesForSinglePoint(board, i, moves, dx, dy)
    for move in moves:
      knightMovesBoardLookup[i].append(move.toIx)

  for i in range(64):
    kingMovesBoardLookup[i] = []
    board.Clear()
    moves = []
    for (dx, dy) in kingMoves:
      GenerateMovesForSinglePoint(board, i, moves, dx, dy)
    for move in moves:
      kingMovesBoardLookup[i].append(move.toIx)

  for (lut, dx, dy) in (
      (rookMovesBoardLookup0, 1, 0),
      (rookMovesBoardLookup1, -1, 0),
      (rookMovesBoardLookup2, 0, 1),
      (rookMovesBoardLookup3, 0, -1),
      (bishopMovesBoardLookup0, 1, 1),
      (bishopMovesBoardLookup1, 1, -1),
      (bishopMovesBoardLookup2, -1, 1),
      (bishopMovesBoardLookup3, -1, -1)):
    for i in range(64):
      lut[i] = []
      board.Clear()
      moves = []
      GenerateMovesForRow(board, i, dx, dy, moves)
      for move in moves:
        lut[i].append(move.toIx)

  for i in range(64):
    pawnAttackBoardLookupWhite[i] = []  
    pawnAttackBoardLookupBlack[i] = []  
    board.Clear()
    x = i & 7
    y = i / 8
    if y < 7:
      if x >= 1:
        pawnAttackBoardLookupWhite[i].append(i + 8 - 1)
      if x < 7:
        pawnAttackBoardLookupWhite[i].append(i + 8 + 1)
    if y >= 1:
      if x >= 1:
        pawnAttackBoardLookupBlack[i].append(i - 8 - 1)
      if x < 7:
        pawnAttackBoardLookupBlack[i].append(i - 8 + 1)

InitializeLookup()


## evaluation start here

#Maximal movement, 1x0, 8x1, 16x2, 24x3, 15x4
"""
43333333
43222223
43211123
43210123
43211123
43222223
43333333
44444444
"""

def EvalKingMobility(board, color):
  # best achievable mobility will be around the bestmob
  bestmob = 404.0
  sum = 0.0
  for m in board.kingMobility[color]:
    if m and m >= 0 and m < 9:
      sum = sum + 9 - m
  return sum / bestmob

# return 0 for non-passed pawns
# return 1 for passed pawns
# return 2 for only own pieces blocking the passed pawn
# return 3 for passed pawns with free squares ahead 
# return 4 for passed pawns, with no squares attacked in the front
#		             (or an equal amount of rook/queen backup)

def IsPassedPawn(board, ix, color):
  xpos = ix & 7
  (firstrowMinus1, lastrowPlus1) = ((None, None), (-1, 8), (8, -1))[color]
  firstpos = firstrowMinus1 * 8 + xpos
  lastpos = lastrowPlus1 * 8 + xpos
  currow = ix / 8
  ownOfficers = (None, whiteOfficers, blackOfficers)[color]
  opposingOfficersMax = 0
  officers = 0
  for pos in range(ix + 8 * color, lastpos, 8 * color):
    if board.board[pos] == -color * pawn:
      return (0, abs(lastrowPlus1 - currow - color))
    if board.attackmap[pos][-color * pawn]: # opposing pawn
      return (0, abs(lastrowPlus1 - currow - color))
  block = 0
  ownblock = 0
  for pos in range(ix + 8 * color, lastpos, 8 * color):
    p = board.board[pos]
    if p != 0: 
      if p * color > 0:
        ownblock = 1
      else:
        return (1, abs(lastrowPlus1 - currow - color))
  if ownblock:
    return (2, abs(lastrowPlus1 - ix - 1))
  for pos in range(ix + 8 * color, lastpos, 8 * color):
    officerCount = 0
    for officers in ownOfficers:
      officerCount = (officerCount - 
       (board.attackmap[pos][officers] + board.attackmap[pos][pawn * color]) +
	board.attackmap[pos][-officers] +
        board.attackmap[pos][color * pawn])
    opposingOfficersMax = max(opposingOfficersMax, officerCount)
  if opposingOfficersMax < 0: #none of the squares is protected by the opponent
    return (4, abs(lastrowPlus1 - currow - color))
  # check out rook and queen support from back
  rookCount = 0
  for pos in range(ix - 8 * color, firstpos, -8 * color):
    p = board.board[pos]
    if p != 0:
      if p == color * rook or p == color * queen:
        rookCount = rookCount + 1
      else:
        break
  if opposingOfficersMax - rookCount < 0: #when counting the rooks, none of the squares is protected by the opponent
    return (4, abs(lastrowPlus1 - currow - color))
  else:
    return (3, abs(lastrowPlus1 - currow - color))

def PawnStructure(board):
  pawns = (None, [0] * 10, [0] * 10)
  passed = (None, [], [])
  for i in range(10):
    passed[1].append([])
    passed[-1].append([])
  backwardFunc = (None, min, max)
  backwardTable = (None, [9] * 10, [-1] * 10)
  rooks = (None, [], [])
  queenIx = [None, None, None] # expect only one queen
  kingIx = [None, 0, 0]
  for ix in range(64):
    y = ix / 8
    x = ix & 7
    p = board.board[ix]
    if p == pawn:
      pawns[1][x] = pawns[1][x] + 1
      passed[1][x].append(IsPassedPawn(board, ix, white))
      backwardTable[1][x] = min(backwardTable[1][x], y)
    elif p == -pawn:
      pawns[-1][x] = pawns[-1][x] + 1
      passed[-1][x].append(IsPassedPawn(board, ix, black))
      backwardTable[-1][x] = max(backwardTable[-1][x], y)
    elif p == rook:
      rooks[1].append(ix)
    elif p == -rook:
      rooks[-1].append(ix)
    elif p == king:
      kingIx[1] = ix
    elif p == -king:
      kingIx[-1] = ix
    elif p == queen:
      queenIx[1] = ix
    elif p == -queen:
      queenIx[-1] = ix

  backwardpawns = [None, [], []]
  sums = [None, 0, 0]
  for col in (-1,1):
    for i in range(0,8):
      if (col * backwardTable[col][i] < col * backwardTable[col][i + 1] and 
          col * backwardTable[col][i] < col * backwardTable[col][i - 1]):
        ix = i + 8 * backwardTable[col][i]
        blocked = 0
        if (board.board[ix + col * 8] * col > 0):
          blocked = 1 # own piece blocks the backward pawn
        else:
          blocked = 3 # opponents piece blocks the backward pawn
          sums[col] = sums[col] - 0.03
        # attack the backward pawn
        for piece in (None, blackOfficers, whiteOfficers)[col]:
          sums[col] = sums[col] - 0.015 * blocked * board.attackmap[ix][piece]
         
    pa = pawns[col]
    pas = passed[col]
    inturn = col == board.turn
    for x in range(8):
      if pa[x]:
        if pa[x - 1] == 0:# no partner on left
          sums[col] = sums[col] - 0.08 * pa[x]
          if pa[x + 1] == 0: # lonely pawn
            sums[col] = sums[col] - 0.08 * pa[x]
        if pa[x + 1] == 0: # no partner on right
          sums[col] = sums[col] - 0.08 * pa[x]
        if (pa[x] > 1): # douple or triple pawn
          sums[col] = sums[col] - 0.08 * (pa[x] - 1)
        for (pp,steps) in pas[x]:
          if pp == 1: # passed, blocked by opponent
            sums[col] = sums[col] + 0.05 + 0.01 * (7 - steps)
            if steps < 2:
              sums[col] = sums[col] + 0.1 * (2 - steps)
          elif pp == 2: # passed with blocked by own piece
            sums[col] = sums[col] + 0.09 + 0.03 * (7 - steps)
            if steps < 2:
              sums[col] = sums[col] + 0.13 * (2 - steps)
          elif pp == 3: # passed with free squares
            sums[col] = sums[col] + 0.11 + 0.05 * (7 - steps)
            if steps < 3:
              sums[col] = sums[col] + 0.05 * (3 - steps)
            if steps < 2:
              sums[col] = sums[col] + 0.11
          elif pp == 4: # passed with free squares, can be well defended
            sums[col] = sums[col] + 0.18 + 0.07 * (7 - steps)
            if steps < 3:
              sums[col] = sums[col] + 0.07 * (3 - steps)
            if steps < 2:
              sums[col] = sums[col] + 0.25
    # favor rooks at (half) open lines
    # while at it, favor rooks that can see each other
    # add the queen to that pool, too.
    for rookIx in rooks[col]:
      if not pa[rookIx & 7]:
        sums[col] = sums[col] + 0.03
      if not pawns[-col][rookIx & 7]:
        sums[col] = sums[col] + 0.03
      if board.attackmap[rookIx][col * rook]:
        sums[col] = sums[col] + 0.025
      if board.attackmap[rookIx][col * queen]:
        sums[col] = sums[col] + 0.01
      if not pa[rookIx & 7]:
        if rookIx == kingIx[-col] & 7:
          sums[col] = sums[col] + 0.02
        if queenIx[-col]:
          if board.IsDefended(rookIx):
            if rookIx == queenIx[-col] & 7:
              sums[col] = sums[col] + 0.01
            if rookIx == (kingIx[-col] & 7) and rookIx == (kingIx[-col] & 7):
              sums[col] = sums[col] + 0.06
        
  if (board.board[11] == pawn):
    sums[white] = sums[white] - 0.05;
    if (board.board[9] == pawn):
      sums[white] = sums[white] - 0.10;
  if (board.board[12] == pawn):
    sums[white] = sums[white] - 0.07;
    if (board.board[14] == pawn):
      sums[white] = sums[white] - 0.11;
  if (board.board[51] == -pawn):
    sums[black] = sums[black] - 0.03;
    if (board.board[49] == -pawn):
      sums[black] = sums[black] - 0.07;
  if (board.board[52] == -pawn):
    sums[black] = sums[black] - 0.07;
    if (board.board[54] == -pawn):
      sums[black] = sums[black] - 0.10;
  return sums

whiteOfficers = (knight, bishop, rook, queen, king)
blackOfficers = (-knight, -bishop, -rook, -queen, -king)
whitePieces = (pawn,) + whiteOfficers
blackPieces = (-pawn,) + blackOfficers
allPieces = whitePieces + blackPieces
pieceValues = [0, 1.0, 3.2, 3.4, 5.1, 9.6, 100.0, -100.0, -9.6, -5.1, -3.4, -3.2, -1.0]
officerValueSum = 0
for officer in whiteOfficers[:-1]:
  officerValueSum = officerValueSum + pieceValues[officer]

def GetSmallestWhite(attacks):
  for piece in whitePieces:
    if attacks[piece]:
      attacks[piece] = attacks[piece] - 1
      return piece
  return 0

def GetSmallestBlack(attacks):
  for piece in blackPieces:
    if attacks[piece]:
      attacks[piece] = attacks[piece] - 1
      return piece
  return 0

evalSingleSquareHash = {}

# for single square fight evaluation with removing the pieceAtPos 
# from defenders
# this is intended for simulated captures where one of the defender 
# is artificially moved to this location
def EvalSingleSquareRemoveDefender(pieceAtPos, attacks, turn):
  import copy
  if (pieceAtPos == 1 or pieceAtPos == -1):
    return EvalSingleSquare(pieceAtPos, attacks, turn, 0)
  else:
    attackcopy = copy.copy(attacks)
    attackcopy[pieceAtPos] = attackcopy[pieceAtPos] - 1
    if attackcopy[pieceAtPos] < 0:
      raise "attackcopy lower than 0"
    return EvalSingleSquare(pieceAtPos, attackcopy, turn, 0)

# returns 1.0 if black can capture whites pawn
def EvalSingleSquare(pieceAtPos, attacks, turn, forceFirstCapture,level=0):
  if pieceAtPos * turn > 0:
    return 0 # cannot hit that own piece anyway
  origattacks = tuple(attacks)
  global evalSingleSquareHash
  try:
    retval = evalSingleSquareHash[(pieceAtPos, origattacks, turn, forceFirstCapture)]
    return retval
  except KeyError:
    pass
  import copy
  attackcopy = copy.copy(attacks)
  if (turn < 0):
    hitter = GetSmallestBlack(attackcopy)
  else:
    hitter = GetSmallestWhite(attackcopy)  
  hitval = 0

  if abs(hitter) == pawn:
    hitval = hitval + turn * 0.1 # bad for the attacker

  if hitter:
    hitval = hitval + pieceValues[pieceAtPos]
    hitval = hitval + EvalSingleSquare(hitter, attackcopy, -turn, 0,level+1)
  if not forceFirstCapture and hitval * turn > 0: 
    # capturing is optional and not a good idea
    hitval = 0

  # retry - without pawns, because they are automatically considered to
  # ruin the position
  npattacks = copy.copy(attacks)
  if npattacks[turn * pawn]:
    npattacks[turn * pawn] = 0
    hitvalnopawns = EvalSingleSquare(pieceAtPos, npattacks, -turn, 0, level+1)
    if (hitvalnopawns * turn < hitval * turn):
      hitval = hitvalnopawns

  # retry - without the most immobile important piece (starting from knight)
  # for mobility test 
  if abs(hitval) < 0.5: # no need to capture, check mobility
    mobattack = copy.copy(attacks)
    mobilitypenalty = None
    for (piece,penalty) in ((knight, 0.2), (king,0.2), (queen, 0.07), (bishop,0.05), (rook,0.05)):
      p = -turn * piece
      if mobattack[p] > 0:
        mobattack[p] = mobattack[p] - 1
        mobilitypenalty = penalty
        break
    if mobilitypenalty:
      hitvalreduced = EvalSingleSquare(pieceAtPos, mobattack, turn, forceFirstCapture, level)
      if abs(hitvalreduced - hitval) >= 0.5: # reduced mobility
        hitval = hitval - turn * mobilitypenalty # good for the attacker

  evalSingleSquareHash[(pieceAtPos, origattacks, turn, forceFirstCapture)] = hitval

  return hitval

# evaluation function - a positive value is good for white
def Eval(board):
  board.evalIsCurrent = 1
  board.uncertainty = 0

  uncertainty = 0

  import copy
  import random

#  sum = 0
#  for pos in range(64):
#    sum = #    sum + pieceValues[board.board[pos]]
#  return sum

  t = board.turn
  if t > 0:
    best = min
    worst = max
  else:
    best = max
    worst = min

  kingIxBlack = board.kingIx[black]
  if kingIxBlack == None:
    return 1000.0
  kingIxWhite = board.kingIx[white]
  if kingIxWhite == None:
    return -1000.0
  b = board.board

  p_pawnstructure = 1
  p_activityknight = 1
  p_activitybishop = 1
  p_activityrook = 1
  p_activityqueen = 1
  p_attack = 1
  p_center = 1

  if hasattr(board, "personality"):
    p = board.personality
    p_pawnstructure = p.pawnstructure
    p_activityknight = p.activityknight
    p_activitybishop = p.activitybishop
    p_activityrook = p.activityrook
    p_activityqueen = p.activityqueen
    p_attack = p.attack
    p_center = p.center

  GenerateAttackMaps(board)
  sumking = 0 # random.random() * 0.05

  if (t < 0):
    kingIx = kingIxBlack
  else:
    kingIx = kingIxWhite

  evaluateMoveEffects = 1

  if board.IsAttacked(kingIx):
    attackers = CalculateKingAttackers(board, kingIx)
    canCapture = 0
    putBetween = 1
    if len(attackers) == 1: 
      if board.IsDefended(attackers[0][0]):
        canCapture = 1
      bestblock = 0
      for blockableSquare in attackers[0][1]:
        block = board.CanBlockACheck(blockableSquare)
        if block > bestblock:
          bestblock = block
      putBetween = bestblock
      uncertainty = uncertainty + 0.3
    else:
      putBetween = 0
    kingMoves = GenerateDestinationListForCheckedKing(board, kingIx)
  
    countKingMoves = len(kingMoves)

    if canCapture:
      i = attackers[0][0]
      amap = copy.copy(board.attackmap[i])
      val = EvalSingleSquare(b[i], board.attackmap[i], t, 1)
      if (putBetween == 2 or countKingMoves): 
        # has other possibilities than capturing
        val = best(val, 0)
        if val:
          evaluateMoveEffects = 0
      sumking = sumking - val
    else:
      if putBetween == 2: # blocks ok
        sumking = sumking - t * 0.1 # not that nice having to block a move
        uncertainty = uncertainty + 0.3
      elif putBetween == 1: # unsure block
        sumking = sumking - t * 2.0 # expect to lose a pawn or two
        uncertainty = uncertainty + 1
      else:
        if countKingMoves == 0:
          board.PopLockedAndAttackMaps()
          return -t * 998.0 # this is going to be a mate
        else:
          bestIx = None
          bestVal = -1
          for i in kingMoves:
            curpiece = abs(b[i]) 
            if curpiece > bestVal:
              bestVal = curpiece
              bestIx = i
          # temporarily move the king to safety and re-evaluate
          mode = Move.normal
          if bestVal:
            mode = Move.capture
          move = Move(kingIx, bestIx, mode)
          if not hasattr(board, "norecurineval"):
            board.norecurineval = 1
            board.Move(move)
            val = Eval(board)
            board.RetractMove()
            del board.norecurineval
            board.PopLockedAndAttackMaps()
            return val

  summ = 0

  matterw = 0
  matterb = 0
  for piece in whiteOfficers[0:-1]:
    mul = pieceValues[piece]
    matterw = matterw + b.count(piece) * mul
    matterb = matterb + b.count(-piece) * mul
  pawnsw = b.count(pawn)
  pawnsb = b.count(-pawn)

  endgame = 1.0 - (matterw + matterb) / (1.5 * officerValueSum);

  movevalues = (
    0, 0.015, p_activityknight*0.027, p_activitybishop*0.021, 
    p_activityrook * (0.002 + 0.015 * endgame), 
    p_activityqueen * (0.0008 + 0.02 * endgame), 
    0.0,
    0.0, 
    p_activityqueen * (0.0008 + 0.02 * endgame), 
    p_activityrook * (0.002 + 0.015 * endgame), 
    0.021 * p_activitybishop, 0.027 * p_activityknight, 0.015)

  attackratingsy = [0.3, 0.6, 0.9, 1.0, 1.3, 1.4, 1.45, 1.4]
  attackratingsx = [0.6, 0.9, 1.0, 1.2, 1.2, 1.0, 0.9, 0.6]

  for i in range(8):
    attackratingsy[i] = attackratingsy[i] ** p_attack
    attackratingsx[i] = attackratingsx[i] ** p_center

  for pos in range(64):
    y = pos / 8
    x = pos & 7
    aratew = attackratingsy[y] * attackratingsx[x]
    arateb = attackratingsy[7 - y] * attackratingsx[x]
    am = board.attackmap[pos]
    for p in whitePieces:
      summ = (summ + 
	am[p] * movevalues[p] * aratew -
        am[-p] * movevalues[-p] * arateb)

  maxhit = 0
  besthits = []
  besthitsopp = []
          
  sumss = 0
  for pos in range(64):
    am = board.attackmap[pos]

    if board.lockmap[pos]:
      sumss = sumss - b[pos] * 0.03

    if board.lockmapQueen[pos]:
      sumss = sumss - b[pos] * 0.02

    if b[pos] == 0: # evaluate a free square
      sse0 = EvalSingleSquare(-t*pawn, am, t, 0)
      sse1 = EvalSingleSquare(t*pawn, am, -t, 0)
      sumss = sumss - (sse0 + sse1) * 0.0025
      # and imaginary knight:
#      sse0 = EvalSingleSquare(-t*knight, am, t, 0)
#      sse1 = EvalSingleSquare(t*knight, am, -t, 0)
#      sumss = sumss - (sse0 + sse1) * 0.001

      for offi in (knight, bishop, rook, queen):
        if am[offi] >= 1:
          am[offi] = am[offi] - 1
          if EvalSingleSquare(offi, am, -1, 0) < 0.5:
            sumss = sumss + 0.007 * am[offi]
          am[offi] = am[offi] + 1

        if am[-offi] >= 1:
          am[-offi] = am[-offi] - 1
          if EvalSingleSquare(-offi, am, 1, 0) > -0.5:
            sumss = sumss - 0.007 * am[-offi]
          am[-offi] = am[-offi] + 1

    elif evaluateMoveEffects and b[pos] * t < 0: 
      # evaluate the possible captures
      sse = EvalSingleSquare(b[pos], am, t, 0)
      maxhit = best(maxhit, sse)
      sumss = sumss - 0.002 * sse
      if sse * t > 0:
        besthitsopp.append(sse)
        uncertainty = uncertainty + abs(0.1 * sse)
    elif evaluateMoveEffects and b[pos]: 
      sse = EvalSingleSquare(b[pos], am, -t, 0)
      sumss = sumss - 0.0015 * sse
      if sse * t > 0:
        besthitsopp.append(sse)
        uncertainty = uncertainty + abs(0.1 * sse)

  besthitsopp.sort()
  if t < 0:
    besthitsopp.reverse()
#  print "besthitsopp", besthitsopp, besthitsopp[-2]

  if len(besthitsopp) >= 2:
    sumss = sumss - 0.2 * besthitsopp[-2]
    uncertainty = uncertainty + abs(0.4 * besthitsopp[-2])

  for i in besthitsopp[:-1]: # expect that the opponent can protect from the best capture
    sumss = sumss - 0.1 * i
    uncertainty = uncertainty + abs(0.3 * i)

#  if maxhit:
    
  sumss = sumss - maxhit * 0.93

  pawnsums = PawnStructure(board) 
  pawnsums[black] = pawnsums[black] * p_pawnstructure
  pawnsums[white] = pawnsums[white] * p_pawnstructure

  sumps = pawnsums[white] - pawnsums[black]
  sumkp = 0
  for (color,matter,kingrow,favoredPawnRow,ownPieces) in (
       (-1, matterw, 7, 6, blackPieces), 
       (1, matterb, 0, 1, whitePieces)):
    frees = []
    
    kingix = board.kingIx[color]
    kingenv = kingMovesBoardLookup[kingix]
    for pos in kingenv:
      attack = board.attackmap[pos]
      kingattackvalues = (0,0.001,0.025,0.03,0.03,0.02,-0.001,
                          0.001, -0.02, -0.03, -0.03, -0.025, -0.001)
      for ix in ownPieces:
        if ix * color < 0:
          sumkp = sumkp + attack[ix] * kingattackvalues[ix]
          uncertainty = uncertainty + abs(attack[ix] * kingattackvalues[ix])

    if (kingix / 8 == kingrow):
      kingx = kingix & 7
      kingximportance = [0.04,0.16,0.10,0.0,0.0,0.05,0.16,0.05]
      pawnwall = [[0.01,0.02,0.02,0.0,0.0,0.05,0.034,0.025],
                  [0.009,0.01,0.005,0.0,0.0,0.005,0.015,0.024]]
      sumkp = sumkp + color * kingximportance[kingx]
      startx = max(kingx - 1, 0)
      endx = min(kingx + 2, 8)
      for (row,rowid) in ((favoredPawnRow,0),(favoredPawnRow + color * 8,1)):
        for x in range(startx, endx):
          ix = row + x
          if b[ix] == color * pawn: # king safety
            sumkp = sumkp + color * pawnwall[rowid][x] * (matter) / 40.0
          if b[ix] == -color * pawn: # king unsafety
            sumkp = sumkp - 0.1 * color * pawnwall[rowid][x] * (matter) / 40.0

  if CanKingBeChecked(board, t): # there could be a check in two moves
    sumkp = sumkp - t * 0.10
    uncertainty += 0.1

  if CanKingBeChecked(board, -t): # next move can be a check
    sumkp = sumkp + t * 0.23
    uncertainty += 0.3

  if not board.castlingWhiteKing and b[8+5] == pawn and (b[8+6] == pawn or b[16 + 6] == pawn):
    sumkp = sumkp + 0.035
    if b[5] == 0:
      sumkp = sumkp + 0.035
    if b[6] == 0:
      sumkp = sumkp + 0.035
  if not board.castlingWhiteQueen and b[8+1] == pawn and b[8+2] == pawn:
    sumkp = sumkp + 0.01
    if b[1] == 0:
      sumkp = sumkp + 0.025
    if b[2] == 0:
      sumkp = sumkp + 0.025
    if b[3] == 0:
      sumkp = sumkp + 0.015
  if not board.castlingBlackKing and b[48 + 5] == -pawn and (b[48 + 6] == -pawn or b[40 + 6] == -pawn):
    sumkp = sumkp - 0.035
    if b[56 + 5] == 0:
      sumkp = sumkp - 0.035
    if b[56 + 6] == 0:
      sumkp = sumkp - 0.035
  if not board.castlingBlackQueen and b[48 + 1] == -pawn and b[48 + 2] == -pawn:
    sumkp = sumkp - 0.01
    if b[56 + 1] == 0:
      sumkp = sumkp - 0.025
    if b[56 + 2] == 0:
      sumkp = sumkp - 0.025
    if b[56 + 3] == 0:
      sumkp = sumkp - 0.015

  sumqp = 0
  if CanQueenBeAttacked(board, t):
    sumqp = sumqp - t * 0.10
    uncertainty += 0.07

  if CanQueenBeAttacked(board, -t):
    sumqp = sumqp + t * 0.15
    uncertainty += 0.1

  sumkm = 0

  limit = 0.3
  wkm = None
  bkm = None
  # king mobility is more important for the party with less matter
  if matterb < officerValueSum * limit:
    GenerateKingStepsMap(board, white)
    wkm = EvalKingMobility(board, white)
    bIsWinning = (pi + atan(matterb - matterw) * 2) / pi
    sumkm = sumkm + 0.2 * bIsWinning * (officerValueSum * limit - matterb) * wkm

  if matterw < officerValueSum * limit:
    GenerateKingStepsMap(board, black)
    bkm = EvalKingMobility(board, black)
    wIsWinning = (pi + atan(matterw - matterb) * 2) / pi
    sumkm = sumkm - 0.2 * wIsWinning * (officerValueSum * limit - matterw) * bkm

  if wkm and bkm:
    mb = board.kingMobility[black]
    mw = board.kingMobility[white]
    for i in range(64):
      wval = mw[i]
      bval = mb[i]
      if wval >= 0:
        if bval < 0 or bval > wval:
          sumkm = sumkm + 0.003
      elif bval >= 0:
        if wval < 0 or wval > bval:
          sumkm = sumkm - 0.003
      if wval >= 0 and wval == bval:
        sumkm = sumkm + 0.002 * t

  totb = matterb + pawnsb
  totw = matterw + pawnsw

  global centerMap
  sumc = 0
  for i in range(64):
    if b[i] == queen:
      sumc = sumc - centerMap[i] * 0.08 * (matterb / officerValueSum)
    if b[i] == rook:
      sumc = sumc - centerMap[i] * 0.04 * (matterb / officerValueSum)
    if b[i] == -queen:
      sumc = sumc + centerMap[i] * 0.08 * (matterw / officerValueSum)
    if b[i] == -rook:
      sumc = sumc + centerMap[i] * 0.04 * (matterw / officerValueSum)

  if totw == 0:
    # king should be in the center
    x = kingIxWhite & 7
    y = kingIxWhite / 8
    sumkm = sumkm + 0.3 * ((2.5 - ((y - 3.5) ** 2 + (x - 3.5) ** 2) ** 0.5) / 2.5)
    sumkm = sumkm + 0.1 * (min(abs(x - 3.5), abs(y - 3.5)) - 2.5)
  
    oppx = kingIxBlack & 7
    oppy = kingIxBlack / 8
    dx = abs(oppx - x)
    dy = abs(oppy - y)
    sumkm = sumkm - 0.03 * ((3 - (dx ** 2 + dy ** 2) ** 0.5) / 2)
    if (dy == 2 and dx < 2) or (dx == 2 and dy < 2):
      sumkm = sumkm - 0.15

  if totb == 0:
    # king should be in the center
    x = kingIxBlack & 7
    y = kingIxBlack / 8
    sumkm = sumkm - 0.3 * ((2.5 - ((y - 3.5) ** 2 + (x - 3.5) ** 2) ** 0.5) / 2.5)
    sumkm = sumkm - 0.1 * (min(abs(x - 3.5), abs(y - 3.5)) - 2.5)

    oppx = kingIxWhite & 7
    oppy = kingIxWhite / 8
    dx = abs(oppx - x)
    dy = abs(oppy - y)
    sumkm = sumkm + 0.03 * ((3 - (dx ** 2 + dy ** 2) ** 0.5) / 2)
    if (dy == 2 and dx < 2) or (dx == 2 and dy < 2):
      sumkm = sumkm + 0.15

  sim = 0
  if (board.moveCount > 4):
    m0 = board.moveHistory[-1]
    m1 = board.moveHistory[-3]
    if m0.fromIx == m1.toIx: # -t needed to move the same piece twice
      sim = sim + 0.05 * t

    m0 = board.moveHistory[-2]
    m1 = board.moveHistory[-4]
    if m0.fromIx == m1.toIx: # t needed to move the same piece twice
      sim = sim - 0.05 * t

    # last moved officer now in danger, loses some tempo
    if t * EvalSingleSquare(b[m1.toIx], board.attackmap[m1.toIx], t, 0) < 1.5:
      sim = sim - 0.12 * t

  if (board.moveCount < 40):
    # get the king and queen pawns moving
    # white
    if b[12] == pawn:
      sim = sim - 0.1
      if b[20] != 0:
        sim = sim - 0.1
    if b[11] == pawn:
      sim = sim - 0.1
      if b[19] != 0:
        sim = sim - 0.1
    # black
    if b[52] == -pawn:
      sim = sim + 0.1
      if b[44] != 0:
        sim = sim + 0.1
    if b[51] == -pawn:
      sim = sim + 0.1
      if b[43] != 0:
        sim = sim + 0.1

    if b[34] == -pawn: # sicilian
      if b[44] == -pawn: # e6, promote e7-e6
        sim = sim - 0.07

    # get the light officers moving
    itbl = [0, 0, -0.2, -0.165, 0.01, 0.05, 0.15, 
               0.15, 0.05, 0.01, -0.165, -0.2, 0]
    for i in range(8):
      sim = sim + itbl[b[i]] - itbl[b[56 + i]]
    frac = (40 - board.moveCount) / 20.0
    if frac > 1.0:
      frac = 1.0
    sim = sim * frac

# summ = movements
# sumking = king check
# sumss = eval single square
# sumps = pawnstructure
# sumkp = king position
# sumkm = king movement
# sumqp = queen can be attacked
# sim = calculate non-developed officers
# sumc = center avoidance for rooks and queens

  sum = (summ + sumking + sumss + sumps + sumkp + 
	 sumkm + sumqp + sim + sumc + board.castlingBonus)
  retval = ((officerValueSum * 3) * (matterw - matterb + sum) / 
            (min(matterw, matterb) + officerValueSum * 2))

  if 0:
    print "summ = movements", summ
    print "sumking = king check", sumking
    print "sumss = eval single square", sumss
    print "sumps = pawnstructure", sumps
    print "sumkp = king position", sumkp
    print "sumkm = king movement", sumkm
    print "sumqp = queen position", sumqp
    print "pawns", pawnsw - pawnsb
    print "officerValueSum", officerValueSum
    print "matters", matterw, matterb

  retval = retval + pawnsw - pawnsb

  board.PopLockedAndAttackMaps()
  board.uncertainty = uncertainty
  return retval

## hash mechanism

class HashTable:
  def Init(m):
    m.hash = {}
    m.hashCount = 0
    m.evals = 0
    m.collisions = 0
    m.hashkeyfifo = []
    m.limit = 10000
  def Add(m, board, eval):
    import copy
    copyboard = Board()
    copyboard.LightPositionCopyFrom(board)
    ihash = hash(board)
#    if m.hash.has_key(ihash):
#      m.collisions = m.collisions + 1
#      print "new collision", ihash, "\n\n"
#      print hash(tuple(board.board))
#      PrintBoard(board)
#
#      print "---------------------------------"
#      oldboard = Board()
#      oldboard.LightPositionCopyFrom(m.hash[ihash][0])
#      print hash(tuple(oldboard.board))
#      PrintBoard(oldboard)
#      print "================================="

    m.hash[ihash] = [copyboard, eval, m.hashCount, board.uncertainty]
    m.hashkeyfifo.append(hash(board))
    if (len(m.hashkeyfifo) > m.limit):
      deletekeys = max(m.limit / 10, 1)
      print "deleting keys", deletekeys, "of", len(m.hashkeyfifo)
      for i in range(deletekeys):
        try:
          del m.hash[m.hashkeyfifo[i]]
        except KeyError:
          pass # the element in the hash table was already overridden 
               # (and deleted by this same mechanism)
      del m.hashkeyfifo[0:deletekeys]
      try:
        import gc
        val = gc.collect()
        print "GC Collect", val
      except ImportError:
        print "import gc failed"
    m.evals = m.evals + 1
  def Get(m, board):
    v = m.GetSeq(board)
    if v:
      return (v[1], v[3])
    return (None, None)
  def GetBoard(m, board):
    v = m.GetSeq(board)
    if v:
      return v[0]
  def GetSeq(m, board):
    try:
      hkey = hash(board)
      v = m.hash[hkey] # (board, eval, count, board.uncertainty)
      v[2] = m.hashCount
      if (v[0].Equal(board)) and v[0].evalDepth >= board.evalDepth:
        m.hashCount = m.hashCount + 1
        return v
      else:
        pass
    except KeyError:
      pass
    return None
  
  def Clean():
    pass

## search

def OrderSimple(board, moves):
  postable = (0, 0.01, 0.02, 0.03, 0.03, 0.02, 0.01, 0)
  import copy
  b = board.board
  t = board.turn
  retmoves = []
  bk = board.killermoves[t]
  for move in moves:
    val = None
    for ix in range(len(bk)):
      v = bk[ix][0]
      mv = bk[ix][1]
      if mv.fromIx == move.fromIx and mv.toIx == move.toIx:
        val = 0.4 * v
    if val == None:
      toIx = move.toIx
      fromIx = move.fromIx
      cur = b[fromIx]
      val = abs(pieceValues[b[toIx]]) # eats it
      amto = board.attackmap[toIx]
      amfrom = board.attackmap[fromIx]
      if abs(cur) != pawn:
        if abs(cur) < rook:
          val = val - 0.01
        amto = copy.deepcopy(board.attackmap[toIx])
        amto[cur] = amto[cur] - 1
      val = val + abs(EvalSingleSquare(cur, amto, -t, 0))
      val = val - abs(EvalSingleSquare(cur, amfrom, -t, 0))
      val = val - postable[toIx & 7] + postable[toIx / 8] * 0.1
      val = val + postable[fromIx & 7] + postable[fromIx / 8] * 0.1
      if move.mode == move.capture:
        val = val + 0.1
    retmoves.append((val, move))
  retmoves.sort()
  retval = []
  for (val, move) in retmoves:
    retval.append(move)
  return retval
  
def PrintSearchMoves(board, bestVal):
  print ':::', 
  for i in range(board.searchStartLevel, board.moveCount):
    print "%s," % board.moveHistory[i], 
  print ':', bestVal
  
def RecordKillerMovesForMoveSorting(board, movelist):
  baseline = -Eval(board) * board.turn
  GenerateAttackMaps(board)
  a = []

#  print "baseline", baseline
#  print "KILLER PRE", movelist
  for i in movelist:
    if i[0] != None:
      a.append((i[0] - baseline, i[1], i[2]))
  board.killermoves[board.turn] = a
#  print "KILLER POST", a

def PrepareKillerMovesForMoveSorting(board, callback):
  moves = GenerateAllLegalMoves(board) # fake
  board.Move(Move(None,None,Move.normal)) # null move, change turn
  moves = GenerateAllLegalMoves(board) # fake
  baseline = -Eval(board) * board.turn
  GenerateAttackMaps(board)
  nhash = HashTable()
  nhash.Init()
  nmlist = []
  cdepth = 1
  (bestVal, bestmove, history) = \
     ABnegaSearchZW(board, nhash, -1e10, 1e10, nmlist, cdepth, callback)
  board.RetractMove() # retract null move
  print "baseline", baseline
  print "KILLER PRE", nmlist

  if nmlist and nmlist[0][0]:
    for ix in range(len(nmlist)):
      if (nmlist[ix][0] != None):
        nmlist[ix][0] = nmlist[ix][0] - baseline
  else:
    nmlist = []

  board.killermoves[-board.turn] = nmlist
  board.killermoves[board.turn] = []

  print "KILLER POST", nmlist  

def ABnegaSearchZWTail(board, hashtbl, alpha, beta, movelist, level, movelevel, callback):
  reps = board.CountRepetitions()
  if reps >= 3:
    return (0, "3 repetitions", [None])
  epsilon = 0.03
  bestVal = None
  bestMove = None
  bestHistory = [] # no history here
  if level < 0.5:                   # leaf position: static evaluation
    (bestVal, uncertainty) = hashtbl.Get(board)
    if not bestVal:
      if board.evalDepth:
        edepth = board.evalDepth
        board.evalDepth = 0
        nhashtbl = HashTable()
        nhashtbl.Init()
        for cdepth in range(1, edepth + 1):
          nmlist = []
          (bestVal, bestmove, history) = \
            ABnegaSearchZWTail(board, nhashtbl, -1e10, 1e10, nmlist, cdepth, cdepth, callback)
        board.evalDepth = edepth
      else:
        bestVal = Eval(board) * board.turn    # from current player's side
      hashtbl.Add(board, bestVal)
    if callback():
      return (None, None, [None])
  else:
    kingix = board.kingIx[board.turn]
    kingixOpp = board.kingIx[-board.turn]
    if kingix == None:
      retval = (-100000 + level, "mate", [None])
      return retval
    if kingixOpp == None:
      retval = (-100000 + level, "mate", [None])
      return retval
    moves = GenerateAllLegalMoves(board) # generate successor moves
    moves = OrderSimple(board, moves)
    if (len(moves) == 1 and 
        board.searchStartLevel == board.moveCount and 
        not board.pondering):
      return (0.0, moves[0], "not evaluated")

    movesorder = []
    if len(movelist) == len(moves):
      moves = []
    if len(movelist):
      # take moves from movelist
      for i in movelist:
        movesorder.append(i[1])
    for m in moves:
      if not m in movesorder:
        movesorder.append(m)
    moves = movesorder

#    if board.searchStartLevel == board.moveCount:
#      print "MOVES", moves
#      print "ML", movelist

    if len (moves) == 0: # no moves, mate or stalemate!
      if board.IsAttacked(kingix): # mate
        prevmove = board.moveHistory[-1]
        matingPieceType = abs(board.board[prevmove.toIx]) 
        # play fancy, try to mate with a pawn or knight rather than queen
        retval = (-(10000 + movelevel * 100 - matingPieceType), "mate", [None])
        return retval
      else:
        return (0.0, "stalemate", [None])

    try:
      prevmove = board.moveHistory[-1]
    except IndexError:
      prevmove = None

    for moveix in range(len(moves)):
      move = moves[moveix]
      if board.searchStartLevel == board.moveCount:
        board.progressEstimate = float(moveix) / len(moves)
      if (alpha >= beta):
        break
#      print "ABBA moving", move
      board.Move(move)
      newmove = [None, move, []]
      movefound = 0
      for m in movelist:
        if m[1] == move:
          movefound = 1
          newmove = m
      if not movefound:
        movelist.append(newmove)

      # search with zero window
      nextlevel = level - 1

      if not board.evalIsCurrent:
        (bestVal, uncertainty) = hashtbl.Get(board)
        if bestVal == None:
#          print "kumpu", hash(board)
          val = Eval(board) * board.turn # re-eval for uncertainty values
          hashtbl.Add(board, val)
        else:
#          print "kampu", hash(board)
          board.uncertainty = uncertainty

#      leveldrop = (0.5 * pi - atan(board.uncertainty)) / (0.5 * pi)
#      leveldrop = max(0.25, leveldrop)
#      leveldrop = min(1.0, leveldrop)
#      if moveix == 0:
#        leveldrop = leveldrop - 0.6
#      leveldrop = leveldrop - 0.4 * moveix / len(moves) + 0.4
#      leveldrop = max(0.25, leveldrop)
#      leveldrop = min(1.0, leveldrop)
#      if moveix >= 3:
#        leveldrop = 1.0
#      print "droppi", leveldrop
#      nextlevel = level - leveldrop

#      leveldrop = 1.0

      if board.searchStartLevel == board.moveCount - 1 and moveix == 0:
        print "firsti", move
        nextlevel = level

#      if board.searchStartLevel == board.moveCount - 2 and moveix == 0:
#        print "secondi", move
#        nextlevel = level

#      if move.mode == move.capture:
#        nextlevel = level - 0.75

#      if IsKingChecked(board, board.turn):
#        nextlevel = level - 0.51
#
#      if len(moves) == 1:
#        nextlevel = level - 0.25
#      elif len(moves) == 2:
#        nextlevel = level - 0.51
#      elif len(moves) == 3:
#        nextlevel = level - 0.75


#      if (prevmove and prevmove.mode == prevmove.capture and 
#	  prevmove.toIx == move.toIx):
#        nextlevel = level - 0.49

      (succVal, reply, history) = ABnegaSearchZWTail(board, hashtbl, -(alpha+epsilon), -alpha, newmove[2], nextlevel, movelevel - 1, callback)
      if (succVal == None):
        return (None, None, [None])

      succVal = -succVal
      if succVal > alpha:
        # alpha value is improved by this move, search again
        (succVal, reply, history) = ABnegaSearchZWTail(board, hashtbl, -beta, -alpha, newmove[2], nextlevel, movelevel - 1, callback)
        if (succVal == None):
          return (None, None, [None])
        succVal = -succVal

      newmove[0] = -succVal # (alpha + beta) * 0.5

      board.RetractMove()
#      print "ABBA retracting", move
      # update alpha and move, if better
      if succVal > alpha:
        alpha    = succVal
        bestMove = move
        bestHistory = history
      bestVal = alpha
      newmove[2].sort()

  movelist.sort()

  assert bestVal != None
  return (bestVal, bestMove,[bestMove]+bestHistory)

def ABnegaSearchZW(board, hashtbl, alpha, beta, movelist, level, callback):
  board.progressEstimate = 0.0
  callback() # call the callback at least once per call
  if board.useOpeningLib and not board.pondering:
    from openinglibrary import nextmove
    librarymovelist = nextmove(board.moveHistory)
    if librarymovelist:
      librarymove = librarymovelist[0]
      print "library move", librarymove
      try:
        return (0.0, StringToMove(board, librarymove), ["opening library"])
      except ValueError, a:
        print a, "error in the opening library"
        print "library move", librarymove
        raise ValueError, (a, "error in the opening library")
  board.searchStartLevel = board.moveCount
  val = ABnegaSearchZWTail(board, hashtbl, alpha, beta, movelist, level, level, callback)
  board.progressEstimate = None

  if (callback()):
    return (None, None, [None]) # this run was stopped
  return val


##################################### test code begins somewhere here

letterToPiece = {
" ":0,
".":0,
"p":-pawn,"n":-knight,"b":-bishop,"r":-rook,"q":-queen,"k":-king,
"P":pawn,"N":knight,"B":bishop,"R":rook,"Q":queen,"K":king
}

def PrintBoard(board):
  if 1:
    for i in range(7,-1,-1):
      str = '"'
      for j in range(8):
        str = str + ".PNBRQKkqrbnp"[board.board[i * 8 + j]]
      str = str + '"'
      print str
  rowheader0 = "+----" * 8 + "+"
  rowheader1 = "|    " * 8 + "|"
  for i in range(7,-1,-1):
    print rowheader0
    print rowheader1
    for j in range(8):
      ix = i * 8 + j
      print "| %c%c" % (" WWWWWWBBBBBB"[board.board[ix]], pieceSymbols[board.board[ix]]),
    print "|"
    print rowheader1
  print rowheader0
  print "turn", board.turn
  print "castlings", board.CastlingTuple()
  print "enpassant", board.enpassant
  print "movesWithOutHittingOrMovingPawns", board.movesWithOutHittingOrMovingPawns

def PrintBoardDebug(board):
  rowheader0 = "+--------" * 8 + "+"
  for i in range(7,-1,-1):
    print rowheader0
    for j in range(8):
      ix = i * 8 + j
      print "|  %c%c   " % (" WWWWWWBBBBBB"[board.board[ix]], pieceSymbols[board.board[ix]]),
    print "|"
    for j in range(8):
      ix = i * 8 + j
      amap = board.attackmap[ix]
      print "|W%d%d%d%d%d%d" % (amap[pawn], amap[knight], amap[bishop], amap[rook], amap[queen], amap[king]),
    print "|"
    for j in range(8):
      ix = i * 8 + j
      amap = board.attackmap[ix]
      print "|B%d%d%d%d%d%d" % (amap[-pawn], amap[-knight], amap[-bishop], amap[-rook], amap[-queen], amap[-king]),
    print "|"
    for j in range(8):
      ix = i * 8 + j
      w = None
      b = None
      if board.kingMobility[white]:
        w = board.kingMobility[white][ix]
      if board.kingMobility[black]:
        b = board.kingMobility[black][ix]
      maptosingleletter = {None: " ", -1: "o", -2: "A"}
      try:
        w = maptosingleletter[w]
      except KeyError:
        pass
      try:
        b = maptosingleletter[b]
      except KeyError:
        pass
      print "|%d%d  %s%s " % (board.attackmapFromLocked[ix][1], board.attackmapFromLocked[ix][-1], w, b),

    print "|"
    for j in range(8):
      ix = i * 8 + j
      v = board.lockmap[ix]
      if (v == None):
        v = 0
      print "|Lock=%d " % v,
    print "|"
  print rowheader0
  print "turn", board.turn
  print "castlings", board.CastlingTuple()
  print "enpassant", board.enpassant
  print "movesWithOutHittingOrMovingPawns", board.movesWithOutHittingOrMovingPawns
  print "last moves", board.movesForPlayerInTurn[-1]

def AssertSetsAreEqual(l0, l1):
  for e0 in l0:
    if not e0 in l1:
      raise AssertionError, str(e0) + " not in " + str(l1)
  for e1 in l1:
    if not e1 in l0:
      raise AssertionError, str(e1) + " not in " + str(l0)

def StringToBoard(str, turn):
#  print "--------------------------------------------------------"
  board = Board()
  board.Setup()
  for i in range(64):
    board.board[i] = letterToPiece[str[(7 - (i / 8)) * 8 + (i & 7)]]
  if board.board[0] != rook or board.board[4] != king:
    board.castlingWhiteQueen = 1
  if board.board[7] != rook or board.board[4] != king:
    board.castlingWhiteKing = 1

  if board.board[56 + 0] != -rook or board.board[56 + 4] != -king:
    board.castlingBlackQueen = 1
  if board.board[56 + 7] != -rook or board.board[56 + 4] != -king:
    board.castlingBlackKing = 1

  board.turn = -turn
  board.UpdateKingAndQueenIndex()
  GenerateAllLegalMoves(board)

# caching the generated moves etc. requires that there is a move history,
# so we kluge one move here... a truely ugly solution, but runs.
  piece = board.board[0]
  print "store", piece
  board.useOpeningLib = 0
  board.Move(Move(None,None,Move.normal)) 
#  board.turn = -board.turn # the null move didn't change the turn
  board.board[0] = piece
  board.UpdateKingAndQueenIndex()
  print "ret", piece

  GenerateAllLegalMoves(board)

# kluge ends

  return board

def AssertLegalMovesFrom(board, expectedlegalmoves):
  legalmoves = GenerateAllLegalMoves(board)
  legalstrmoves = []
  for move in legalmoves:
    legalstrmoves.append(repr(move))
  try:
    AssertSetsAreEqual(legalstrmoves, expectedlegalmoves)
  except AssertionError, attr:
    PrintBoard(board)
    print "expected moves:"
    print expectedlegalmoves
    print "generated moves:"
    print legalstrmoves
    raise AssertionError, attr

def _testsetup():
  board = Board()
  board.Setup()
  AssertLegalMovesFrom(board, 
    ("a2-a3", "a2-a4",
     "b2-b3", "b2-b4",
     "c2-c3", "c2-c4",
     "d2-d3", "d2-d4",
     "e2-e3", "e2-e4",
     "f2-f3", "f2-f4",
     "g2-g3", "g2-g4",
     "h2-h3", "h2-h4",
     "b1-a3", "b1-c3",
     "g1-f3", "g1-h3"))

def _testretractenpassant():
  board = StringToBoard(
"rnb.kbnr"
"pp...ppp"
"..p..q.."
"........"
"...Np..."
"..NB...."
"PPPP.PPP"
"R.BQK..R", white)
  board.Move(StringToMove(board, "f2-f4"))
  move = StringToMove(board, "e4xf3")
  board.Move(move)
  print move
  print dir(move)
  for i in dir(move):
    print getattr(move, i)

  board.RetractMove()
  print dir(move)
  for i in dir(move):
    print getattr(move, i)
  assert board.board[3*8 + 5] == pawn

def _testking():
  board = StringToBoard(
    ".......k"
    "........"
    "........"
    "........"
    "........"
    "........"
    "........"
    "Kn......", 
    white)
  print "board", board.board[0]
  print "board", board.board[63]
  AssertLegalMovesFrom(board, ("a1-a2", "a1-b2", "a1xb1"))

def _testpawn0():
  board = StringToBoard(
    "........"
    "........"
    "........"
    ".p......"
    "p......."
    "p.p....k"
    ".P....nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ("b2xa3", "b2xc3", "b2-b3", "b2-b4"))

def _testpawn1():
  board = StringToBoard(
    "........"
    "........"
    "........"
    ".p......"
    "pP......"
    "p.p....k"
    ".P....nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ("b2xa3", "b2xc3", "b2-b3"))

def _testpawn2():
  board = StringToBoard(
    "........"
    ".....p.."
    ".....P.."
    ".p......"
    ".P......"
    "pP.....k"
    ".P....nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ("b2xa3",))

def _testpawn2():
  board = StringToBoard(
    "........"
    ".....p.."
    ".....P.."
    ".p......"
    ".P......"
    "pP.....k"
    ".P....nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ("b2xa3",))

def _testpawnpromotion():
  board = StringToBoard(
    "..b....."
    "...P...."
    "........"
    "........"
    "........"
    ".......k"
    "......nb"
    "......nK", 
    white)
  AssertLegalMovesFrom(board, ("d7-d8N", "d7-d8B", "d7-d8R", "d7-d8Q", 
    "d7xc8N", "d7xc8B", "d7xc8R", "d7xc8Q"))

def _testpawnenpassant():
  board = StringToBoard(
    "........"
    "...p...."
    "........"
    ".pP.Pp.."
    "........"
    ".......k"
    "......nb"
    "......nK", 
    black)
  board.Move(StringToMove(board, "d7-d5"))
  AssertLegalMovesFrom(board, ("c5-c6", "c5xd6", "e5-e6", "e5xd6"))

def _testcastlingKingside0():
  board = StringToBoard(
    "rn..k..r"
    "p...p..p"
    "p...P..p"
    "P......P"
    "........"
    "........"
    "........"
    ".......K", 
    black)
  AssertLegalMovesFrom(board, ("e8-d8", "e8-f8", "O-O", "h8-g8", "h8-f8",
                               "b8-d7", "b8-c6"))

def _testcastlingKingside1():
  board = StringToBoard(
    ".r..k..r"
    "p...p..p"
    "p...P..p"
    "P......P"
    "........"
    "........"
    "........"
    ".......K", 
    white)
  board.Move(StringToMove(board, "h1-h2"))
  board.Move(StringToMove(board, "b8-a8"))
  board.Move(StringToMove(board, "h2-h1"))
  AssertLegalMovesFrom(board, ("e8-d8", "e8-f8", "O-O", "h8-g8", "h8-f8",
                               "a8-b8", "a8-c8", "a8-d8"))

def _testcastlingKingside2():
  board = StringToBoard(
    "r...k..r"
    "p...p..p"
    "p...P..p"
    "P...B..P"
    "........"
    "........"
    "........"
    "...R...K", 
    black)
  AssertLegalMovesFrom(board, ("e8-f8", "O-O", "h8-g8", "h8-f8",
                               "a8-b8", "a8-c8", "a8-d8"))

def _testcastlingNone():
  board = StringToBoard(
    "r...k..r"
    "pP..p..P"
    "p...P..p"
    "P...B..P"
    "........"
    "........"
    "........"
    ".......K", 
    black)
  AssertLegalMovesFrom(board, ("e8-d8", "e8-f8", "h8-g8", "h8-f8",
                               "a8-b8", "a8-c8", "a8-d8", "h8xh7"))


def _testcastlingQueenside0():
  board = StringToBoard(
    "r...k..."
    "p...p..."
    "p...P..."
    "P......."
    "........"
    "........"
    "........"
    ".......K", 
    black)
  AssertLegalMovesFrom(board, ("e8-d8", "e8-f8", "O-O-O",
                               "a8-b8", "a8-c8", "a8-d8"))

def _testnomoves():
  board = StringToBoard(
    "........"
    ".....p.."
    ".....P.."
    ".p......"
    ".P.p...."
    ".P.P...k"
    ".P.P..nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ())


def _testknight():
  board = StringToBoard(
    "........"
    ".....p.."
    ".....P.."
    ".p......"
    "p..p...."
    "...P...k"
    ".N.P..nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ("b2xa4", "b2-c4", "b2-d1"))


def _testrook():
  board = StringToBoard(
    "........"
    ".....p.."
    ".....P.."
    ".p......"
    "........"
    "...p...k"
    ".R.P..nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ("b2-b1", "b2-b3", "b2-b4", "b2xb5", "b2-a2", 
    "b2-c2"))

def _testbishop():
  board = StringToBoard(
    "........"
    ".....p.."
    ".....P.."
    ".p......"
    "........"
    "...p...k"
    ".B.P..nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ("b2-a3", "b2-a1","b2xc1","b2-c3","b2-d4","b2-e5"))


def _testqueen():
  board = StringToBoard(
    "........"
    ".....p.."
    ".....P.."
    ".p......"
    "........"
    "...p...k"
    ".Q.P..nb"
    "..q...nK", 
    white)
  AssertLegalMovesFrom(board, ("b2-b1", "b2-b3", "b2-b4", "b2xb5", "b2-a2", 
    "b2-c2", "b2-a3", "b2-a1","b2xc1","b2-c3","b2-d4","b2-e5")
  )


def _testkingchecked0():
  board = StringToBoard(
    "........"
    ".....p.."
    ".....P.."
    ".p......"
    "........"
    "...p...k"
    ".R.P..nb"
    "..q...K.", 
    white)
  if not IsKingChecked(board,white):
    raise AssertionError, "king check"
  if IsKingChecked(board,black):
    raise AssertionError, "king check"

def _testkingchecked2():
  board = StringToBoard(
    "r..R...."
    "ppp  p p"
    "  n   rk"
    "......q."
    ".......Q"
    "..P....."
    "P.P..P.P"
    "....K.NR", black)
  checker = IsKingChecked(board,white)
  if checker:
    raise AssertionError, "white king check", checker
  checker = IsKingChecked(board,black)
  if not checker:
    raise AssertionError, "black king check"
  print GenerateAllLegalMoves(board)

def _testkingchecked3():
  board = StringToBoard(
    "rk.r.Q.."
    "ppp....p"
    ".....p.."
    "........"
    ".....P.."
    "..P....."
    "P.....QP"
    "....K.NR", black)
  checker = IsKingChecked(board,white)
  if checker:
    raise AssertionError, "white king check", checker
  checker = IsKingChecked(board,black)
  if checker:
    raise AssertionError, "black king check"
  print GenerateAllLegalMoves(board)
  rookIx = 7 * 8 + 3
  print "lock", board.lockmap[rookIx]

def _testkingchecked1():
  board = StringToBoard(
    "rn.....r"
    "p..kp..p"
    "p...P..p"
    "P......P"
    "........"
    "........"
    "........"
    ".......K", 
    white)
  checker = IsKingChecked(board,white)
  if checker:
    raise AssertionError, "white king check", checker
  checker = IsKingChecked(board,black)
  if not checker:
    raise AssertionError, "black king check"

def StringToMove(board, movestr):
  moves = GenerateAllLegalMoves(board)
  movefound = None
  for m in moves:
    if repr(m) == movestr:
      movefound = m
      break
  if not movefound:
    raise ValueError, ("could not find %s in %s" % (movestr, moves))
  return movefound

def alphabetacallback(*kw):
  print "alpha beta callback", kw

def _testBeginning2():
  board = Board()
  board.Setup()
  moves = ("e2-e4", "d7-d5", "b1-c3", "g8-f6", "e4-e5", "d5-d4", "e5xf6",
"d4xc3", "f6xg7", "c3xd2")
  for move in moves:
    board.Move(StringToMove(board, move))
  PrintBoard(board)
  board.Move(StringToMove(board, "c1xd2"))
  PrintBoard(board)

def PrintMovelist(movelist,depth=0):
  if movelist == []:
    return
  for m in movelist:
#    print "  " * depth, "HH", m
    print "  " * depth, m[0], m[1]
    PrintMovelist(m[2], depth + 1)

def _testBeginning():
  board = Board()
  board.Setup()
#  moves = ("e2-e4", "e7-e5", "d2-d4", "e5xd4", "d1xd4", "b8-c6", "d4-d5", "f8-d6")
#  for move in moves:
#    board.Move(StringToMove(board, move))
  print "legal moves"
  print GenerateAllLegalMoves(board)
  print "best move",

  hashtbl = HashTable()
  while 1:
    hashtbl.Init()
    movelist = []
    (bestval, bestmove, hist) = ABnegaSearchZW(board, hashtbl, -1e10, +1e10, movelist, 1, alphabetacallback)
    (bestval, bestmove, hist) = ABnegaSearchZW(board, hashtbl, -1e10, +1e10, movelist, 2, alphabetacallback)
    (bestval, bestmove, hist) = ABnegaSearchZW(board, hashtbl, -1e10, +1e10, movelist, 3, alphabetacallback)
    if not bestmove:
      break
    board.Move(bestmove)
    print bestmove, "(", bestval, "-", hist, "(", hashtbl.evals, '/', hashtbl.hashCount, "))"
    PrintMovelist(movelist)

def _testplayStaticEvalOnly():
  board = Board()
  board.Setup()
  movelist = []
  while 1:
    moves = GenerateAllLegalMoves(board)
    
    (bestval, bestmove, hist) = ABnegaSearchZW(board, hashtbl, -1e10, +1e10, movelist, 1, alphabetacallback)
    if not bestmove:
      break
    board.Move(bestmove)
    print bestmove, "(", bestval, "-", hist, "(", hashtbl.evals, '/', hashtbl.hashCount, "))"

def _testbeg():
  board = StringToBoard(
			"rnbqkbnr"
			"pp..pppp"
			"..p....."
			".B.p...."
			"....P..."
			"..N....."
			"PPPP.PPP"
			"R.BQK.NR", white)
  print GenerateAllLegalMoves(board)
  PrintBoard(board)
  PrintBoardDebug(board)

  hash = HashTable()

  while 1:
    hash.Init()
    movelist = []
    (bestval, bestmove, hist) = ABnegaSearchZW(board, hash, -1e10, +1e10, movelist, 2, alphabetacallback)
    if not bestmove:
      break
    print "MOVEstart", bestmove, board.turn
    board.Move(bestmove)
    print "MOVEend", bestmove, board.turn
    print GenerateAllLegalMoves(board)
    PrintBoard(board)
    PrintBoardDebug(board)
    print bestmove, "(", bestval, "-", hist, "(", hash.evals, '/', hash.hashCount, "))"
    break # for profiler

def _testbegsimpler():
  board = StringToBoard(
			"rnbqkbnr"
			"pp..pppp"
			"..p....."
			".B.p...."
			"....P..."
			"..N....."
			"PPPP.PPP"
			"R.BQK.NR", white)
  board.Move(StringToMove(board, "b5-a4"))
  print GenerateAllLegalMoves(board)
  PrintBoard(board)
  PrintBoardDebug(board)

  movelist = []
  hash = HashTable()
  while 1:
    hash.Init()
    (bestval, bestmove, hist) = ABnegaSearchZW(board, hash, -1e10, +1e10, movelist, 2, alphabetacallback)
    if not bestmove:
      break
    print "MOVEstart", bestmove, board.turn
    board.Move(bestmove)
    print "MOVEend", bestmove, board.turn
    print GenerateAllLegalMoves(board)
    PrintBoard(board)
    PrintBoardDebug(board)
    print bestmove, "(", bestval, "-", hist, "(", hash.evals, '/', hash.hashCount, "))"
#    break # for profiler


def _testplayAlphaBetaZW():
  file = open("game-abzw.txt", "w")
  board = Board()
  board.Setup()
  hash = HashTable()
  movelist = []
  while 1:
    hash.Init()
    (bestval, bestmove, hist) = ABnegaSearchZW(board, hash, -1e10, +1e10, movelist, 3, alphabetacallback)
    str = repr(bestmove) + "(" + repr(bestval) + "-" + repr(hist)+'\n'
    file.write(str)
    if not bestmove:
      break
    board.Move(bestmove)
#    PrintBoard(board)
    print bestmove, "(", bestval, "-", hist, "(", hash.evals, '/', hash.hashCount, "))"
    break # for profiler

def _testplayrandomFindMoveStats(ngames, nmoves):
  import random
  count0 = 0
  count1 = 0
  count2 = 0
  count0x = 0
  count1x = 0
  count2x = 0
  for i in range(ngames): # take a number of games...
    print "----------------"
    board = Board()
    board.Setup()
#    moves = ("e2-e4", "e7-e5", "d2-d4", "e5xd4", "d1xd4", "b8-c6", "d4-d5", "f8-d6")
#    for move in moves:
#      board.Move(StringToMove(board, move))

    for i in range(nmoves):
      moves = GenerateAllLegalMoves(board)
      if len(moves) == 0:
        break
      ix = int(random.random() * len(moves))
      if ix >= len(moves):
        ix = len(moves) - 1
#      print "JJ", ix, len(moves)
      pickmove = moves[ix]
      board.turn = -board.turn
      movesOpp = GenerateAllLegalMoves(board)
      board.turn = -board.turn

      board.Move(pickmove) # move changes the parameter

      newmovesOpp = GenerateAllLegalMoves(board)

      check = IsKingChecked(board, board.turn)

      board.turn = -board.turn
      newmoves = GenerateAllLegalMoves(board)
      board.turn = -board.turn

      moveCountInc = 0
      moveCountDec = 0
      moveCountBoth = 0
      strmoves = map(repr, moves)
      strnewmoves = map(repr, newmoves)

      for move in strnewmoves:
        if move in strmoves:
          moveCountBoth = moveCountBoth + 1
        else:
          moveCountInc = moveCountInc + 1
      for move in strmoves:
        if move in strnewmoves:
          pass
        else:
          moveCountDec = moveCountDec + 1
      count0 = count0 + moveCountBoth 
      count1 = count1 + moveCountInc 
      count2 = count2 + moveCountDec

      moveCountInc = 0
      moveCountDec = 0
      moveCountBoth = 0
      strmovesOpp = map(repr, movesOpp)
      strnewmovesOpp = map(repr, newmovesOpp)

      for move in strnewmovesOpp:
        if move in strmovesOpp:
          moveCountBoth = moveCountBoth + 1
        else:
          moveCountInc = moveCountInc + 1
      for move in strmovesOpp:
        if move in strnewmovesOpp:
          pass
        else:
          moveCountDec = moveCountDec + 1
      print "X", moveCountBoth, moveCountInc, moveCountDec
      if check:
        count0x = count0x + moveCountBoth 
        count1x = count1x + moveCountInc 
        count2x = count2x + moveCountDec
      else:
        count0 = count0 + moveCountBoth 
        count1 = count1 + moveCountInc 
        count2 = count2 + moveCountDec

  print "FINAL", count0x, count1x, count2x
  print "FINAL", count0, count1, count2

def _testplayrandom(ngames, nmoves):
  import random
  import copy
  for i in range(ngames): # take a number of games...
    print "----------------"
    board = Board()
    board.Setup()
    hash = HashTable()
    for i in range(nmoves):
      hash.Init()
      moves = GenerateAllLegalMoves(board)
      if len(moves) == 0:
        break
      ix = int(random.random() * len(moves))
      if ix >= len(moves):
        ix = len(moves) - 1
#      print "JJ", ix, len(moves)
      pickmove = moves[ix]
      copyboard = copy.deepcopy(board)
      board.Move(pickmove)
      if random.random() < 0.5:
        board.RetractMove()
        if not board.Equal(copyboard):
          print "-------------- boards not equal ---------------"
          PrintBoard(board)
          PrintBoard(copyboard)
          print pickmove
          raise ValueError
      else:
        print pickmove


def GenMap(pieces):
  retval = [0] * 13
  for i in pieces:
    retval[i] = retval[i] + 1
  return retval

def _testevalsinglesquarecomplex():
  for capture in whitePieces:
    for hitter in (black, white):
      d = -hitter
      map = GenMap((hitter*knight,
		hitter*knight,
		hitter*bishop,
		d * rook,
		d * rook,
		d * queen))
      val = EvalSingleSquare(d * capture, map, hitter, 0)
      should = pieceValues[d*capture]
#      print "hopo", val,should,map,hitter
      assert abs(val - should) < 0.4

  val = EvalSingleSquare(-1, [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], 1, 0)
  print ":::EvalSingleSquare:::(-1, [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], 1)", val
  assert val == 0


def _testevalsinglesquarenoonehits():
  for t in (white, black):
    for capture in whitePieces + (free,) + blackPieces:
      val = EvalSingleSquare(capture, [0] * 13, t, 0)
      assert val == 0
  
def _testevalsinglesquare():
  val = EvalSingleSquare(-1, GenMap((1,)), white, 0)
  print "val", val

  print "test single hits"
  turn = white
  for capturer in whitePieces:
    for capture in blackPieces + (free,):
      val = EvalSingleSquare(capture, GenMap((capturer,)), turn, 0)
      should = pieceValues[capture]
      if abs (val - should) > 0.2:
        raise ValueError, ("_testevalsinglesquare", repr(capturer), "hits", repr(capture), ":", val, "!=", should)

  turn = black
  for capturer in blackPieces:
    for capture in whitePieces + (free,):
      val = EvalSingleSquare(capture, GenMap((capturer,)), turn, 0)
      should = pieceValues[capture]
      if abs (val - should) > 0.2:
        raise ValueError, ("_testevalsinglesquare", repr(capturer), "hits", repr(capture), ":", val, "!=", should)

  turn = white
  for capturer in whitePieces:
    for capture in whitePieces:
      val = EvalSingleSquare(capture, GenMap((capturer,)), turn, 0)
      should = 0
      if abs (val - should) > 0.2:
        raise ValueError, ("_testevalsinglesquare", repr(capturer), "hits", repr(capture), ":", val, "!=", should)

  turn = black
  for capturer in blackPieces:
    for capture in blackPieces:
      val = EvalSingleSquare(capture, GenMap((capturer,)), turn, 0)
      should = 0
      if abs (val - should) > 0.2:
        raise ValueError, ("_testevalsinglesquare", repr(capturer), "hits", repr(capture), ":", val, "!=", should)
  
  print "test single hits ok"

def _testreps():
  board = Board()
  board.Setup()
  for i in range(2,10):
    board.Move(StringToMove(board, "b1-c3"))
    board.Move(StringToMove(board, "b8-c6"))
    board.Move(StringToMove(board, "c3-b1"))
    board.Move(StringToMove(board, "c6-b8"))
    reps = board.CountRepetitions()
    print "repsut", reps, i
    assert reps == i

def _testplayhuman():
  board = Board()
  board.Setup()
  hash = HashTable()
  lastmove = None
  movelist = []
  while 1:
    hash.Init()
    (bestval, bestmove, hist) = ABnegaSearchZW(board, hash, -1e10, +1e10, movelist, 3, alphabetacallback)
    if not bestmove:
      break
    board.Move(bestmove)
    PrintBoard(board)
    print GenerateAllLegalMoves(board)
    while 1:
      import sys
      emovestr = sys.stdin.readline()[:-1]
      if emovestr == "debug":
        PrintBoardDebug(board)
      elif emovestr == "retract":
        board.RetractMove()
        board.RetractMove()
        PrintBoard(board)
      else:
        try:
          emove = StringToMove(board, emovestr)
          board.Move(emove)
          lastmove = emove
          PrintBoard(board)
          break
        except a,b:
          print a, b
      
#    PrintBoard(board)
    print bestmove, "(", bestval, "-", hist, "(", hash.evals, '/', hash.hashCount, "))"
#    break # for profiler

def _testbishopattackmap():
  board = StringToBoard(
    "r..qk.nr"
    "..ppbppp"
    "bpn.p..."
    "p...P..."
    "...P...."
    "..P..N.."
    "PP.BBPPP"
    "RN.QK..R", white
  );
  moves = GenerateAllLegalMoves(board)
  whitecastling = StringToMove(board, "O-O")
  assert whitecastling in moves
  assert board.attackmap[4 * 8 + 1][-bishop] == 1

def _testevaluator0():
  board0 = StringToBoard(
    ".....rk."
    "..pp...."
    ".p..p..p"
    "p.....p."
    "...n..P."
    "..P.P.NP"
    "PP....K."
    ".....R..", white)
  board1 = StringToBoard(
    ".....rk."
    "..pp...."
    ".pn.p..p"
    "p.....p."
    "...P..P."
    "..P.P.NP"
    "PP....K."
    ".....R..", white)
  e0, e1 = Eval(board0), Eval(board1)
  assert e0 > e1 + 1.0

def _testlockedpawnattackmap():
  board = StringToBoard(
"k.....r."
"ppp..p.p"
"P.B..p.."
".p..p..."
".P..P..."
"..Prb..P"
"....NPP."
"....RRK.", black) #blacks bishop in imminent danger
  GenerateAttackMaps(board)
  PrintBoardDebug(board)
  assert board.attackmap[20][pawn] == 1
  assert board.attackmap[21][pawn] == 0
  assert board.attackmap[22][pawn] == 0
  assert board.attackmap[23][pawn] == 0
  assert board.attackmap[40][-pawn] == 0
  assert board.attackmap[42][-pawn] == 1

def _testplay0():
  board = StringToBoard(
"r...k..r"
".bppqpp."
".pP.p..."
"p......p"
"..P..P.."
"P.P...P."
".B.QP.BP"
"R....RK.", black)
  move = StringToMove(board, "e7-c5")
  print "turn-1", board.turn

  board.Move(move)
  print "turn0", board.turn
  e = Eval(board)
  print "Eval",e
  print "turn", board.turn
  assert e > 3


def _testtightsituation():
  board = StringToBoard(
".......r"
".pkq.p.."
".p..b..."
".Pp.B..."
"P.P.P.r."
"....Q..."
"....BPP."
"R.....K.", black)
  movelist = []
  hash = HashTable()
  hash.Init()
  (bestval, bestmove, hist) = ABnegaSearchZW(board, hash, -1e10, +1e10, movelist, 2, alphabetacallback)
#  print "HUH", bestval, bestmove, hist
#  PrintBoardDebug(board)
#  assert bestmove.fromIx == 4 * 8 + 3
#  assert bestmove.toIx == 5 * 8 + 2
  e = Eval(board)
  print "Eval",e
#  print "turn", board.turn
#  assert e > 3

def _testqueenbishoplineattack():
  board = StringToBoard(
"...rr.k."
".pp...pp"
"p.n..pq."
"..b.p..."
".P......"
"..BP.NPP"
"P.PQRPK."
"....R...",
  black
  )
  GenerateAttackMaps(board)
  for i in board.attackmap:
    print i, ","
  attackmapshouldbe = [
[0,0,0,1,1,0,0,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0,0,0],
[0,0,0,0,1,1,0,0,0,0,0,0,0],
[0,0,0,0,1,1,0,0,0,0,0,0,0],
[0,0,1,0,1,1,0,0,0,0,0,0,0],
[0,0,0,0,1,0,1,0,0,0,0,0,0],
[0,0,1,0,1,0,1,0,0,0,0,0,0],
[0,0,0,0,1,0,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,1,0,0,0,0,0,0,0],
[0,0,1,1,1,0,0,0,0,0,0,0,0],
[0,0,0,0,1,1,0,0,0,0,0,0,0],
[0,0,0,0,1,1,1,0,0,0,1,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,1,0,0,0,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,2,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,1,0,0,0,0,0,0,0],
[0,1,0,0,0,1,0,0,1,1,0,0,0],
[0,1,0,0,2,1,0,0,0,0,1,0,0],
[0,0,0,0,0,0,1,0,0,0,0,0,0],
[0,1,0,0,0,0,1,0,1,0,0,0,0],
[0,0,0,0,0,0,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,1,0,1,0,0,0,0,1,1,0],
[0,1,0,0,0,0,0,0,0,0,0,0,0],
[0,0,1,1,0,0,0,0,0,1,1,1,1],
[0,1,0,0,2,0,0,0,1,0,0,0,0],
[0,0,0,0,0,1,0,0,0,0,0,0,1],
[0,1,0,0,0,0,0,0,1,0,0,0,0],
[0,0,1,0,0,0,0,0,0,0,0,0,0],
[0,1,0,1,0,1,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,0,0,0,0,0,1],
[0,1,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,1,0,0,0],
[0,0,1,1,2,0,0,0,0,1,0,1,1],
[0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,1,0,0,1,0,0,1,0,0,0,1],
[0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,0,0,0,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,0,0,1,1,0,1],
[0,0,0,0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,0,0,1,0,0,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,1],
[0,0,0,0,0,1,0,0,1,0,0,0,1],
[0,0,0,0,0,0,0,0,0,0,1,1,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,0,0,0,1,1,1,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0],
[0,0,0,0,0,0,0,0,0,2,0,0,0],
[0,0,0,0,0,0,0,0,0,2,0,1,0],
[0,0,0,0,0,0,0,0,0,2,0,0,0],
[0,0,0,0,0,0,0,0,0,1,0,1,0],
[0,0,0,0,0,0,0,0,1,1,0,0,0],
[0,0,0,0,0,0,0,1,0,2,1,0,0],
[0,0,0,0,0,0,0,0,0,2,0,0,0],
[0,0,0,0,0,0,0,1,0,0,0,0,0]]
  for i in range(64):
    print "h", i, attackmapshouldbe[i], board.attackmap[i]
    assert attackmapshouldbe[i] == board.attackmap[i]

def _testreveal():
  board = StringToBoard(
"rnbqk.nr"
"pppp.ppp"
"........"
"....p..."
".b..P..."
".....N.."
"PPPP.PPP"
"RNBQKB.R",
  white
  )
  GenerateAttackMaps(board)
  PrintBoardDebug(board)  

  realmoves = GenerateAllLegalMoves(board)
  print "reveal hajoa", realmoves
    

def _testevalmate():
  boardMate = StringToBoard(
".......Q"
"........"
"........"
".......k"
".....p.."
".....K.P"
"........"
"......R.",
  black
  )
  boardNotMate = StringToBoard(
"........"
".....Q.."
"........"
".......k"
".....p.."
".....K.P"
"........"
"......R.",
  black
  )
  eMate = Eval(boardMate)
  eNot = Eval(boardNotMate)
  print eNot, eMate
  assert (eMate > eNot)
  
def _testevaldualcapture():
  board = StringToBoard(
"....r.k."
"p.RbRpp."
".......p"
"........"
".P......"
"P.P.KP.."
"...r..PP"
"........", black)
  e = Eval(board)
  print e
#  assert e > 2

  board = StringToBoard(
"....R.k."
"p.Rb.pp."
".......p"
"........"
".P......"
"P.P.KP.."
"...r..PP"
"........", white)
  e = Eval(board)
  print e
  assert e > 2

def _testevaldualcapture2():
  board = StringToBoard(
"r..qr.k."
"ppp..ppp"
"..N..n.."
"......B."
"....P..."
"..NP...."
"bPP..bPP"
"R..Q.RK.", white)
  e = Eval(board)
  print e
#  assert e > 2

def _testevalqueencapture():
  board = StringToBoard(
"r.b.kbnr"
"ppp..ppp"
"..n....."
".B..p..."
"........"
"..N..N.."
"qPPP.PPP"
"R.BQ.RK."
, white)
  e = Eval(board)
  print e
  assert e > 2

def _testevaldualcapture3():
  board = StringToBoard(
"r.bqk.nr"
"pppp.ppp"
"..n....."
"...Pp..."
".b..P..."
"..P....."
"PP...PPP"
"RNBQKBNR", black)
  e = Eval(board)
  print e, board.uncertainty
  assert e > -board.uncertainty

def _testOpeningsTail(board):
  from openinglibrary import allnextmoveslib
  openingmoves = allnextmoveslib(board.moveHistory)
  realmoves = GenerateAllLegalMoves(board)
  for omove in openingmoves:
    movename = omove.split(":")[0]
    print "trying", omove
    found = 0
    for rmove in realmoves:
      if repr(rmove) == movename:
        found = 1
        board.Move(rmove)
        _testOpeningsTail(board)
        board.RetractMove()
    if not found:
      PrintBoard(board)
      print realmoves
      raise "Could not generate opening move ", omove


def _testopenings():
  board = Board();
  board.Setup()
  _testOpeningsTail(board)


def _test():
  _testreveal()
  _testplay0()
  _testbishopattackmap()
  _testpawn0()
  _testsetup()
  _testpawn1()
  _testpawn2()
  _testpawnpromotion()
  _testpawnenpassant()
  _testknight()
  _testbishop()
  _testrook()
  _testqueen()
  _testking()
  _testkingchecked0()
  _testkingchecked1()
  _testcastlingKingside0()
  _testcastlingKingside1()
  _testcastlingKingside2()
  _testcastlingQueenside0()
  _testcastlingNone()
  _testreps()
  _testretractenpassant()
  _testplay0()
  _testkingchecked2()
  _testkingchecked3()
  _testlockedpawnattackmap()
  _testevaluator0()

  _testevalsinglesquarenoonehits()
  _testevalsinglesquarecomplex()
  _testevalsinglesquarecomplex()
  _testevalsinglesquarecomplex()

  _testevalsinglesquare()

  _testtightsituation()
  _testqueenbishoplineattack()
  _testevalmate()
  _testevaldualcapture()
  _testevaldualcapture2()
  _testevaldualcapture3()
  _testevalqueencapture()
  _testopenings()

def _testlonger():
  _testbeg()
  _testplayrandomFindMoveStats(10, 30)
  _testBeginning()
  _testBeginning2()
  _testplayrandom(3,20)
  _testplayrandom(1,200)
  _testplayAlphaBetaZW()




_testevaldualcapture3()

#_test()
#_testlonger()
#_testplayhuman()

#_testbeg()