8

मैं एक वितरित गो/गोमोकू बॉट लिख रहा हूं।कोई भी वितरित समानांतर पेड़ खोज एल्गोरिदम सुझाव?

असल बिंदु कई कंप्यूटरों पर पेड़ खोज वितरित करने के लिए है। मूल पेड़ खोज एल्गोरिदम के साथ डीएफएस की तरह यह बहुत आसान होगा, क्योंकि मैं केवल खोज स्थान को subtrees में विभाजित कर सकता हूं। हालांकि मैं अल्फा-बीटा छंटनी के साथ मिनी-मैक्स की तरह कुछ और अधिक कुशलता प्राप्त करना चाहता हूं - लेकिन मेरी समझ से यह किसी भी तरह की साझा स्मृति के बिना काफी व्यर्थ है। तो मैं फंस गया हूँ।

कोई भी विचार क्या एल्गोरिथ्म मैं इस्तेमाल कर सकते हैं कि कुशल है और आसानी से वितरित? और सबसे महत्वपूर्ण बात यह है कि, मुझे इसके लिए कुछ (छद्म) कोड कहां मिल सकता है या शायद कार्यान्वयन?

धन्यवाद,

उत्तर

6

आप के बारे में मोंटे कार्लो ट्री खोजें अप पढ़ने की जरूरत नहीं है क्योंकि यह स्वाभाविक आसान है वितरित करने के लिए (यह न तो आसान है और न ही कठिन है एक और वृक्ष खोज की तुलना में), लेकिन क्योंकि यह कला की स्थिति है और समस्या पर काम करने वाले लोग उस एल्गोरिदम के वितरित संस्करण पर काम कर रहे हैं।

आप एक वितरित एल्गोरिथ्म बनाने की मुसीबत के लिए जा रहे हैं, तो वहाँ एक कम एक के साथ शुरू करने के लिए कोई कारण नहीं है। जब तक कि आप शैक्षणिक कारणों के लिए एक वितरित एल्गोरिदम नहीं बना रहे हैं, इस मामले में, आगे बढ़ें, मूल एल्गोरिदम वितरित करने के प्रयोग में कुछ गहराई से शैक्षिक होगा और यह गैर-वितरित अत्याधुनिक एल्गोरिदम से भी बदतर प्रदर्शन करेगा :)

Some slides

MoGo homepage

Wikipedia page on computer go में "हाल के घटनाक्रमों" अनुभाग देखें।

+0

वैसे यह आशाजनक लग रहा है, इसमें देखेंगे। धन्यवाद। – kurczak

+0

उत्कृष्ट समाधान! – user262976

1

DDS* और ABDADA 2 वितरित/समानांतर अल्पमहिष्ठ एल्गोरिदम हैं। कुछ संचार आवश्यक है, लेकिन यह कुछ परिणामों को नियंत्रक को वापस रिले करके किया जा सकता है।

आसान दृष्टिकोण के रूप में आप होगा मानचित्र की तरह कुछ अलग खोज के पेड़ों की जड़ें को कम उल्लेख किया है।

@Pascal Cuoq rightly mentions के रूप में, मोंटे कार्लो ट्री खोजें जाओ में राज्य के अत्याधुनिक है।

यहाँ आप MoGo के खोज एल्गोरिदम का एक अच्छा विवरण और कैसे पा सकते हैं अपने parallelized:

http://www.lri.fr/~gelly/paper/nips_exploration_exploitation_mogo.pdf

नोड्स जो बेहतर परिणाम यादृच्छिक नाटक पर आधारित के साथ बाहर खेल रहे हैं और अधिक गहराई से पता लगाया जाता है। प्रत्येक चरण में एक-प्लाई विस्तार के लिए एक पत्ता नोड का चयन किया जाता है। यह प्रत्येक मशीन को विस्तार करने के लिए एक अलग पत्ता चुनकर वितरित किया जा सकता है।

मोंटे कार्लो पेड़ खोज का एक अच्छा सिंहावलोकन यहाँ है:

http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf

+0

धन्यवाद, ABDADA पहली नज़र पर भी ठीक लग रहा है। – kurczak

2

प्रयास करें मानचित्र दृष्टिकोण को कम करें। उदाहरण के लिए, को देखने के

Breadth-First Search (BFS) & MapReduce

+0

मैं वास्तव में समझ नहीं सकता कि यह किसी भी तरह से डीएफएस से बेहतर कैसे हो सकता है। – kurczak

+0

मेरा मतलब यह नहीं है कि बीएफएस किसी भी तरह से डीएफएस से बेहतर है। यह एक खोज समस्या के लिए मानचित्र कम करने का एक उदाहरण है। –

संबंधित मुद्दे