"""Build the opening book (data/book.bin) for the Psion Organiser II chess program.

Stages (each caches its result under tools/book/cache/, so a rerun is fast):
  1. extract : stream the Lichess PGN dump -> cache/games.txt
               (one line per game: whiteElo blackElo estSeconds san1 san2 ... up to MAXPLY)
  2. stats   : prefix trie over move sequences for the "club" and "strong" rating bands,
               merged by position (transpositions) -> cache/stats.pkl
  3. tree    : frequency-driven expansion; engine (P) moves checked by Stockfish
               (evals cached in cache/sf.json) -> data/book.bin + data/book_report.txt

Usage:  python -E -P build_book.py [--stage all|extract|stats|tree] [--force]
"""
import argparse
import heapq
import io
import json
import os
import pickle
import re
import sys
import time
from collections import Counter, defaultdict
from concurrent.futures import ThreadPoolExecutor

import chess
import chess.engine

HERE = os.path.dirname(os.path.abspath(__file__))
CHESS = os.path.normpath(os.path.join(HERE, '..', '..'))
PGN = os.path.join(CHESS, 'ext', 'lichess', 'lichess_2016-01.pgn.zst')
OPENINGS = [os.path.join(CHESS, 'ext', 'openings', c + '.tsv') for c in 'abcde']
STOCKFISH = os.path.join(CHESS, 'ext', 'stockfish', 'stockfish', 'stockfish-windows-x86-64-universal.exe')
CACHE = os.path.join(HERE, 'cache')
DATA = os.path.join(CHESS, 'data')
GAMES = os.path.join(CACHE, 'games.txt')
STATS = os.path.join(CACHE, 'stats.pkl')
SFCACHE = os.path.join(CACHE, 'sf.json')
BOOK = os.path.join(DATA, 'book.bin')
REPORT = os.path.join(DATA, 'book_report.txt')

# ---------------------------------------------------------------- parameters
MAXPLY = 24             # plies kept per game in the extract
MIN_SECONDS = 180       # club games: base + 40*increment >= 3 minutes (no bullet)
CLUB = (1200, 1900)     # both players inside this band
STRONG = 2000           # both players >= this
CLUB_TRIE_MIN = 10      # keep club trie nodes reached by >= this many games
STRONG_TRIE_MIN = 2
OPP_MIN_GAMES = 30      # opponent move: >= 30 games ...
OPP_MIN_SHARE = 0.01    # ... and >= 1% of games in the position
P_MAX = 3               # engine moves per position
P_CAND = 5              # human candidates checked by Stockfish
P_MIN_SHARE = 0.05      # candidate needs >= 5% of strong games in the position
P_REL = 0.30            # keep a passing candidate if its weighted popularity >= 30% of the top one
STRONG_MIN_TOTAL = 20   # fewer strong games than this -> fall back to club stats for candidates
SF_DEPTH = 16
SF_MARGIN = 35          # centipawns
SF_WORKERS = 12
MAX_DEPTH = 20          # plies
TARGET_MOVES = 5500
MAX_BYTES = 11800

MAINLINES = [  # Lichess chess-openings names (the last listed line of each name is checked)
    "Ruy Lopez: Closed", "Ruy Lopez: Berlin Defense", "Italian Game: Giuoco Piano",
    "Italian Game: Two Knights Defense", "Scotch Game", "Petrov's Defense",
    "Sicilian Defense: Najdorf Variation", "Sicilian Defense: Dragon Variation", "Sicilian Defense: Open",
    "Sicilian Defense: Alapin Variation", "French Defense: Winawer Variation", "French Defense: Advance Variation",
    "French Defense: Tarrasch Variation", "Caro-Kann Defense: Advance Variation", "Caro-Kann Defense: Main Line",
    "Scandinavian Defense: Main Line", "Pirc Defense", "Queen's Gambit Declined",
    "Queen's Gambit Accepted", "Slav Defense", "King's Indian Defense: Normal Variation",
    "Nimzo-Indian Defense", "Grünfeld Defense", "Indian Defense: London System",
    "English Opening", "Dutch Defense",
]

