زنجیره‌های مارکوف جذب‌کننده، ماتریس گذار و افق زمانی در تحلیل فاز خروج (Bearoff) تخته‌نرد

مقدمه و صورت‌بندی فضاهای حالت تصادفی در بازی‌های رومیزی

در نظریه بازی‌های ریاضی و محاسباتی، کلاس بازی‌های مجموع-صفر دو نفره با اطلاعات کامل اما دارای ماهیت تصادفی (Two-Player Zero-Sum Stochastic Games with Perfect Information)، چالش‌های محاسباتی متمایزی در مقایسه با بازی‌های معین مانند شطرنج و دوز ارائه می‌دهند. در این سیستم‌ها، هر مرحله از فرایند انتقال حالت نه تنها وابسته به تصمیم عقلایی بازیکنان (Rational Agent Decisions) است، بلکه مستقیماً تحت تأثیر یک بردار متغیرهای تصادفی با توزیع احتمالی مشخص قرار دارد. بازی کلاسیک تخته‌نرد (Backgammon) به عنوان کهن‌ترین نمونه از فرایندهای تصادفی کنترل‌شده، یکی از دقیق‌ترین بسترهای ریاضی برای مطالعه مدل‌های زنجیره مارکوف زمان‌گسسته (Discrete-Time Markov Chains - DTMC) و فرایندهای تصمیم‌گیری مارکوف (MDP) به شمار می‌رود.

دینامیک تخته‌نرد به طور کلاسیک به دو فاز مجزا تفکیک می‌شود: فاز تماس (Contact Phase) که در آن مهره‌های دو بازیکن در یک ماتریس تقاطعی برهم‌کنش دارند و امکان زدن مهره (Hitting) و مسدودسازی (Blocking) وجود دارد؛ و فاز بدون برخورد یا فاز خروج (Bearoff Phase) که پس از عبور کامل مهره‌های حریفین رخ می‌دهد. در فاز پایانی خروج، سیستم به طور کامل از یک بازی رقابتی دوطرفه کوپل‌شده به دو فرایند تصادفی مستقل تک‌بازیکنه (Decoupled Single-Agent MDP) تبدیل می‌شود که در آن هدف هر عامل، کمینه‌سازی امید ریاضی زمان رسیدن به حالت جذب (Absorbing State) یعنی خروج تمامی مهره‌ها از صفحه است. در این مقاله، ساختار توپولوژیک و جبری زنجیره‌های مارکوف جذب‌کننده در فاز Bearoff، ماتریس‌های گذار کانونی، ماتریس بنیادی و الگوریتم‌های برنامه‌ریزی پویای جدول پایه خروج (Bearoff Tablebases) را مورد کالبدشکافی دقیق ریاضی قرار می‌دهیم.

ساختار ترکیبیاتی و جبری زنجیره‌های مارکوف جذب‌کننده

فرض کنید فضای حالت فاز خروج برای یک بازیکن با بردار حالت s = (c_1, c_2, c_3, c_4, c_5, c_6) مدل‌سازی شود، به طوری که c_i در بازه {0, 1, ..., 15} نشان‌دهنده تعداد مهره‌های مستقر در خانه i-ام (از خانه ۱ تا ۶) باشد، با قید مجموع c_i کمتر یا مساوی ۱۵. در این ساختار، حالت جذب یکتا که با s_0 = (0, 0, 0, 0, 0, 0) نشان داده می‌شود، وضعیتی است که تمام مهره‌ها از صفحه بازی خارج شده‌اند. اندازه دقیق این فضای حالت گسسته از طریق فرمول ترکیبیاتی ستاره‌ها و میله‌ها (Stars and Bars) برای قرار دادن حداکثر ۱۵ مهره در ۶ خانه قابل محاسبه است:

|S| = Σ C(k + 6 - 1, 6 - 1) = C(15 + 6, 6) = C(21, 6) = 54,264

این تعداد حالت (۵۴٬۲۶۴ حالت متمایز)، از نظر پیچیدگی محاسباتی به اندازه کافی محدود است که امکان حل دقیق و تحلیلی تمام بردارها را از طریق ماتریس‌های تنک (Sparse Matrices) و برنامه‌ریزی پویا فراهم آورد، اما به اندازه‌ای بزرگ و متراکم است که ساختار ماتریس گذار آن رفتارهای بسیار غنی از نظریه ارگودیسیتی و ماتریس‌های پوزیتیو-شبه‌معین به نمایش بگذارد.

