search.py

   1 # search.py
   2 # 28 June 2007
   3
   4 """
   5     This file is part of Arrocco, which is Copyright 2007 Thomas Plick
   6     (tomplick 'at' gmail.com).
   7
   8     Arrocco is free software; you can redistribute it and/or modify
   9     it under the terms of the GNU General Public License as published by
  10     the Free Software Foundation; either version 3 of the License, or
  11     (at your option) any later version.
  12
  13     Arrocco is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16     GNU General Public License for more details.
  17
  18     You should have received a copy of the GNU General Public License
  19     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20 """
  21
  22 import time, ctypes, thread, Queue, threading
  23
  24 from lib import lib
  25 from position import *
  26
  27 pvCache = {}
  28
  29 def updatePVCache(pv):
  30     for (a, b) in zip(pv, pv[1:]):
  31         pvCache[a.fen()] = b
  32
  33
  34 def alphaBetaInC(pos, depth,
  35             alpha, beta, stopper = None, childArray = None):
  36     counter = ctypes.c_long(1)
  37     if childArray is None:
  38         childArray = (Position * (depth * 32))()
  39
  40     value = lib.alphaBeta(ctypes.byref(pos), childArray, depth,
  41                     alpha, beta, ctypes.byref(counter), ctypes.byref(stopper))
  42
  43     # get the PV...
  44     pv = L = [pos]
  45     node = pos
  46     for i in range(depth):
  47         try:
  48             node = node.children()[pos.getBranch(i)]
  49             L.append(node)
  50         except: break
  51
  52     return dict(value = value, pv = pv,
  53                nodeCount = counter.value)
  54
  55 def alphaBeta(pos, depth, alpha = -99999, beta = 99999, splits = 0,
  56         stopper = None, top = False, parentProc = None):
  57     a = time.time()
  58
  59     pos.offswitch.value = 0
  60     result = alphaBetaParallel(pos, depth, alpha, beta, splits,
  61                 pos.offswitch, parentProc)
  62     pvCache.clear()
  63     updatePVCache(result['pv'])
  64
  65     b = time.time()
  66     result['time'] = int(b - a) + 1
  67     return result
  68
  69
  70 # parallel stuff
  71
  72 import spawn
  73 def alphaBetaParallel(pos, depth, alpha, beta, splits, stopper, parentProc = None):
  74     kids = pos.children()
  75     if depth == 0 or len(kids) == 0 or stopper.value:
  76         return alphaBetaInC(pos, 0, alpha, beta, stopper)
  77
  78     running = []
  79     results = Queue.Queue()
  80     nodeCount = 1
  81     bestPV = []
  82
  83     q = Queue.Queue()
  84     if pos.fen() in pvCache:
  85         favorite = pvCache[pos.fen()]
  86         kids[kids.index(favorite)] = None
  87         q.put(favorite)
  88         at_a_time = 1
  89     elif splits <= 0:
  90         return alphaBetaInC(pos, depth, alpha, beta, stopper)
  91     else:  at_a_time = 2
  92
  93     for k in kids:
  94         if k is not None: q.put(k)
  95
  96     rfq = 0
  97     try:
  98         while rfq < len(kids):
  99             if len(running) < at_a_time:
 100                 try:
 101                     next = q.get_nowait().copy()
 102                     stopper = ctypes.c_int(0)
 103                     def calc():
 104                         ret = next, proc, alphaBeta(next, depth - 1, -beta, -alpha,
 105                                         splits - at_a_time + 1, stopper, parentProc)
 106                         if stopper.value == 0:  results.put(ret)
 107                     def stop(): stopper.value = 1
 108
 109                     if not parentProc:
 110                         parentProc = spawn  # module spawn
 111                     proc = parentProc.spawn(calc, stop)
 112
 113                     running.append(proc)
 114                     proc.position, proc.alpha = next, alpha
 115                     proc.start()
 116                 except Queue.Empty: pass
 117
 118             try:
 119                 resChild, resProc, result = results.get(True, .05)
 120                 try:
 121                     rfq += 1
 122                     if splits > 0:  at_a_time = 2
 123                     running.remove(resProc)
 124                 except ValueError: pass
 125             except Queue.Empty:
 126                 continue
 127
 128             value = -result['value']
 129             nodeCount += result['nodeCount']
 130
 131             for proc in running:
 132                 if proc.position == resChild:
 133                     proc.stop()
 134                     running.remove(proc)
 135
 136             if value >= beta:
 137                 alpha = beta; break
 138             elif value > alpha:
 139                 alpha = value
 140                 bestPV = [pos] + result['pv']
 141
 142                 # evaluate other pos (if there is one) with this alpha
 143                 for proc in running:
 144                     insertAtFront(proc.position, q)
 145     except KeyboardInterrupt:
 146         for kid in running: kid.stop()
 147         raise
 148
 149     for kid in running: kid.stop()
 150     return dict(value = alpha, nodeCount = nodeCount, pv = bestPV)
 151
 152
 153 def insertAtFront(element, queue):
 154     newQ = Queue.Queue()
 155     while not queue.empty(): newQ.put(queue.get())
 156     queue.put(element)
 157     while not newQ.empty(): q.put(newQ.get())
 158
 159