# Mild style preferences (open games, quick development): multipliers on popularity
# when ranking P candidates, keyed by the SAN path.
PREFER = {
    (): {'e4': 4.0},
    ('e4',): {'e5': 2.5},
    ('d4',): {'d5': 1.5},
    ('e4', 'e5'): {'Nf3': 2.0},
    ('e4', 'e5', 'Nf3'): {'Nc6': 2.0},
    ('e4', 'e5', 'Nf3', 'Nc6'): {'Bb5': 1.5, 'Bc4': 1.5},
}


def log(*a):
    print(time.strftime('%H:%M:%S'), *a, flush=True)


# ---------------------------------------------------------------- stage 1
COMMENT = re.compile(r'\{[^}]*\}')


def est_seconds(tc):
    if tc == '-' or not tc:
        return 99999
    try:
        base, inc = tc.split('+')
        return int(base) + 40 * int(inc)
    except ValueError:
        return 0


def stage_extract(force=False):
    if os.path.exists(GAMES) and not force:
        log('extract: cached', GAMES)
        return
    import zstandard
    tmp = GAMES + '.tmp'
    n = kept = 0
    we = be = tc = None
    with open(PGN, 'rb') as f, open(tmp, 'w', encoding='ascii', newline='\n') as out:
        reader = zstandard.ZstdDecompressor().stream_reader(f, read_size=1 << 20)
        text = io.TextIOWrapper(reader, encoding='utf-8', errors='replace')
        try:
            for line in text:
                c = line[:1]
                if c == '[':
                    if line.startswith('[WhiteElo '):
                        we = line[11:-3]
                    elif line.startswith('[BlackElo '):
                        be = line[11:-3]
                    elif line.startswith('[TimeControl '):
                        tc = line[14:-3]
                    continue
                if c == '\n' or not c:
                    continue
                # movetext line (one per game in the Lichess dumps)
                n += 1
                if '{' in line:
                    line = COMMENT.sub('', line)
                moves = []
                for tok in line.split():
                    if tok[0].isdigit() or tok == '*':
                        continue
                    moves.append(tok.rstrip('?!'))
                    if len(moves) >= MAXPLY:
                        break
                if moves and we and be and we.isdigit() and be.isdigit():
                    out.write('%s %s %d %s\n' % (we, be, est_seconds(tc), ' '.join(moves)))
                    kept += 1
                we = be = tc = None
                if n % 500000 == 0:
                    log('extract: %d games, %d kept' % (n, kept))
        except zstandard.ZstdError as e:  # truncated download: stop cleanly
            log('extract: stream ended early (%s); using %d games' % (e, n))
    os.replace(tmp, GAMES)
    log('extract: done, %d games, %d kept' % (n, kept))


# ---------------------------------------------------------------- stage 2
def build_trie(lines, tmin):
    """Level-wise prefix trie over SAN sequences; nodes reached by < tmin games are dropped."""
    parent, san, count = [-1], [None], [len(lines)]
    node_of = [0] * len(lines)
    active = list(range(len(lines)))
    for k in range(MAXPLY):
        cnt = Counter()
        for g in active:
            t = lines[g]
            if len(t) > k:
                cnt[(node_of[g], t[k])] += 1
        ids = {}
        for key, c in cnt.items():
            if c >= tmin:
                ids[key] = len(parent)
                parent.append(key[0])
                san.append(key[1])
                count.append(c)
        new = []
        for g in active:
            t = lines[g]
            if len(t) > k:
                i = ids.get((node_of[g], t[k]))
                if i is not None:
                    node_of[g] = i
                    new.append(g)
        active = new
        if not active:
            break
    return parent, san, count


def merge_positions(parent, san, count):
    """Position (EPD) -> (games reaching it, {uci: games}) summed over all move orders."""
    fens = [None] * len(parent)
    epds = [None] * len(parent)
    b = chess.Board()
    fens[0], epds[0] = b.fen(), b.epd()
    pos = defaultdict(lambda: [0, Counter()])
    pos[epds[0]][0] = count[0]
    bad = 0
    for i in range(1, len(parent)):
        p = parent[i]
        if fens[p] is None:
            continue
        b = chess.Board(fens[p])
        try:
            mv = b.parse_san(san[i])
        except ValueError:
            bad += 1
            continue
        pos[epds[p]][1][mv.uci()] += count[i]
        b.push(mv)
        fens[i], epds[i] = b.fen(), b.epd()
        pos[epds[i]][0] += count[i]
    if bad:
        log('stats: %d unparsable SAN nodes skipped' % bad)
    return {k: (v[0], dict(v[1])) for k, v in pos.items()}


