बुनियादी सिद्धांतों से शुरू हुई Monte-Carlo Graph Search

 (github.com/lightvector)
3 पॉइंट द्वारा GN⁺ 2024-03-11 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Monte-Carlo Graph Search(MCGS) एक ऐसा तरीका है जो उन खेलों में, जहाँ कई move sequences एक ही state में transition करते हैं, MCTS को tree के बजाय directed graph पर लागू करके duplicate search को साझा करने की कोशिश करता है
  • मौजूदा MCTS के visit count N और average value Q को सीधे DAG में ले जाने पर, shared child का visit count parent की policy और value estimation से मेल नहीं खा सकता, जिससे algorithm unsound हो सकता है
  • MCTS को regularized policy optimization के रूप में देखें तो PUCT द्वारा बनाई गई action-wise visit distribution posterior policy है, और Q को उस policy की expected utility के रूप में समझा जा सकता है
  • सही MCGS child node visit count से अलग edge visit count N(n,a) को track करता है, और Q को U(n) तथा child Q के weighted sum से दोबारा calculate करके graph में भी policy और value का अर्थ बनाए रखता है
  • वास्तविक implementation में stale Q, incremental updates, transposed child से playout जारी रखना है या नहीं, hash collisions और game के cycles को handle करने जैसे विकल्प बाकी रहते हैं, और KataGo अभी idempotent updates का उपयोग करता है

Tree search जिन transposed states को छोड़ देती है

  • Game tree search में अलग-अलग move sequences का एक ही state में transition(transposition) होना संभव है
    • Chess में 1. d4 d5 2. Nf3 और 1. Nf3 d5 2. d4 एक ही position तक पहुँचते हैं
  • जिन games में transposition संभव है, उनमें search depth बढ़ने पर duplicate states exponential रूप से बढ़ सकते हैं, इसलिए एक ही state की computation साझा करना बेहतर है
  • सामान्य MCTS implementation game को branching tree की तरह treat करता है और उसी position के कई instances को फिर से search करता है
    • repeated positions के लिए neural-network evaluation caching जैसी low-level optimization लागत घटा सकती है
    • लेकिन अगर एक instance में कोई अहम tactic मिलकर evaluation सुधर जाए, तो भी वह दूसरे instances तक propagate न होने की समस्या बनी रहती है
  • State space को directed acyclic graph(DAG) के रूप में model करने पर, कई paths जब एक ही state तक पहुँचते हैं तो उस state को एक node के रूप में represent किया जा सकता है
  • वास्तविक cycles वाले games की handling को अधिकतर अलग रखते हुए, focus इस बात पर है कि DAG में MCTS को कैसे काम करना चाहिए

Standard MCTS: execution statistics जमा करने वाला tree

  • Standard MCTS game के searched हिस्से को memory में node tree के रूप में store करता है
  • हर node आम तौर पर ये values track करता है
    • N: अब तक इस node से गुजरने या इस node पर खत्म हुए playouts की संख्या
    • Q: उन playouts द्वारा sample की गई utility values का running average
  • एक playout इस क्रम में चलता है
    • root से शुरू करके exploration formula के अनुसार next action चुनते हुए नीचे जाता है
    • किसी अभी तक unsearched state तक पहुँचने पर नया node add करता है
    • नए state की utility U प्राप्त करता है। उदाहरण neural network के value head को query करना है
    • tree में ऊपर लौटते हुए हर node का N बढ़ाता है और Q average update करता है
  • AlphaZero-style MCTS में action selection के लिए PUCT formula का उपयोग होता है
    • N(a): action a कितनी बार try किया गया है, और tree में यह उस action द्वारा pointed child node के N के बराबर होता है
    • Q(a): action a की average utility, जो child node के Q के बराबर होती है
    • PlayerToMove: current player maximize कर रहा है या minimize, यह reflect करता है
    • P(a): neural-network policy prediction जैसी prior probability
    • c_PUCT: tunable constant
  • “PUCT” predicted priors का उपयोग करने वाली Predictor UCT/UCB family से आया है, और AlphaZero variant का functional form original form से अलग है
  • आधुनिक MCTS neural-network evaluation इस्तेमाल करे तो deterministic हो सकता है, लेकिन नाम में “Monte-Carlo” पुराने तरीके से आया है जिसमें utility estimate करने के लिए random rollout अंत तक चलाए जाते थे
  • turn का computation budget खत्म होने तक playout repeat करने के बाद, root पर Q नहीं बल्कि सबसे बड़े visit count N वाला child final action के रूप में चुना जाता है
    • high Q और low N वाला child shallow search में noise से ऊँचा दिखा हुआ mistake हो सकता है
  • root की visit distribution N(a) / ΣN(b) AlphaZero training loop में policy learning target के रूप में उपयोग हो सकती है

