Monte Carlo graph search के मूल सिद्धांत
- Monte Carlo tree search (MCTS) को tree के बजाय directed graph पर लागू करने वाला "Monte Carlo graph search" ("MCGS") कभी-कभी लागू करना कठिन माना जाता है.
- मौजूदा शैक्षणिक संदर्भ tree के लिए MCTS की "standard" व्याख्या का अनुसरण करते हैं, इसलिए इसे graph तक सामान्यीकृत करना वैचारिक रूप से समझना कठिन होता है.
- यह दस्तावेज़ एक अधिक सहज मानी जाने वाली, मूलतः समतुल्य लेकिन अधिक साफ़-सुथरी व्याख्या प्रस्तुत करता है, और यह निकालता है कि graph search को इस तरह क्यों काम करना चाहिए, वह भी मूल सिद्धांतों से.
परिचय / पृष्ठभूमि
- game tree search या अन्य tree search अनुप्रयोगों में, एक ही state तक पहुँचने वाली कई संभावित moves या actions की sequences मिल सकती हैं.
- उदाहरण के लिए, chess में
1. d4 d5 2. Nf3 उसी position तक ले जाता है जिस तक 1. Nf3 d5 2. d4 ले जाता है.
- जब game में ऐसी स्थितियाँ संभव होती हैं, तो search depth के साथ संभावित मामलों की संख्या geometric रूप से बढ़ती है, जिससे deep search आवश्यक से अधिक महँगी हो जाती है.
- आदर्श रूप से, हम चाहेंगे कि search की ऐसी branches computation साझा करें.
- लेकिन standard MCTS implementation game को branching tree की तरह मानती है और tree के भीतर duplicate positions को अक्षम रूप से दोबारा search करती है.
MCTS की सामान्य व्याख्या - running statistics का tree
- MCTS को अक्सर ऐसे algorithm के रूप में समझाया जाता है जो tree के nodes से होकर गुजरने वाले playouts की running statistics को track करता है.
- हर node game की एक single state को दर्शाता है, और visit count (N) तथा playouts द्वारा sampled utility values के running average (Q) को track करता है.
- MCTS की एक single iteration या playout में tree के नीचे जाते हुए आगे search करने के लिए अगला action sample करना, नई state पर पहुँचने पर tree का विस्तार करना, नई state की utility U का अनुमान लगाना, और फिर tree में ऊपर लौटते हुए हर node पर N बढ़ाना तथा sampled नई utility U के साथ average Q को update करना शामिल होता है.
graph में क्या ग़लत हो जाता है?
- ऊपर के algorithm को tree के बजाय directed acyclic graph पर जैसा-का-तैसा लागू करने पर algorithm गलत हो सकता है.
- ऐसा इसलिए है क्योंकि MCTS को multi-armed bandit आधारित method के विस्तार के रूप में playouts की running statistics के संदर्भ में आम तौर पर समझाया जाता है.
- Czech, Korus, Kersting ने इस समस्या का समाधान किया और एक sound algorithm तक पहुँचे, लेकिन online policy learning के दृष्टिकोण से MCTS को देखने का एक वैकल्पिक तरीका भी है.
- इस वैकल्पिक व्याख्या में graph तक सामान्यीकरण अपेक्षाकृत स्वाभाविक रूप से सामने आता है.
MCTS को regularized policy optimization के रूप में फिर से देखना
- जब MCTS अलग-अलग nodes पर statistics update करता है, तो वह वास्तव में online policy learning का एक रूप चला रहा होता है.
- MCTS का visit distribution, neural network की prior policy P को क्रमिक रूप से सुधारकर expected utility को अधिकतम करने वाली "posterior" policy का लगभग प्रतिनिधित्व करता है.
सही Monte Carlo graph search करना
- MCTS को graph तक बढ़ाने पर आने वाली सारी समस्याएँ इस धारणा से उत्पन्न होती हैं कि child node की visits केवल parent node से ही आती हैं.
- सिद्धांत यह सुनिश्चित करता है कि PUCT द्वारा चुनी गई cumulative action counts एक posterior policy प्रदान करती हैं जो optimized policy π का approximation होती है, इसलिए इसी को track किया जाना चाहिए.
- यदि उस व्याख्या का उपयोग करें जिसमें node द्वारा report किया गया Q value posterior policy का expected value है, तो individual playouts की गणना कैसे की जाए इस पर चर्चा किए बिना recursive Q formula लागू किया जा सकता है.
implementation choices पर चर्चा
- इस दस्तावेज़ में प्रस्तुत algorithm, Czech, Korus, Kersting के algorithm से बहुत मिलता-जुलता है, लेकिन इसमें कुछ implementation choices और कुछ मामूली अंतर हैं.
- implementation को सरल रखने के लिए कई विकल्प चुने जा सकते हैं, जैसे Q values की "staleness" कम करने की रणनीतियाँ, या incremental के बजाय समान updates का उपयोग करना.
GN⁺ की राय
- यह लेख Monte Carlo graph search (MCGS) की जटिलता और उसे समझने के लिए एक नया दृष्टिकोण प्रस्तुत करके artificial intelligence और game theory में रुचि रखने वाले लोगों को आकर्षित कर सकता है.
- MCTS जैसे algorithms chess और Go जैसे जटिल strategy games में महत्वपूर्ण भूमिका निभाते हैं, और ऐसे games के लिए AI के विकास में योगदान देते हैं.
- हालाँकि, इस लेख की सामग्री entry-level software engineers के लिए कुछ कठिन हो सकती है और इसके लिए सैद्धांतिक पृष्ठभूमि की जानकारी चाहिए.
- MCGS को implement करते समय जिन बातों पर विचार करना चाहिए, उनमें algorithm की efficiency और accuracy के बीच संतुलन कैसे रखा जाए, यह शामिल है; इसका वास्तविक game environments में performance पर बड़ा प्रभाव पड़ सकता है.
- समान कार्यक्षमता देने वाले अन्य projects या products में DeepMind का AlphaZero शामिल है, जिसने chess, Go, और shogi में मानव शीर्ष खिलाड़ियों से आगे का स्तर हासिल किया है.
1 टिप्पणियां
Hacker News राय
ग्राफ सर्च AI की reasoning प्रगति के लिए ज़रूरी है, और सिर्फ़ साधारण LLMs इससे नाकाम रहेंगे। लिंक में game tables के लिए Zobrist hashing सहित बहुत-सी अच्छी reference सामग्री है। language-based state descriptions के लिए अच्छी hashing ढूँढ़नी होगी ताकि graph search computationally विस्फोटक न हो जाए। tree search पर अच्छी पढ़ाई के लिए 'Thinking Fast and Slow' और 'Teaching Large Language Models to Reason with Reinforcement Learning' हैं, जो MCTS approach की तुलना दूसरी मौजूदा RL strategies से करते हैं.
HN URL से ही मैं KataGo के प्रतिभाशाली developer को पहचान गया। Reddit पर उसके cbaduk पोस्ट लगातार बेहतरीन होते हैं।
"Monte-Carlo Tree Search" नाम के बारे में, पाठकों को ध्यान देना चाहिए कि बताए गए algorithm में "Monte-Carlo" जैसा कुछ नहीं है और यह पूरी तरह deterministic है। यह अजीब है कि MCTS आम तौर पर deterministic तरीके से implement किया जाता है। मैंने माना था कि sampling में randomness होती है।
MCTS का अध्ययन करते समय यह उद्धृत paper मेरी नज़र से पूरी तरह छूट गया था। अगली बार इस modification को आज़माना बहुत मज़ेदार होगा।
पृष्ठभूमि ज्ञान: