我正在尝试开发一种AI来最佳玩1人桌游。我正在使用深度优先搜索功能。
我已经尝试通过对所有循环进行迭代的初始循环多线程并递归到游戏树中来加快速度。我的想法是,每个线程都会将可能的初始移动板分割成多个块,并在单独的递归函数中进一步进行评估。调用的所有函数都是nogil
但是,由于多线程解决方案给出了不同的结果,所以我只能猜测是一个竞争条件,并且我不确定如何解决它。
cdef struct Move:
int x
int y
int score
cdef Move search( board_t& board, int prevClears, int maxDepth, int depth ) nogil:
cdef Move bestMove
cdef Move recursiveMove
cdef vector[ Move ] moves = generateMoves( board )
cdef board_t nextBoard
cdef int i, clears
bestMove.score = 0
# Split the initial possible move boards amongst threads
for i in prange( <int> moves.size(), nogil = True ):
# Applies move and calculates the move score
nextBoard = applyMove( board, moves[ i ], prevClears, maxDepth, depth )
# Recursively evaluate further moves
if maxDepth - depth > 0:
clears = countClears( nextBoard )
recursiveMove = recursiveSearch( nextBoard, moves[ i ], clears, maxDepth, depth + 1 )
moves[ i ].score += recursiveMove.score
# Update bestMove
if moves[ i ].score > bestMove.score:
bestMove = moves[ i ]
return bestMove
当涉及到prange
时,Cython会做一些魔术,这取决于微妙的事情-因此,人们真的必须查看结果C代码才能了解发生了什么。
据我所见,您的代码至少有两个问题。
1。问题: bestMove
未初始化。
%%cython -+
cdef struct Move:
...
def foo()
cdef Move bestMove
return bestMove
将导致以下C代码:
...
struct __pyx_t_XXX_Move __pyx_v_bestMove;
...
__pyx_r = __pyx_convert__to_py_struct____pyx_t_XXX_Move(__pyx_v_bestMove); if ...
return __pyx_r;
即使很可能初始值将仅由零组成,局部变量__pyx_v_bestMove
将保持未初始化状态(例如,参见此SO-post)。
例如,如果是bestMove
int,Cython会发出警告,但不适用于结构。
2。问题:分配bestMove
会导致赛车状态。
顺便说一句,结果可能不仅是最佳举动,而且甚至是非法举动,因为它可能是其他举动的组合(x
-,y
-,score
-值来自其他合法举动)指定的法律动作。
这里是此问题的较小复制者:
%%cython -c=-fopenmp --link-args=-fopenmp
# cython
cimport cython
from cython.parallel import prange
cdef struct A:
double a
@cython.boundscheck(False)
def search_max(double[::1] vals):
cdef A max_val = [-1.0] # initialized!
cdef int i
cdef int n = len(vals)
for i in prange(n, nogil=True):
if(vals[i]>max_val.a):
max_val.a = vals[i]
return max_val.a
是max_val
Cython不会构建它,因为它会试图将cdef double
设为私有(巧妙)。但是现在,max_val
在线程之间共享(请参见生成的C代码),并且应该保护对其的访问。如果没有,我们可以看到(可能需要运行多次才能触发竞争条件)结果:
max_val
可以做什么?正如@DavidW所建议的,我们可以收集每个线程的最大值,然后在后期处理步骤中找到绝对最大值-请参见此>>> import numpy as np
>>> a = np.random.rand(1000)
>>> search_max(a)-search_max(a)
#0.0006253360398751351 but should be 0.0
,该结果将导致:
SO-post
[我认为将openmp功能与C / C ++一起使用并用Cython包装生成的代码更容易且更不容易出错:不仅Cython %%cython -+ -c=-fopenmp --link-args=-fopenmp
cimport cython
from cython.parallel import prange, threadid
from libcpp.vector cimport vector
cimport openmp
cdef struct A:
double a
@cython.boundscheck(False)
def search_max(double[::1] vals):
cdef int i, tid
cdef int n = len(vals)
cdef vector[A] max_vals
# every thread gets its own max value:
NUM_THREADS = 4
max_vals.resize(NUM_THREADS, [-1.0])
for i in prange(n, nogil=True, num_threads = NUM_THREADS):
tid = threadid()
if(vals[i]>max_vals[tid].a):
max_vals[tid].a = vals[i]
#post process, collect results of threads:
cdef double res = -1.0
for i in range(NUM_THREADS):
if max_vals[i].a>res:
res = max_vals[i].a
return res
不行,而且在看简单代码时很难在并行代码中看到问题C代码,没有Cython所做的任何隐式魔术。