DAG पर भोलेपन से लागू करने पर आने वाली समस्याएँ

  • Tree MCTS code को लगभग वैसा ही रखते हुए, अगर नया game state पहले से nodes_by_hash में हो तो existing node की ओर point कराया जा सकता है
  • यह तरीका tree की इस assumption को बनाए नहीं रख पाता कि child node visit count parent से चुने गए action visit count के बराबर है
  • उदाहरण स्थिति
    • Node A, node C की ओर जाने वाले action को prefer करता है, और A का Q ज्यादातर C को search करने वाले करीब 30 playouts से निर्धारित है
    • C दूसरी transposition paths से भी करीब 40 बार visit हुआ है
    • बाद में C दूसरी transposition path से और अधिक visit होता है, गहराई में tactic मिलता है और C की utility estimate 0.39 → 0.51 तक बढ़ जाती है
  • C को update करने वाला playout A से होकर नहीं गुजरा, इसलिए A का Q C के नए evaluation को reflect नहीं कर पाता
  • इसके बाद A को फिर playout मिले तो भी PUCT ज्यादा visit count वाले C के बजाय कम visit count वाले दूसरे action को explore कर सकता है
    • क्योंकि C “पहले से काफी search हो चुका” जैसा दिखता है
    • परिणामस्वरूप A का Q उल्टा घट सकता है
  • भोला graph extension, transposition path द्वारा upper preferred moves को ज्यादा visit करने पर parent को दूसरे moves अधिक explore कराने लगता है, जिससे playout average में artificial bias बन सकता है
  • यह इतना unsound algorithm बन जाता है कि infinite search में भी optimal move पर converge करेगा या नहीं, स्पष्ट नहीं रहता

सभी parents को update करने से भी समाधान नहीं होता

  • जब कोई node किसी playout से update हो, तब उस playout ने वास्तव में जिन parents से path लिया, केवल उन्हें नहीं बल्कि सभी parents और ancestors को reflect कराने का तरीका भी सोचा जा सकता है
  • यह तरीका पिछले A-C case में A की utility को साथ में update कर सकता है
  • लेकिन दूसरे उदाहरण में parent D, transposed child F की बहुत सारी visits से contaminate हो जाता है जिसे वह खुद prefer नहीं करता
    • D का best child E Q = 0.56 है, और D का Q = 0.55 इससे मेल खाता है
    • D ने F को सिर्फ एक बार search किया, लेकिन F दूसरी path से पहले ही 9 बार visit होकर कुल 10 visits की अवस्था में है
    • बाद में F दूसरी path से 100 बार और visit होकर low utility बनाए रखता है, तो all-parent update method D के Q को 0.35 तक नीचे खींच सकता है
  • D के नजरिए से वह F को इतने सारे playouts allocate नहीं करना चाहता था, इसलिए all-parent update भी policy meaning को तोड़ने वाला तरीका है

MCTS को policy optimization के रूप में देखना

  • Monte-Carlo Tree Search as Regularized Policy Optimization MCTS की machine-learning perspective से व्याख्या करता है
  • हर node पर PUCT द्वारा बार-बार चुनी गई cumulative visit distribution निम्न optimization problem के solution को approximate करती और converge करती है
π가 최대화하는 값:
Σ π(a) Q(a) - λ_N D_KL(P || π)
  • Components का अर्थ
    • Σ π(a) Q(a): policy π follow करने पर estimated expected utility
    • D_KL(P || π): prior policy P और posterior policy π के अंतर को मापने वाला reverse KL divergence
    • λ_N: KL term की strength तय करने वाला coefficient, जो visit count बढ़ने पर घटता है
  • Visit distribution को neural network की prior policy P से starting point लेकर, अधिक visits से action utility evidence जमा होने के साथ बेहतर होने वाली posterior policy के रूप में देखा जा सकता है
  • इसलिए MCTS को tree के हर node पर छोटी online policy learning साथ-साथ करने वाला algorithm माना जा सकता है
  • यह perspective बताता है कि visit distribution मजबूत agent की policy जैसी क्यों दिखती है, और AlphaZero में policy learning target के रूप में क्यों इस्तेमाल होती है
  • Optimization problem का exact solution calculate करके policy के रूप में इस्तेमाल करना भी संभव है, लेकिन व्यवहार में कम visits और संयोग से ऊँचा दिखने वाले Q वाले moves को बड़ा weight मिल सकता है
    • Visit distribution को posterior policy के रूप में इस्तेमाल करने पर, किसी move को high weight पाने के लिए वास्तव में बहुत search होना पड़ता है, इसलिए यह अधिक robust है

Q की पुनर्व्याख्या: playout average से policy expectation तक

  • Standard definition में node n का Q(n), n को visit करने वाले playouts की utility average है
Q(n) = (1 / N(n)) Σ U(p)
  • इसे child basis पर फिर लिखें तो यह इस तरह है
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
  • यहाँ U(n) node n की raw neural-network utility estimate है, और N(c) Q(c) child-wise visit count से weighted child value है
  • इसलिए Q को child Qs के visit-distribution weighted average के रूप में समझा जा सकता है
  • अगर visit distribution MCTS द्वारा optimize की जाने वाली posterior policy है, तो Q(n) उस posterior policy को follow करने पर regularized expected utility है
  • इस interpretation में हर node, children द्वारा report किए गए Q को maximize करने के लिए policy optimize करता रहता है, और अपने Q को उस policy से हासिल होने वाली expected utility के latest estimate के रूप में update करता है
  • अगर child node का Q game-theoretic optimal value पर converge करता है, तो parent की policy और Q भी recursively optimal value पर converge करते हैं