def stage_stats(force=False):
    if os.path.exists(STATS) and not force:
        log('stats: cached', STATS)
        return
    club, strong = [], []
    for line in open(GAMES, encoding='ascii'):
        w, b, e, mv = line.split(' ', 3)
        w, b = int(w), int(b)
        if CLUB[0] <= w <= CLUB[1] and CLUB[0] <= b <= CLUB[1] and int(e) >= MIN_SECONDS:
            club.append(mv.split())
        elif w >= STRONG and b >= STRONG:
            strong.append(mv.split())
    log('stats: %d club games, %d strong games' % (len(club), len(strong)))
    out = {'meta': {'club_games': len(club), 'strong_games': len(strong)}}
    for name, lines, tmin in (('club', club, CLUB_TRIE_MIN), ('strong', strong, STRONG_TRIE_MIN)):
        t = build_trie(lines, tmin)
        log('stats: %s trie %d nodes' % (name, len(t[0])))
        out[name] = merge_positions(*t)
        log('stats: %s %d positions' % (name, len(out[name])))
    del club, strong
    with open(STATS + '.tmp', 'wb') as f:
        pickle.dump(out, f, protocol=pickle.HIGHEST_PROTOCOL)
    os.replace(STATS + '.tmp', STATS)


# ---------------------------------------------------------------- Stockfish
class Stockfish:
    """Pool of single-threaded engines; results cached in cache/sf.json."""

    def __init__(self, workers=SF_WORKERS):
        self.workers = workers
        self.engines = []
        self.q = None
        self.cache = {}
        if os.path.exists(SFCACHE):
            c = json.load(open(SFCACHE))
            if c.get('depth') == SF_DEPTH:
                self.cache = c['pos']
        self.dirty = False

    def _queue(self):
        import queue
        if self.q is None:
            self.q = queue.Queue()
            for _ in range(self.workers):
                e = chess.engine.SimpleEngine.popen_uci(STOCKFISH)
                e.configure({'Threads': 1, 'Hash': 64})
                self.engines.append(e)
                self.q.put(e)
        return self.q

    @staticmethod
    def _cp(info, turn):
        return info['score'].pov(turn).score(mate_score=100000)

    def _work(self, fen, cands):
        q = self._queue()
        eng = q.get()
        try:
            b = chess.Board(fen)
            epd = b.epd()
            ent = self.cache.get(epd)
            lim = chess.engine.Limit(depth=SF_DEPTH)
            if ent is None:
                info = eng.analyse(b, lim)
                ent = {'best': [info['pv'][0].uci(), self._cp(info, b.turn)], 'moves': {}}
                ent['moves'][ent['best'][0]] = ent['best'][1]
            for u in cands:
                if u not in ent['moves']:
                    info = eng.analyse(b, lim, root_moves=[chess.Move.from_uci(u)])
                    ent['moves'][u] = self._cp(info, b.turn)
            self.cache[epd] = ent
            self.dirty = True
            return ent
        finally:
            q.put(eng)

    def need(self, epd, cands):
        ent = self.cache.get(epd)
        return ent is None or any(u not in ent['moves'] for u in cands)

    def get(self, fen, cands):
        epd = chess.Board(fen).epd()
        if self.need(epd, cands):
            self.misses += 1
            return self._work(fen, cands)
        return self.cache[epd]

    misses = 0

    def batch(self, jobs):
        jobs = [(f, c) for f, c in jobs if self.need(chess.Board(f).epd(), c)]
        if not jobs:
            return
        log('stockfish: evaluating %d positions with %d engines, depth %d' % (len(jobs), self.workers, SF_DEPTH))
        done = 0
        with ThreadPoolExecutor(self.workers) as ex:
            for _ in ex.map(lambda j: self._work(*j), jobs):
                done += 1
                if done % 250 == 0:
                    log('stockfish: %d/%d' % (done, len(jobs)))
                    self.save()
        self.save()

    def save(self):
        if self.dirty:
            json.dump({'depth': SF_DEPTH, 'pos': dict(self.cache)}, open(SFCACHE + '.tmp', 'w'))
            os.replace(SFCACHE + '.tmp', SFCACHE)
            self.dirty = False

    def close(self):
        self.save()
        for e in self.engines:
            e.quit()


