شجرة اللعبة

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة
يوضح الرسم التخطيطي المستويين الأولين، أو ما يُعرفان بالطبقتين ، في شجرة لعبة إكس-أو . تكون دورانات وانعكاسات المواقع متكافئة، لذا يمتلك اللاعب الأول ثلاثة خيارات للحركة: في المنتصف، أو على الحافة، أو في الزاوية. يمتلك اللاعب الثاني خيارين للرد إذا لعب اللاعب الأول في المنتصف، وإلا فلديه خمسة خيارات. وهكذا.

في سياق نظرية الألعاب التوافقية ، تُعرَّف شجرة اللعبة بأنها رسم بياني يمثل جميع حالات اللعبة الممكنة ضمن لعبة متسلسلة ذات معلومات كاملة . وتشمل هذه الألعاب الشطرنج ، والداما ، ولعبة غو ، ولعبة إكس أو .

يمكن استخدام شجرة اللعبة لقياس تعقيد اللعبة ، إذ تمثل جميع الطرق الممكنة لتطورها. ونظرًا لكبر حجم أشجار الألعاب المعقدة كالشطرنج، تستخدم الخوارزميات المصممة لهذا النوع من الألعاب أشجارًا جزئية، مما يجعل الحساب ممكنًا على الحواسيب الحديثة. توجد طرق متنوعة لحل أشجار الألعاب. فإذا أمكن توليد شجرة كاملة، يمكن استخدام خوارزمية حتمية ، كالاستقراء العكسي أو التحليل الرجعي . أما في حال تعذر توليد شجرة كاملة، فيمكن استخدام خوارزميات عشوائية وخوارزميات الحد الأدنى والحد الأقصى ، مثل خوارزمية مونت كارلو للبحث عن الشجرة (MCTS) .

فهم شجرة اللعبة

لفهم شجرة اللعبة بشكل أفضل، يمكن اعتبارها أسلوبًا لتحليل الألعاب التنافسية، والتي تحدد الإجراءات التي يتخذها اللاعب للفوز. في نظرية الألعاب، شجرة اللعبة عبارة عن رسم بياني موجه، حيث تمثل عقدها مواقع في اللعبة (مثل ترتيب القطع في لعبة لوحية)، وتمثل حوافها الحركات (مثل نقل القطع من موقع إلى آخر على اللوحة). [ 1 ]

شجرة اللعبة الكاملة هي شجرة اللعبة التي تبدأ من الوضع الابتدائي وتحتوي على جميع الحركات الممكنة من كل وضع؛ وهي نفس الشجرة المُستمدة من تمثيل اللعبة ذي الشكل الموسع . وبشكل أدق، تُعدّ اللعبة الكاملة معيارًا للعبة في نظرية الألعاب، حيث تُعبّر بوضوح عن العديد من الجوانب المهمة. على سبيل المثال، تسلسل الإجراءات التي قد يتخذها أصحاب المصلحة، وخياراتهم عند كل نقطة قرار، ومعلومات حول الإجراءات التي يتخذها أصحاب المصلحة الآخرون عندما يتخذ كل صاحب مصلحة قرارًا، وفوائد جميع نتائج اللعبة الممكنة. [ 2 ]

The number of leaf nodes in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 255,168 leaf nodes.

Game trees are important in artificial intelligence because one way to pick the best move in a game is to search the game tree using any of numerous tree search algorithms, combined with minimax-like rules to prune the tree. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are much too large to search. Instead, a chess-playing program searches a partial game tree: typically as many plies from the current position as it can search in the time available. Except for the case of "pathological" game trees[3] (which seem to be quite rare in practice), increasing the search depth (i.e., the number of plies searched) generally improves the chance of picking the best move.

Two-person games can also be represented as and-or trees. For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.

Solving game trees

Deterministic algorithm version

An arbitrary game tree that has been fully colored

With a complete game tree, it is possible to "solve" the game – that is to say, find a sequence of moves that either the first or second player can follow that will guarantee the best possible outcome for that player (usually a win or a tie). The deterministic algorithm (which is generally called backward induction or retrograde analysis) can be described recursively as follows.

  1. Color the final ply of the game tree so that all wins for player 1 are colored one way (Blue in the diagram), all wins for player 2 are colored another way (Red in the diagram), and all ties are colored a third way (Grey in the diagram).
  2. Look at the next ply up. If there exists a node colored opposite as the current player, color this node for that player as well. If all immediately lower nodes are colored for the same player, color this node for the same player as well. Otherwise, color this node a tie.
  3. Repeat for each ply, moving upwards, until all nodes are colored. The color of the root node will determine the nature of the game.

The diagram shows a game tree for an arbitrary game, colored using the above algorithm.