सही MCGS: edge visits और child visits को अलग करना

  • Graph में समस्या इसलिए पैदा होती है क्योंकि parent की child visit केवल उसी parent के जरिए होती है, यह assumption लगाया जाता है
  • Transposition paths होने पर child node visit count, PUCT द्वारा उस parent पर allocate किए जाने वाले visit count से arbitrarily अलग हो सकता है
  • समाधान है किसी specific node पर PUCT द्वारा चुने गए action की cumulative count को अलग से track करना
  • हर node n ये values track करता है
    • N(n): यह node कुल कितनी बार visit हुआ
    • N(n,a): node n पर PUCT ने action a कितनी बार चुना, यानी edge visit count
    • Q(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
  • यहाँ Q(n,a), action a चलकर पहुँचे child node c के Q(c) के बराबर है
  • PUCT calculation में भी child visit count नहीं, बल्कि edge visit count इस्तेमाल होता है
argmax_a PlayerToMove(n) * Q(n,a)
       + c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
  • Basic algorithm playout path के actions चुनता है, transposed state पहले से हो तो existing node को link करता है, वापस लौटते समय edge visit count बढ़ाता है और फिर N तथा Q को child values के function के रूप में recalculate करता है
  • यह तरीका Czech, Korus, Kersting के Monte-Carlo Graph Search for AlphaZero से high level पर similar है, लेकिन execution statistics नहीं बल्कि policy-optimization perspective से निकला है

Implementation choices: stale Q और update method

  • दिए गए pseudocode में केवल उन nodes को update किया जाता है जिनसे playout वास्तव में गुजरा है
  • इस वजह से जिन paths से नहीं गुजरा गया, उनके node Q stale Q हो सकते हैं
  • फिर भी theoretically यह sound है
    • PUCT जैसे standard exploration formulas limit में सभी actions को infinitely try करते हैं
    • Node दोबारा visit होने पर, उस समय के child Q और edge visit count का उपयोग करके सही Q directly calculate करता है
    • DAG में limit में game-theoretic optimal value पर converge हो सकता है
  • Stale Q search efficiency घटा सकता है
    • Immediate parent pointers रखकर parent Q भी update किए जा सकते हैं
    • सभी ancestors को topological order में update करके stale state हटाई जा सकती है
    • केवल playout path update करते हुए अलग parallel thread stale nodes ढूँढकर update कर सकता है
  • Pseudocode idempotent update का उपयोग करता है
    • पहले कोई भी intermediate update हुआ हो, node को एक बार visit करने पर children की current values के लिए N और Q सही हो जाते हैं
  • Incremental update भी संभव है, लेकिन graph में उसे equivalent या limit में equivalent बनाना ज्यादा tricky है
  • Czech आदि ने execution-statistics perspective से approach किया, इसलिए उन्होंने अधिक incremental formula इस्तेमाल किया
    • Edge visit count के साथ edge का Q भी store किया
    • Stale Q को latest value तक धीरे-धीरे catch up कराने वाला mechanism और error-tolerance hyperparameter रखा
  • दिया गया pseudocode दिखाता है कि नए error-tolerance parameter या edge Q storage के बिना भी MCGS चल सकता है
  • KataGo अभी idempotent formula का उपयोग करता है

Transposed child से playout जारी रखना है या नहीं

  • Tree MCTS में edge visit increase और child visit increase एक ही घटना हैं
  • Graph में transposition के कारण child node उस edge से पहले ही ज्यादा बार visit हो चुका हो सकता है
  • ऐसे में child node को पहले से पर्याप्त visit हुआ मानकर playout रोक सकते हैं, और सिर्फ edge visit बढ़ाने के बाद parent और ancestors update कर सकते हैं
  • रोकने के पक्ष में कारण
    • अगर edge visit कम और child visit ज्यादा है, तो उस child को extra visit देने की marginal information कम हो सकती है
  • जारी रखने के पक्ष में कारण
    • जिस node की child visit edge visit से ज्यादा है, उसके कई parents से transposition आने की संभावना ज्यादा है, और वह अधिक parents को प्रभावित करता है, इसलिए accurate evaluation important हो सकता है
  • यह choice experimentation का क्षेत्र बना हुआ है
    • जब child visit count edge visit count से काफी ज्यादा हो तभी रोकने वाला threshold method भी संभव है
  • KataGo default रूप से playout रोकता है, लेकिन जारी रखने या probabilistically कुछ हिस्से ही रोकने के config options देता है
  • Pseudocode playout नहीं रोकता, और जरूरत हो तो child.N <= edge_visits condition से एक line check जोड़ा जा सकता है

Hash, terminal nodes, real game cycles

  • Game-terminal node pseudocode में visit count से independent रूप से N = 1, U = Q = game result utility के रूप में recalculate होता है
    • Parent का corresponding edge visit count सामान्य रूप से बढ़ता है, इसलिए यह तरीका भी संभव है
    • अगर game result probabilistic है और expected utility directly calculate नहीं की जा सकती, तो terminal node की हर visit पर N बढ़ाकर sampled result का average लेना important हो सकता है
  • Game-ending utility को और व्यापक रूप से handle करके provable values को graph के ऊपर ज्यादा तेजी से propagate करना भी संभव है
    • General MCTS/MCGS में निश्चित utility values को recognize करने का mechanism नहीं होता, इसलिए जब terminal states important हों तो यह alpha-beta जैसी classical search जितनी सस्ती तरह से optimal value पर converge नहीं करता
  • Transpositions खोजने के लिए game state के unique hash की assumption है
    • Complex game state के लिए सचमुच collision-free hash बनाना tricky और महँगा हो सकता है
    • 128-bit या 192-bit का पर्याप्त बड़ा Zobrist hash, adversarially बनाए गए states न हों तो practical रूप से collisions रोकने के लिए आम तौर पर काफी होता है
    • Hash collision से cycle बनने पर infinite recursion से बचने के लिए cycle detection जोड़ा जा सकता है
  • Go के superko, chess की threefold repetition जैसे actual game rules से बनने वाले cycles की handling को detail में नहीं लिया गया है
  • 2024-03-10 appendix repetitions और cycle handling पर अधिक rough विचारों वाला Google Docs link देता है, और game-specific heuristic experiments की जरूरत हो सकती है
  • KataGo की Go handling में, किसी specific move के बाद original position पर लौटने के लिए कम से कम S + E - 1 moves लगते हैं, इस Go-specific theorem का उपयोग करके cycle-related situations में node sharing को स्थिर रूप से limit किया जाता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-03-11
Hacker News की राय

  • मुझे लगता है कि AI reasoning को आगे बढ़ाने के लिए ऐसी graph search ज़रूरी है। केवल simple LLM से कामयाबी की संभावना कम है
    लिंक में game tables के लिए Zobrist hashing https://en.wikipedia.org/wiki/Zobrist_hashing सहित कई अच्छे references हैं
    graph search की computation मात्रा explode न हो, इसके लिए language-based state descriptions के लिए अच्छी hashing ढूंढनी होगी
    tree search के संदर्भ में Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 और MCTS approach की current दूसरी reinforcement learning strategies से तुलना करने वाला Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642 भी पढ़ने लायक हैं

    • यह बहुत low-level लगता है
      एक कदम आगे बढ़ने के लिए state representation और search algorithm को साथ में सीखने वाला तरीका हो सकता है। search algorithm उस neural network के state representation पर search करे जहां से उसे cost मिल सके
      https://sites.google.com/view/genie-2024/
      DeepMind का Genie discrete states को model करने का अच्छा example है। neural network collision detection और actions सहित बेहद complex representations सीखता है। उस state को pixels में decode करने के बजाय, शायद उसी state पर सीधे search किया जा सकता है
      बेशक यह structure असल में काफी अलग हो सकता है
    • यह बहुत ज़्यादा simplified है, लेकिन explore करने लायक approach मुझे ऐसी लगती है
      logical arguments के collection को लेकर हर argument को hash देने का तरीका खोजें, और उन argument hashes को first principles के अनुसार layered Merkle tree के रूप में represent करें
      अगर कोई argument सफलतापूर्वक refute हो जाए तो उस argument का hash बदल जाता है, और lower-level arguments के hashes भी invalid हो जाते हैं
    • लगता है कि दोनों को किसी तरह combine करना असंभव नहीं होना चाहिए। यह मानना मुश्किल है कि brain हर काम के लिए सिर्फ एक technique इस्तेमाल करता है; ज़्यादा संभावना है कि कई tools हों और उनके ऊपर कोई selector हो जो तय करे कि कौन-सा tool कब इस्तेमाल करना है

  • HN URL में author देखकर तुरंत पहचान गया कि यह KataGo बनाने वाला genius है: https://github.com/lightvector/KataGo
    https://www.reddit.com/r/cbaduk/ पर उनकी posts भी लगातार शानदार होती हैं

    • URL सचमुच KataGo repository के अंदर है

  • chess का मेरा experience बहुत ज़्यादा नहीं है, लेकिन search tree में same position इतनी बार duplicate होती है कि वह important हो जाए—इस दावे पर मुझे शक है। Leela Zero से actual measurements देखना चाहूंगा
    अगर threefold repetition और 50-move rule तक state में शामिल कर दें, तो repetition की संभावना बहुत कम हो जाएगी; हालांकि मुझे लगता है कि उन चीज़ों को consider किए बिना भी यही बात लागू होती है

    • Go में ko बहुत common है। board position को exactly repeat करना legal नहीं है, लेकिन अगर tree search ko positions को ठीक से evaluate न करे, तो ऐसे situations आसानी से बनाए जा सकते हैं जहां AI bad move खेले

  • “Monte-Carlo Tree Search” नाम के उलट, ऊपर वाले algorithm में Monte Carlo बिल्कुल नहीं है और यह पूरी तरह deterministic है—यह बात अजीब लगती है। आम तौर पर implement होने वाला MCTS deterministic है, यह नहीं सोचा था; मुझे लगा sampling में randomness होती है

    • Original MCTS में randomness थी। लगता है article में भी mention है; आख़िर में position evaluate करने के लिए playouts किए जाते थे
      आज के similar projects में इसे better-quality neural network evaluation से replace कर दिया गया है। random moves खेलकर देखना कि कौन जीतता है, बहुत अच्छा तरीका नहीं है, लेकिन उस समय known best strategy यही थी
      अंततः Monte Carlo वाला part आज भी MCTS कहलाने वाली चीज़ का essential element नहीं था, बल्कि second-best था। इसलिए नाम थोड़ा unfortunate हो गया
    • Strictly speaking, यह उसी “monte carlo” नाम के तहत आने वाला एक अलग algorithm है
      दिलचस्प बात यह है कि ज़्यादातर Monte Carlo methods असली random number generator पर नहीं, बल्कि pseudorandom number generator पर निर्भर करते हैं, इसलिए same seed और input दिए जाएं तो हमेशा same result देने वाला deterministic तरीका होता है
      यह algorithm सामान्य pseudorandom generator और अलग heuristics इस्तेमाल करने के बजाय neural network से query करता है। neural network एक विशाल search space पर heuristic है, इसलिए training के आधार पर कुछ खास outcomes की ओर strongly biased बहुत खराब pseudorandom generator की तरह काम करता है, और नतीजे में heuristics applied pseudorandom generator जैसा दिखता है
      अहम बात यह है कि यह MCTS की specialization है, इसलिए technically हर use case के लिए fit नहीं है
    • अगर randomness है, तो जानना चाहूंगा कि convergence होती है या नहीं, और कितने resource-time की जरूरत होती है। CPU, RAM, GPU, TPU, QPU के हिसाब से भी यह बदल सकता है

  • MCTS investigate करते समय article में mention किया गया paper मेरी नज़र से पूरी तरह छूट गया था। अगली बार इस modified method को खुद चलाकर देखना काफी मज़ेदार होगा

  • अच्छा होगा अगर कोई simple introduction हो

    • game-playing AI बनाते समय—और broadly कहें तो लगभग सभी AI में—सबसे promising techniques में से एक tree search है। यह future moves के आधार पर current move को rank करने का तरीका है
      जिन games में same state तक कई paths से पहुंचा जा सकता है, वहां अलग-अलग branches में same state node को बार-बार record करने में बहुत memory waste हो सकती है
      यह article graph search वाले approach को अच्छी तरह examine करता है। मूल रूप से यह game state को hash करने की extra computation करता है ताकि पता चले कि node पहले visit हुआ है या नहीं, और इसके बदले memory बचाता है
      क्योंकि already seen node को फिर से record करने की ज़रूरत नहीं रहती, cycle-free tree एक directed acyclic graph में बदल जाता है
      इस वजह से correct results पाने के लिए tree search में थोड़ा बदलाव करना पड़ता है। खासकर optimization unit को vertex, यानी state, के बजाय edge, यानी action या move, के हिसाब से ज्यादा align करना पड़ता है
      यह topic को अच्छी तरह समझने वाले व्यक्ति द्वारा लिखा गया, literate programming style का एक well-written technical essay है