# ---------------------------------------------------------------- stage 3
class Node:
    __slots__ = ('fen', 'path', 'wW', 'wB', 'depth', 'group', 'club_n')

    def __init__(self, fen, path, wW, wB):
        self.fen, self.path, self.wW, self.wB = fen, path, wW, wB
        self.depth = len(path)
        self.group = None      # list of [chess.Move, preferred, Node]
        self.club_n = 0


def candidates(board, path, stats):
    """Human candidate moves for the engine side: [(uci, weighted popularity)]."""
    epd = board.epd()
    src = stats['strong'].get(epd)
    if src is None or src[0] < STRONG_MIN_TOTAL:
        src = stats['club'].get(epd) or src
    if src is None:
        return []
    n, moves = src
    pref = PREFER.get(tuple(path), {})
    out = []
    for u, c in sorted(moves.items(), key=lambda kv: -kv[1])[:P_CAND]:
        if c >= 2 and c >= P_MIN_SHARE * n:
            out.append((u, c * pref.get(board.san(chess.Move.from_uci(u)), 1.0)))
    return out


PSTAT = Counter()   # P-selection counters for the report (last grow() pass)


def choose_p(board, path, stats, sf):
    """-> [(uci, weight)], 1..P_MAX moves, best first. sf=None gives the no-engine approximation."""
    cands = candidates(board, path, stats)
    if sf is None:
        passing = list(cands)
        if not passing:
            return [(None, 1.0)]
    else:
        ent = sf.get(board.fen(), [u for u, _ in cands])
        best_u, best_cp = ent['best']
        passing = [(u, w) for u, w in cands if ent['moves'][u] >= best_cp - SF_MARGIN]
        PSTAT['candidates'] += len(cands)
        PSTAT['rejected'] += len(cands) - len(passing)
        if not passing:
            PSTAT['sf_fallback'] += 1
            return [(best_u, 1.0)]
    passing.sort(key=lambda x: -x[1])
    top = passing[0][1]
    return [(u, w) for u, w in passing if w >= P_REL * top][:P_MAX]


def expand(node, stats, sf):
    board = chess.Board(node.fen)
    club = stats['club'].get(board.epd())
    n, moves = club if club else (0, {})
    node.club_n = n
    pm = choose_p(board, node.path, stats, sf)
    if pm[0][0] is None:   # approximation pass, no human data: stand-in engine move
        pm = [(next(iter(board.legal_moves)).uci(), 1.0)]
    pw = sum(w for _, w in pm)
    pdict = dict(pm)
    opp = [u for u, c in sorted(moves.items(), key=lambda kv: -kv[1])
           if c >= OPP_MIN_GAMES and c >= OPP_MIN_SHARE * n and u not in pdict]
    group = []
    white = board.turn == chess.WHITE
    for u, pref in [(u, True) for u, _ in pm] + [(u, False) for u in opp]:
        mv = chess.Move.from_uci(u)
        share = moves.get(u, 0) / n if n else 0.0
        ps = pdict[u] / pw if pref else 0.0
        if white:
            wW, wB = node.wW * ps, node.wB * share
        else:
            wW, wB = node.wW * share, node.wB * ps
        san = board.san(mv)
        board.push(mv)
        group.append([mv, pref, Node(board.fen(), node.path + [san], wW, wB)])
        board.pop()
    node.group = group
    return len(group)


