I am trying to implement pvs into my Othello ai, as a way to improve on alpha beta proning, but when I implement it, it is actually slower by about double, my question is, how would I implement it, and can i do it by keeping min/man and not having to make it into a single function. I welcome any suggestions. I roughly understand how pvs works, but i am still confused on some things. my scoring function gives a positive number for x and a negative for y
def max_step(board,depth,path,a,b):
if game_end(board):
return score_end(board)
if depth == 0:
return score(board)
my_moves = {i:score((k := make_move(board,i,"x"))) for i in find_indexses(board,"x")}
if len(my_moves) == 0:
return min_step(board,depth-1,path,a,b)
results = []
my_sorted_moves = dict(sorted(my_moves.items(), key=lambda item: item[1],reverse=True))
result = None
for move,index in enumerate(my_sorted_moves.keys()) :
new_board = make_move(board,index,"x")
if index == 0:
result = min_step(new_board,depth-1,path+[board],a,b)
else:
result = min_step(new_board,depth-1,path+[board],b-1,b)
if result > a and result < b:
result = min_step(new_board,depth-1,path+[board],a,b)
results.append(result)
if result >= a:
a = result
if b <= a:
break
return max(results)
def min_step(board,depth,path,a,b):
if game_end(board):
return score_end(board)
if depth == 0:
return score(board)
my_moves = {i:score((k := make_move(board,i,"o"))) for i in find_indexses(board,"o")}
if len(my_moves) == 0:
return min_step(board,depth-1,path,a,b)
results = []
my_sorted_moves = dict(sorted(my_moves.items(), key=lambda item: item[1]))
result = None
for move,index in enumerate(my_sorted_moves.keys()) :
new_board = make_move(board,index,"o")
if index == 0:
result = max_step(new_board,depth-1,path+[board],a,b)
else:
result = max_step(new_board,depth-1,path+[board],b-1,b)
if result > a and result < b:
result = max_step(new_board,depth-1,path+[board],a,b)
results.append(result)
if result <= b:
b = result
if b <= a:
break
return min(results)
def find_next_move(board,token,depth):
res = {}
for moves in find_indexses(board,token):
if token == "x":
board1 = board
board1 = make_move(board1,moves,"x")
res[moves] = min_step(board1,depth-1,[board],-99999999,9999999)
else:
board1 = board
board1 = make_move(board1,moves,"o")
res[moves] = max_step(board1,depth-1,[board],-99999999,9999999)
print(res)
if token == "x":
return max(zip(res.values(), res.keys()))[1]
return min(zip(res.values(), res.keys()))[1]
I tried to keep my min/max functions intact and just edited them to add pvs, but it doesn't work, I also attempted to use only one function but that just did not make sense to me in the context of othello, aside from that I don't know what to do
I'd strongly recommend making it into a single function that can play as either side. You have doubled your troubles here by creating two copies of essentially the same routine that both have to be correct and kept exactly in step.
If you represent the sides by +1 and -1 then multiplying the positional score by "side" makes the problem a pure maximisation one on every level.
(Nega)Scout requires that the move ordering is very good for it to out perform alpha-beta and usually takes its principal variation starting point from the result of the previous N-1 depth search. If you don't do iterative deepening to get a fairly good PV then I'm not sure there will be an obvious benefit.
The other heuristic which works well in either NegaScout or Alpha-Beta is the "Killer move" heuristic which if it is a legal move is worth trying before doing any move generation (I'm not sure how well it works in Othello).
If you get any of the pruning windows wrong you will likely end up doing all of the work twice because the initial optimistic scout search fails and so it then has to do a full window search hence your observation.
I suggest picking a test position with a small number of legal moves (constructed if necessary it need not be a sensible real game position) that is 3 or 4 moves away from being won by white and with just one extremely strong winning move and then follow the code execution through at each ply level 2 through 4 to see where it fails to prune accurately. If you keep the number of valid moves low then you can explore and map the whole game tree manually.
You can do it with separate min and max if you really want but it doubles the risk of making a silly mistake (even if you do need to think very carefully to collapse it into a single routine). I suggest checking them against each other as snippets in something like Diff to make sure they are self consistent.
It is all too easy to make a fence post error or miss a "-" somewhere!
I think the example given in Wiki for Principal Variation Search is OK. Why not try a new function based on that and see if you can get that to work?