<jupyter_start><jupyter_text>Backpropagating valuesThe main idea here is that in the vicinity of a terminated trajectory (game) we can reasonably hope to find other trajectories that would also be terminated. We hope to overcome the problem of sparse rewards during RL training.So we look at how we can generate training data for the value function from walking backward (using ```undo()```  from a game that has finally terminated in favour of one of the parties.<jupyter_code>import numpy as np

from wgomoku import (
    GomokuBoard, HeuristicGomokuPolicy, Heuristics, ThreatSearch,
    StochasticMaxSampler, GomokuTools as gt)
heuristics = Heuristics(kappa=3.0)
ts = ThreatSearch(max_depth=6, max_width=5)
p = HeuristicGomokuPolicy(bias=.5,topn=5, style=2, threat_search=ts)
A,B,C,D,E,F,G,H,I, J, K, L, M, N, O, P, Q, R, S, T, U = \
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21
BLACK, WHITE, EDGES = 0,1,2
import pandas as pd
SIZE=19
df = pd.read_csv("newgames1.csv", header=None)
df.columns = ['board', 'win']
games = df['board']
stones = gt.string_to_stones(games[12])
board = GomokuBoard(disp_width=10, N=SIZE, heuristics= heuristics, stones = stones)
gt.stones_to_string(stones), board.game_state()
board.display()
from wgomoku import create_sample, to_matrix12
ts = ThreatSearch(max_depth=4, max_width=5)
p = HeuristicGomokuPolicy(bias=.5,topn=5, style=2, threat_search=ts)
p.suggest(board)<jupyter_output><empty_output><jupyter_text>The ```ValueTracker```<jupyter_code>from wgomoku import ValueTracker
tracker = ValueTracker(p)<jupyter_output><empty_output><jupyter_text>Register a board with its value. Duplicates are (silently ignored).<jupyter_code>newboards = tracker.register(board)
tracker, newboards<jupyter_output><empty_output><jupyter_text>--- One step back<jupyter_code>board.undo().display()
board.game_state()
enum = np.ndenumerate(p.probas(board=board, style=2))
sampler = StochasticMaxSampler(enum, topn=10)
choices = [ gt.m2b((x,y),SIZE) for _, (x,y), prob, _ in sampler.choices]
[(chr(x+64), y) for x,y in choices]<jupyter_output><empty_output><jupyter_text>If all possible moves lead to the same terminating value, then the value before the move is just that same outcome. At the same time we record also the other terminating outcomes.<jupyter_code>newboards = tracker.register(board)
tracker, newboards<jupyter_output><empty_output><jupyter_text>--- And one more step back<jupyter_code>board.undo().display()
board.game_state()
enum = np.ndenumerate(p.probas(board=board, style=2))
sampler = StochasticMaxSampler(enum, topn=10)
choices = [ gt.m2b((x,y),SIZE) for _, (x,y), prob, _ in sampler.choices]
[(chr(x+64), y) for x,y in choices]
newboards = tracker.register(board)
tracker, newboards<jupyter_output><empty_output><jupyter_text>The value of (J, 14) is zero, but we have the forward-looking value of (J, 14) already registered! So, if all possible moves lead to a board with a known value, the negative of that value is the value of the registered board.<jupyter_code>board.undo().display()
board.game_state()
enum = np.ndenumerate(p.probas(board=board, style=2))
sampler = StochasticMaxSampler(enum, topn=10)
choices = [ gt.m2b((x,y),SIZE) for _, (x,y), prob, _ in sampler.choices]
[(chr(x+64), y) for x,y in choices]
newboards = tracker.register(board)
tracker, newboards
last_move = board.stones[-1]
board.undo().display()
board.game_state(), last_move
enum = np.ndenumerate(p.probas(board=board, style=2))
sampler = StochasticMaxSampler(enum, topn=10)
choices = [ gt.m2b((x,y),SIZE) for _, (x,y), prob, _ in sampler.choices]
[(chr(x+64), y) for x,y in choices]
newboards = tracker.register(board)
tracker, newboards<jupyter_output><empty_output><jupyter_text>Now we have come to head of the threat sequence. All of the above can be achieved in a single call to ```reg_variants```<jupyter_code>stones = gt.string_to_stones(games[12])
board = GomokuBoard(disp_width=10, N=SIZE, heuristics= heuristics, stones = stones)
tracker = ValueTracker(p)
tracker.reg_variants(board)
tracker<jupyter_output><empty_output><jupyter_text>--- Using trees from threat searchA long threat sequence from Victoria's win over Xokk:<jupyter_code>v_vs_x = 'i10h11h9g8j11k12i9j9i8i11j7g10i6i7k8l9j8l8l6k7k6l5'
stones = gt.string_to_stones(v_vs_x)
board = GomokuBoard(disp_width=10, N=19, heuristics= heuristics, stones = stones)

board.display()
v_vs_x = 'i10h11h9g8j11k12i9j9i8i11j7g10' #'i6i7k8l9j8l8l6k7k6l5'
stones = gt.string_to_stones(v_vs_x)
board = GomokuBoard(disp_width=10, N=19, heuristics= heuristics, stones = stones)

board.display()
ts = ThreatSearch(7,4)
moves, tree = ts.is_tseq_won(board)
moves
terminated = tree.select(lambda n: n.value != 0)
len(tree.all_trajectories())
stones, value = tree.all_trajectories()[5]
b = GomokuBoard(disp_width=9, N=19, heuristics=heuristics, stones = stones)
print("Value: %s - Game state: %s" % (value, b.game_state()))
b.display()
tracker = ValueTracker(p)
for t in tree.all_trajectories():
    b = GomokuBoard(disp_width=9, N=19, heuristics=heuristics, stones = t[0])
    tracker.reg_variants(b)
tracker, len(tracker.reg)<jupyter_output><empty_output><jupyter_text>See? From a single game state that represents the beginning of a winning threat sequence, we can find 20 samples with a well-defined non-zero state. That will certainly help training a policy function. But we can do even better. Any state within the threat sequence is just another state with well-defined value. Evaluated early states in a threat-sequence and will help train the policy to see the future! That means indeed that the policy will start at a significantly higher strength than with only the naive heuristics<jupyter_code>trajectories = [(l[1], l[0]) for l in tracker.reg.values()]
for t in trajectories:
    stones = gt.string_to_stones(t[0])
    value = t[1]
    if value == 1:
        to_go = stones[-10:]
        stones = stones[:-10]
    elif value == -1:
        to_go = stones[-9:]
        stones = stones[:-9]
    value = 1
    board = GomokuBoard(
        disp_width=10, N=19, heuristics= heuristics, stones = stones)  
    for x,y in to_go:
        tracker.reg_variants(board, value)
        value = -value
        board.set(x,y)
len(tracker.reg)
tracker<jupyter_output><empty_output><jupyter_text>Quality checkFirst, let's look at an example. Below, we're looking at a trajectory that's among the above registered trajectories with a value of -1. That means that black has just made another move and the value (-1 from white's point of view) suggests that this is just another threat in a winning threat sequence.<jupyter_code>sample = 'i10h11h9g8j11k12i9j9i8i11j7g10i6i7k6l5j6'
stones = gt.string_to_stones(sample)
board = GomokuBoard(disp_width=10, N=19, heuristics= heuristics, stones = stones)
board.display()<jupyter_output><empty_output><jupyter_text>What we do now is: defend the current threat and then see whether the resulting position is in fact representing the start of a winning threat sequence for black.<jupyter_code>ts = ThreatSearch(max_depth=6, max_width=3)
board = GomokuBoard(
    disp_width=10, N=19, heuristics= heuristics, stones = stones)  