def grow(stats, sf, target):
    """Expand the most likely positions first until the move budget is used."""
    PSTAT.clear()
    root = Node(chess.STARTING_FEN, [], 1.0, 1.0)
    heap = [(-2.0, 0, root)]
    tick = 1
    total = 0
    expanded = []
    while heap:
        negw, _, node = heapq.heappop(heap)
        if chess.Board(node.fen).is_game_over():
            continue
        cost = expand(node, stats, sf)
        if total + cost > target:
            node.group = None
            break
        total += cost
        expanded.append(node)
        if node.depth + 1 >= MAX_DEPTH:
            continue
        for mv, pref, child in node.group:
            w = child.wW + child.wB
            if w > 0:
                heapq.heappush(heap, (-w, tick, child))
                tick += 1
    return root, total, expanded


def to_entries(node):
    return [(mv, pref, to_entries(child) if child.group else None) for mv, pref, child in node.group]


def stage_tree():
    sys.path.insert(0, HERE)
    import book as bookreader   # our own reader/encoder in this folder
    stats = pickle.load(open(STATS, 'rb'))
    log('tree: stats loaded (%d club / %d strong positions)' % (len(stats['club']), len(stats['strong'])))
    sf = Stockfish()
    try:
        # pass 1: approximate tree without the engine, to batch the Stockfish work in parallel
        _, _, approx = grow(stats, None, int(TARGET_MOVES * 1.3))
        jobs = [(nd.fen, [u for u, _ in candidates(chess.Board(nd.fen), nd.path, stats)]) for nd in approx]
        sf.batch(jobs)
        # pass 2: real tree; shrink the budget until it fits the byte limit
        target = TARGET_MOVES
        while True:
            root, total, expanded = grow(stats, sf, target)
            blob = bookreader.encode_group(to_entries(root))
            log('tree: target %d -> %d moves, %d bytes (%d positions evaluated on demand)'
                % (target, total, len(blob), sf.misses))
            if len(blob) <= MAX_BYTES:
                break
            target = int(target * 0.97)
    finally:
        sf.close()
    with open(BOOK, 'wb') as f:
        f.write(blob)
    write_report(root, expanded, blob, stats, bookreader)


# ---------------------------------------------------------------- report
def load_openings():
    out = []
    for p in OPENINGS:
        with open(p, encoding='utf-8') as f:
            next(f)
            for line in f:
                parts = line.rstrip('\n').split('\t')
                if len(parts) >= 3:
                    sans = [t for t in parts[2].split() if not t[0].isdigit()]
                    out.append((parts[0], parts[1], sans))
    return out