یک زنجیره مارکوف با فضای حالت S جذب‌کننده نامیده می‌شود اگر حداقل یک حالت جذب وجود داشته باشد و از هر حالت گذرا (Transient State) بتوان در تعداد متناهی گام با احتمال اکیداً مثبت به حالت جذب رسید. ماتریس گذار P برای چنین سیستمی را می‌توان در فرم کانونی (Canonical Form) بلوکی زیر بازنویسی کرد:

P = [ [Q, R], [0, I_r] ]

در این فرم بلوکی، Q یک ماتریس مربعی از مرتبه t × t (که در اینجا t = 54,263 حالت گذرا است) بوده و احتمال انتقال میان حالات گذرا را نشان می‌دهد. ماتریس R از مرتبه t × r نمایانگر احتمال انتقال مستقیم از حالات گذرا به حالات جذب است (با r = 1 در فاز خروج ساده)، و I_r ماتریس همانی مرتبه r است که بازتاب‌دهنده ویژگی پایدار حالت جذب می‌باشد. ماتریس صفر در گوشه پایین سمت چپ نیز مؤید این است که فرار از حالت جذب غیرممکن است.

ماتریس بنیادی و بردار امید ریاضی افق خروج

ویژگی بنیادین ماتریس استوکاستیک فرعی Q این است که با افزایش توان‌های متوالی k -> ∞، مقادیر Q^k -> 0 همگرا می‌شوند. این قضیه از این واقعیت سرچشمه می‌گیرد که شعاع طیفی ρ(Q) = max |λ_i| < 1 اکیداً کمتر از یک است. این ویژگی وجود معکوس ماتریس زیر موسوم به ماتریس بنیادی (Fundamental Matrix) را تضمین می‌کند:

N = (I_t - Q)^(-1) = Σ_{k=0}^{∞} Q^k

درایه‌های ماتریس بنیادی N_{ij} مفهوم فیزیکی بسیار دقیقی در تئوری کنترل دارند: N_{ij} امید ریاضی تعداد دفعاتی است که زنجیره مارکوف در حالت گذرای s_j سپری می‌کند، مشروط بر اینکه سیستم از حالت s_i آغاز شده باشد. بنابراین، اگر بردار ستونی 1 را به عنوان بردار یک‌ها با بعد t تعریف نماییم، بردار زمان مورد انتظار تا جذب (Expected Time to Absorption) به صورت زیر به دست می‌آید:

τ = N 1 = (I_t - Q)^(-1) 1

مولفه i-ام این بردار، یعنی τ_i = E[T | S_0 = s_i]، امید ریاضی دقیق تعداد پرتاب‌های مورد نیاز (Expected Rolls) برای خروج کامل تمام مهره‌ها از حالت s_i را مشخص می‌کند. علاوه بر امید ریاضی مرتبه اول، گشتاور مرتبه دوم و واریانس تعداد پرتاب‌ها نیز از طریق عملگرهای برداری ماتریس بنیادی قابل استخراج است:

v = (2N - I_t) τ - τ_sq

که در آن τ_sq نشان‌دهنده ضرب هادامارد بردار τ در خودش است. واریانس حاصل، معیار دقیق عدم‌قطعیت و نوسان (Volatility) در مسابقه خروج را تعیین می‌کند که مستقیماً در تصمیم‌گیری‌های مربوط به مکعب دوبرابرکننده (Doubling Cube Decisions) و محاسبه نقاط پذیرش کیوب (Take-Points) به کار گرفته می‌شود.

فضای نمونه پرتاب تاس و اپراتور بل‌من برای بهینه‌سازی سیاست

در تخته‌نرد کلاسیک، در هر نوبت دو تاس ۶ وجهی مستقل با توزیع یکنواخت پرتاب می‌شوند. کل فضای برآمدهای ممکن تاس برابر با ۶ × ۶ = ۳۶ است. از آنجا که ترتیب تاس‌ها در خروجی فیزیکی تاثیری ندارد، این ۳۶ برآمد به ۲۱ نتیجه نامتقارن متمایز کاهش می‌یابند:

• ۱۵ پرتاب غیرجفت (مانند ۶-۵، ۴-۱ و غیره) با احتمال وقوع P(d) = 2/36 = 1/18 ≈ 0.0556 که در آن بازیکن امکان ۲ حرکت دارد.

• ۶ پرتاب جفت (مانند ۶-۶، ۵-۵، ۱-۱) با احتمال وقوع P(d) = 1/36 ≈ 0.0278 که بر اساس قوانین بازی، مقدار تاس دوبرابر شده و بازیکن ۴ حرکت با اندازه مساوی انجام می‌دهد.