عادة ما يكون من الممكن حل لعبة (بالمعنى التقني لـ "حل") باستخدام مجموعة فرعية فقط من شجرة اللعبة، لأنه في العديد من الألعاب لا يلزم تحليل حركة ما إذا كانت هناك حركة أخرى أفضل لنفس اللاعب (على سبيل المثال، يمكن استخدام تقليم ألفا-بيتا في العديد من الألعاب الحتمية).

تُعرف أي شجرة فرعية يمكن استخدامها لحل اللعبة باسم شجرة القرار ، وتُستخدم أحجام أشجار القرار ذات الأشكال المختلفة كمقاييس لتعقيد اللعبة . [ 4 ]

نسخة الخوارزميات العشوائية

يمكن استخدام الخوارزميات العشوائية في حل أشجار الألعاب. يتميز هذا النوع من التطبيقات بميزتين رئيسيتين: السرعة والتطبيق العملي. فبينما يمكن حل أشجار الألعاب باستخدام طريقة حتمية في زمن O ( n ) ، فإن الخوارزمية العشوائية التالية لها زمن تشغيل متوقع قدره θ ( n ) ≤ 0.792 إذا كانت درجة كل عقدة في شجرة اللعبة 2. علاوة على ذلك، فهي عملية لأن الخوارزميات العشوائية قادرة على "إحباط الخصم"، أي أن الخصم لا يستطيع التغلب على نظام أشجار الألعاب بمعرفة الخوارزمية المستخدمة في حل شجرة اللعبة لأن ترتيب الحل عشوائي.

فيما يلي تطبيق لخوارزمية حل شجرة اللعبة العشوائية: [ 5 ]

دالة gt_eval_rand ( u ) -> bool : """تُرجع القيمة True إذا كانت نتيجة تقييم هذه العقدة هي الفوز، وإلا تُرجع القيمة False"" " إذا كانت u.leaf : تُرجع u.win وإلا : random_children = ( gt_eval_rand ( child ) for child in random_order ( u.children ) ) إذا كانت u.op == " OR " : تُرجع any ( random_children ) إذا كانت u.op == " AND " : تُرجع all ( random_children )

تعتمد الخوارزمية على فكرة " الدائرة القصيرة ": إذا تم اعتبار العقدة الجذرية عامل " أو "، فبمجرد العثور على قيمة صحيحة واحدة ، يتم تصنيف الجذر على أنه صحيح ؛ وعلى العكس من ذلك، إذا تم اعتبار العقدة الجذرية عامل " و "، فبمجرد العثور على قيمة خاطئة واحدة ، يتم تصنيف الجذر على أنه خاطئ .

[ 6 ]

انظر أيضاً

مراجع

  1. ↑ زوكرمان، إينون؛ ويلسون، براندون؛ ناو، دانا س. (2018). "تجنب خلل شجرة اللعبة في البحث التنافسي ثنائي اللاعبين" . الذكاء الحسابي . 34 (2): 542-561 . doi : 10.1111/coin.12162 . ISSN 1467-8640 . S2CID 46926187 .  
  2. ↑ هوانغ، زيشو؛ يو، هانغ؛ تشو، شيانغيانغ؛ بنغ، تشنوي (2018-05-01). "نموذج تحسين جديد قائم على شجرة اللعبة لأنظمة تحويل الطاقة المتعددة" . الطاقة . 150 : 109-121 . Bibcode : 2018Ene...150..109H . doi : 10.1016/j.energy.2018.02.091 . ISSN 0360-5442 . 
  3. ↑ ناو، دانا (1982). "دراسة لأسباب الأمراض في الألعاب". الذكاء الاصطناعي . 19 (3): 257-278 . doi : 10.1016/0004-3702(82)90002-9 .
  4. ↑ فيكتور أليس (1994). البحث عن حلول في الألعاب والذكاء الاصطناعي (ملف PDF) . أطروحة دكتوراه، جامعة ليمبورغ، ماستريخت، هولندا. ISBN 90-900748-8-0.
  5. ↑ دانيال روش (2013). SI486D: العشوائية في الحوسبة، وحدة أشجار الألعاب . الأكاديمية البحرية الأمريكية، قسم علوم الحاسوب. مؤرشف من الأصل بتاريخ 8 مايو 2021. تم الاطلاع عليه بتاريخ 29 أبريل 2013 .
  6. ↑ بيكار، ليبور؛ ماتوشو، راديك؛ أندرلا، جيري؛ ليتشمانوفا، مارتينا (سبتمبر 2020). "مراجعة لأبحاث لعبة كالاه واقتراح خوارزمية استدلالية حتمية جديدة مقارنة بحلول البحث الشجري واتخاذ القرار البشري" . المعلوماتية . 7 (3): 34. doi : 10.3390/informatics7030034 . hdl : 10084/142398 .

للمزيد من القراءة