def write_report(root, expanded, blob, stats, bookreader):
    st, dm, ld = bookreader.validate(blob)
    out = []
    w = out.append
    w('Opening book report  (%s)' % time.strftime('%Y-%m-%d %H:%M'))
    w('')
    w('file            : data/book.bin')
    w('bytes           : %d' % st['bytes'])
    w('moves           : %d' % st['moves'])
    w('groups          : %d' % st['groups'])
    w('P (engine) moves: %d' % st['P'])
    w('J lengths       : %d' % st['J'])
    w('max depth       : %d plies' % st['max_depth'])
    leaves = sum(ld.values())
    w('mean leaf depth : %.1f plies' % (sum(d * c for d, c in ld.items()) / leaves))
    w('moves per ply   : ' + ' '.join('%d:%d' % (d, dm[d]) for d in sorted(dm)))
    w('leaf depths     : ' + ' '.join('%d:%d' % (d, ld[d]) for d in sorted(ld)))
    w('')
    m = stats['meta']
    w('Sources: Lichess rated games 2016-01; club = both %d-%d, >= %d s (%d games); strong = both >= %d (%d games)'
      % (CLUB[0], CLUB[1], MIN_SECONDS, m['club_games'], STRONG, m['strong_games']))
    w('Opponent moves: >= %d games and >= %.0f%% of club games in the position (position-merged counts)'
      % (OPP_MIN_GAMES, OPP_MIN_SHARE * 100))
    w('Engine (P) moves: up to %d of the top %d strong-player moves (>= %.0f%% share), each within %d cp of '
      'Stockfish 19 best at depth %d (1 thread, 64 MB hash); else Stockfish best'
      % (P_MAX, P_CAND, P_MIN_SHARE * 100, SF_MARGIN, SF_DEPTH))
    w('  human candidates checked: %d, rejected by Stockfish: %d, groups using Stockfish best only: %d'
      % (PSTAT['candidates'], PSTAT['rejected'], PSTAT['sf_fallback']))
    w('')

    nd, line = root, []
    b = chess.Board()
    while nd.group:
        mv, pref, child = nd.group[0]
        line.append(b.san(mv))
        b.push(mv)
        nd = child
    w('Engine main line (first P move each ply): ' + ' '.join(line))
    w('')
    w('Most frequent positions (path -> P moves | other moves in group):')
    for nd in sorted(expanded, key=lambda n: -(n.wW + n.wB))[:40]:
        b = chess.Board(nd.fen)
        ps = [b.san(mv) for mv, pref, _ in nd.group if pref]
        others = [b.san(mv) for mv, pref, _ in nd.group if not pref]
        w('  %-44s -> P: %-16s | %s' % (' '.join(nd.path) or '(start)', ' '.join(ps), ' '.join(others)))
    w('')

    def follow(sans):
        """-> (plies of sans found in the book, node reached, board)."""
        nd, b = root, chess.Board()
        for k, s in enumerate(sans):
            if nd is None or not nd.group:
                return k, nd, b
            try:
                mv = b.parse_san(s)
            except ValueError:
                return k, None, b
            hit = [c for m2, _, c in nd.group if m2 == mv]
            if not hit:
                return k, None, b
            b.push(mv)
            nd = hit[0]
        return len(sans), nd, b

    def reach(sans):
        return follow(sans)[0] == len(sans)

    def club_n(sans):
        b = chess.Board()
        for s in sans:
            b.push_san(s)
        return stats['club'].get(b.epd(), (0, {}))[0]

    w('Lichess chess-openings lines whose whole move list is in the book, by length:')
    byl = defaultdict(lambda: [0, 0])
    missing = []
    for eco, name, sans in load_openings():
        k = min(len(sans), 12)
        ok = reach(sans)
        byl[k][0] += ok
        byl[k][1] += 1
        if not ok and len(sans) <= 8:
            n = club_n(sans)
            if n >= 3000:
                missing.append((n, eco, name, ' '.join(sans)))
    for k in sorted(byl):
        w('  %s%2d plies: %4d / %4d' % ('>=' if k == 12 else '  ', k, byl[k][0], byl[k][1]))
    w('Named lines (<= 8 plies) reached in >= 3000 club games but not fully in the book:')
    for n, eco, name, s in sorted(missing, reverse=True)[:30]:
        w('  %6d  %s %-40s %s' % (n, eco, name[:40], s))
    if not missing:
        w('  (none)')
    w('')
    w('Main named lines (plies of the line in book / line length; P moves where the line ends):')
    ops = {name: sans for eco, name, sans in load_openings()}
    for name in MAINLINES:
        sans = ops.get(name)
        if not sans:
            w('  %-46s (not in list)' % name)
            continue
        k, nd, b = follow(sans)
        tail = ''
        if k == len(sans) and nd is not None and nd.group:
            tail = 'P: ' + ' '.join(b.san(mv) for mv, pref, _ in nd.group if pref) +                 '  (+%d more in group)' % sum(1 for _, pref, _ in nd.group if not pref)
        elif k == len(sans):
            tail = '(leaf)'
        w('  %-46s %2d/%-2d %s' % (name[:46], k, len(sans), tail))
    w('')
    open(REPORT, 'w', encoding='utf-8').write('\n'.join(out) + '\n')
    print('\n'.join(out[:14]))


def main():
    ap = argparse.ArgumentParser()
    ap.add_argument('--stage', default='all', choices=['all', 'extract', 'stats', 'tree'])
    ap.add_argument('--force', action='store_true', help='recompute the selected stage')
    a = ap.parse_args()
    os.makedirs(CACHE, exist_ok=True)
    os.makedirs(DATA, exist_ok=True)
    if a.stage in ('all', 'extract'):
        stage_extract(a.force and a.stage == 'extract')
    if a.stage in ('all', 'stats'):
        stage_stats(a.force and a.stage == 'stats')
    if a.stage in ('all', 'tree'):
        stage_tree()


if __name__ == '__main__':
    main()