یک عامل عقلایی در مواجهه با هر پرتاب d در D و حالت s در S، مجموعه‌ای از حرکات مجاز A(s, d) در اختیار دارد. هر اقدام مجاز a در A(s, d) حالت فعلی s را به یک حالت قطعی جدید s' = f(s, a) منتقل می‌سازد. تابع ارزش بهینه V*(s) که نشان‌دهنده کمینه امید ریاضی پرتاب‌های باقی‌مانده است، معادله مشهور بلمن (Bellman Optimality Equation) را ارضا می‌کند:

V*(s) = 1 + Σ_{d in D} P(d) min_{a in A(s, d)} V*(f(s, a))

با شرط مرزی مشخص برای حالت جذب: V*(s_0) = 0. از آنجا که تمام حرکات در فاز Bearoff مهره‌ها را به جلو می‌رانند یا از صفحه خارج می‌کنند، هیچ چرخه‌ای در گراف حالت وجود ندارد (s' همواره پیپ کانت یا مجموع موقعیت کمتری نسبت به s دارد). این ساختار بدون چرخه مستقیم (Directed Acyclic Graph - DAG) اثبات می‌کند که سیستم را می‌توان بدون نیاز به تکرار ماتریسی پیچیده، از طریق مرتب‌سازی توپولوژیک بر اساس مجموع پیپ (Pip Count) و برنامه‌ریزی پویای بازگشتی در زمان O(|S| · |D|) به طور دقیق حل نمود.

پیاده‌سازی الگوریتم تولید پایگاه داده خروج (Bearoff Solver)

کد پایتون زیر، ساختار پایه‌ای یک حل‌کننده دقیق جدول خروج مبتنی بر اصل بلمن و برنامه‌ریزی پویا را به تصویر می‌کشد:

import numpy as np

class BearoffTablebaseSolver:
    def __init__(self, max_checkers=15, max_points=6):
        self.max_checkers = max_checkers
        self.max_points = max_points
        self.dice_outcomes = self._generate_dice_distribution()
        self.v_table = {}  # memoization table: state_tuple -> float (expected rolls)
        self.v_table[(0,) * max_points] = 0.0

    def _generate_dice_distribution(self):
        outcomes = []
        for d1 in range(1, 7):
            for d2 in range(d1, 7):
                prob = (1.0 / 36.0) if d1 == d2 else (2.0 / 36.0)
                moves = [d1] * 4 if d1 == d2 else [d1, d2]
                outcomes.append((prob, moves))
        return outcomes

    def get_legal_transitions(self, state, moves):
        # state is tuple of checker counts on points [1, 2, 3, 4, 5, 6]
        current_states = {state}
        for die in moves:
            next_states = set()
            for st in current_states:
                transitions = self._apply_single_die(st, die)
                next_states.update(transitions)
            current_states = next_states
        return list(current_states)

    def _apply_single_die(self, state, die):
        res = []
        st = list(state)
        # Check if direct bearoff or move is possible
        p_idx = die - 1
        if p_idx < self.max_points and st[p_idx] > 0:
            nxt = list(st)
            nxt[p_idx] -= 1
            res.append(tuple(nxt))
        # Move within board
        for p in range(die, self.max_points):
            if st[p] > 0:
                nxt = list(st)
                nxt[p] -= 1
                nxt[p - die] += 1
                res.append(tuple(nxt))
        # Over-bearoff rule
        if not res:
            highest = max([idx for idx, c in enumerate(st) if c > 0], default=-1)
            if highest >= 0 and highest < p_idx:
                nxt = list(st)
                nxt[highest] -= 1
                res.append(tuple(nxt))
        return res if res else [state]

    def solve_state(self, state):
        if state in self.v_table:
            return self.v_table[state]
        
        expected_cost = 1.0
        for prob, moves in self.dice_outcomes:
            candidates = self.get_legal_transitions(state, moves)
            min_sub_cost = min(self.solve_state(cand) for cand in candidates)
            expected_cost += prob * min_sub_cost
            
        self.v_table[state] = expected_cost
        return expected_cost

حساسیت توابع ارزش نسبت به ویژگی‌های توزیع تصادفی تاس

یکی از پایه‌ای‌ترین پیش‌فرض‌های نظریه استوکاستیک در بازی‌های تخته‌ای، فرض عدم اریب بودن (Unbiasedness) و استقلال آماری توزیع پرتاب‌ها است. با این حال، در شبیه‌سازها و پلتفرم‌های ابری آنلاین، خطاهای تصادفی‌سازی و اریب‌های جزئی ژنراتورهای اعداد شبه‌تصادفی (PRNG) می‌توانند اثرات شدیدی بر ارزش‌های انتظاری بگذارند. به عنوان مثال، اگر احتمال تاس جفت از مقدار تئوریک ۶/۳۶ = ۱/۶ تنها به میزان ۱ درصد انحراف داشته باشد، تابع ارزش V*(s) در موقعیت‌های عمیق خروج تا بیش از ۴ درصد شیفت نامتقارن نشان می‌دهد.

به همین سبب، در مهندسی پلتفرم‌های محاسباتی مدرن بازی‌های فکری، استفاده از سیستم‌های تاییدپذیر تصادفی‌سازی شفاف و معماری‌های بر مبنای رمزنگاری الزامی است. الگوریتم‌های اعتبارسنجی مدرن مانند سیستم‌های مبتنی بر توابع هش با تعهد رمزنگاری (Commitment Schemes) و استانداردهای اعتبارسنجی تاس منصفانه و تصادفی نشان می‌دهند که چگونه می‌توان از طریق پروتکل‌های اثبات با دانش صفر یا جفت‌های بذر کلاینت-سرور (Client-Server Seed Pairs)، اطمینان یافت که پرتاب‌ها منطبق بر توزیع یکنواخت گسسته خالص بوده و هیچ گونه سوگیری آماری در طول زنجیره‌های مارکوف چندمیلیونی رخ نمی‌دهد.

همگرایی با تقریب‌گرهای شبکه‌های عصبی عمیق (TD-Gammon و AlphaZero)

در دهه‌های گذشته، یادگیری تقویتی تفاوت زمانی (Temporal Difference Learning) که توسط جرالد تسائورو در TD-Gammon به اوج رسید، نشان داد که شبکه‌های پرسپترون چندلایه می‌توانند توابع ارزش بسیار دقیقی بدون پایگاه داده صریح فرا گیرند. با این وجود، مطالعات تحلیلی بر روی خطای تقریب در فاز Bearoff آشکار می‌سازد که شبکه‌های عصبی پیوسته در تقریب زدن ناپیوستگی‌های تند بردار خروج با چالش مواجه می‌شوند. در موقعیت‌های خاص با تعداد مهره‌های اندک (پیکربندی‌های ۲ یا ۳ مهره)، خطای تقریب شبکه عصبی در محاسبه شانس گامان (Gammon Probability) می‌تواند تا ۱۲ درصد انحراف نسبت به حل دقیق ماتریس بنیادی ایجاد کند.

از این رو، موتورهای مدرن تخته‌نرد نظیر GNU Backgammon و WildBG رویکردی ترکیبی (Hybrid Architecture) اتخاذ می‌کنند: در فازهای پیچیده تماس و مانور استراتژیک، از تقریب‌گرهای شبکه‌های عصبی عمیق کانوولوشنال و ترنسفورمر بهره می‌گیرند، اما به محض ورود موقعیت به زیرفضای فاز بدون برخورد، کنترل مستقیماً به پایگاه داده از پیش‌محاسبه‌شده دقیق (Exact Tablebase Lookups) حاصل از حل معادلات زنجیره مارکوف جذب‌کننده واگذار می‌شود تا خطای تصمیم‌گیری به صفر مطلق کاهش یابد.

نتیجه‌گیری و افق‌های پژوهشی

کالبدشکافی فاز پایانی تخته‌نرد از منظر زنجیره‌های مارکوف جذب‌کننده، پیوند بنیادین میان احتمالات کلاسیک، تحلیل طیفی ماتریس‌ها و بهینه‌سازی تصادفی بل‌من را نمایان می‌سازد. با فرموله کردن حالات به صورت ماتریس‌های متعارف و بهره‌گیری از ماتریس بنیادی، می‌توان تمامی پارامترهای بازی شامل امید ریاضی پرتاب‌ها، واریانس، احتمال خروج زودتر از حریف و مقادیر بهینه مکعب کیوب را با دقت تحلیلی مطلق استخراج نمود. این بینش‌های نظری، زیربنای مستحکمی برای ارزیابی کیفی موتورهای هوش مصنوعی و طراحی سیستم‌های مدرن تحلیلی در بازی‌های استراتژیک فراهم می‌آورند.