move = p.suggest(bias=10.0, topn=5, board=board, style=2)
board.set(move.x, move.y)
ts.is_tseq_won(board)<jupyter_output><empty_output><jupyter_text>You can see this is true for our example. Now let's do exactly that for all of the 44 different trajectories that we have found to have terminal or pre-terminal state, the latter justified by well-determined threat-sequences<jupyter_code>trajectories = [(l[1], l[0]) for l in tracker.reg.values()]
len(trajectories)
ts = ThreatSearch(max_depth=6, max_width=3)
faults=[]
for t in trajectories:
    stones = gt.string_to_stones(t[0])
    value = t[1]
    board = GomokuBoard(
        disp_width=10, N=19, heuristics= heuristics, stones = stones)  
    state = board.game_state()
    if state != 0 and state != value:
        print("Discrepenccy: ", t[0], state, value)
        faults.append(t)
    elif value == 1:
        (_, won), _ = ts.is_tseq_won(board)
        if not won:
            print("Not a threat:", t[0], value)
            faults.append(t)
    elif value == -1:
        move = p.suggest(bias=10.0, topn=5, board=board, style=2)
        board.set(move.x, move.y)
        (_, won), _ = ts.is_tseq_won(board)
        if not won:
            print("Not a threat:", t[0], value)
            faults.append(t)
faults<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11770981507823614, 'fraction_numerical': 0.02927927927927928, 'mean_word_length': 5.310396409872849, 'pattern_counts': {'":': 0, '<': 53, '<?xml version=': 0, '>': 53, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '13', 'dir': 'jupyter-structured-clean-dedup', 'id': '460617', 'license': 'Apache-2.0', 'n_tokens_mistral': 3134, 'n_tokens_neox': 2979, 'n_words': 821, 'path': 'ValueBackProp.ipynb', 'repo_name': 'smurve/DeepGomoku', 'size': '8436'}