كل هذا هو ملكة الملكة ماب.
تنسج في اسطبلات بدة
والشعر يهدم متشابكة ...
وليام شكسبيرلقد كان
إطلاقًا طويلًا ، ولكن تم فعل الكثير.
ظهر مدير الجلسة ، مما يتيح لك التراجع عن التحركات التي تم إجراؤها عن طريق الخطأ. في بعض الأماكن ، تمت إضافة تصميم الصوت. ومع ذلك ، توصلت إلى
طريقة رائعة لدفع العديد من الخيارات البديلة للموضع الأولي في لعبة واحدة. والأهم من ذلك - وصلت أخيرًا إلى الألعاب بمعلومات غير مكتملة.
سأشرح ما هو على المحك. في ألعاب الطاولة المعتادة ، مثل
الشطرنج أو
لعبة الداما ، يتوفر للاعبين ، في أي وقت في اللعبة ، معلومات كاملة عن موقع القطع (الخاصة بهم والخصم) ، وقواعد تحريكها ، وأهداف اللعبة ، إلخ. يتم دراسة هذه الألعاب جيدًا وتقع ضمن فئة "
الألعاب ذات المعلومات الكاملة ". الآن ، تخيل أن بعض هذه المعلومات قد تكون مخفية عن اللاعب.
ضباب الحرب هو توضيح رائع للموضوع. وفقًا لقواعد "
الشطرنج الأعمى " ، لا يمكن للاعبين رؤية جميع قطع العدو ، ولكن فقط تلك التي يتم وضعها في الحقول ، والتي يمكن الوصول إليها بحركة واحدة من أي قطعة. لقد قمت بإضافة إضافتين إلى هذه القاعدة:
- بالطبع ، يرى اللاعب قطعه دائمًا ، ولكن بالمناسبة يتم عرضها - في شكل عادي أو شفاف ، يمكنه الحكم على ما إذا كان الخصم يراها.
- لأغراض التزيين فقط ، قمت بوضع "غيوم" على مناطق غير مرئية حاليًا.
بعد أن أتقنت
المبدأ العام ، انخرطت قليلاً وقمت بعمل عدد كبير من الألعاب مع "ضباب الحرب". بالإضافة إلى
لعبة الشطرنج نفسها ، لدي خيارات "مظلمة" لكل من
Xiang و
Changi و
Shatrange و
Sittuyin والعديد من الألعاب الأخرى. حتى أن هناك "
بنادق عمياء "! تشترك جميع هذه الألعاب في شيء واحد:
الكمبيوتر يغش!لم أحاول حتى إجراء تغييرات على خوارزميات الروبوتات لهذه الألعاب ، لأنني راهنت على أن الظروف غير المتكافئة تعوض جزئيًا على الأقل عن لعبتهم الضعيفة للغاية مقارنة بالبشر. كما
كتبت سابقًا ، يعد تطوير الذكاء الاصطناعي عالي الجودة لألعاب الطاولة مهمة صعبة للغاية. بالطبع ، القواعد لها استثناءات. حتى مع لعبة الروبوت الضعيفة للغاية ، سيكون من الصعب على الشخص أن يلعب
لعبة غير مألوفة ، مكتوبة حرفيا بالفخاخ. ماذا يمكننا أن نقول عن نسختها "المظلمة"
ومع ذلك ، بشكل عام ، هذا ليس نهجًا صحيحًا للغاية. أريد أن أرى بوت يمكن أن يفعل بالضبط بالبيانات التي يمتلكها خصمه - رجل. لماذا هذا مهم؟ كل شيء بسيط للغاية - بالمناسبة يلعب البوت ، أحيانًا يكون من السهل جدًا تخمين ما إذا كان يمكنه الوصول إلى المعلومات المخفية (اللمحات) أم لا. وبالطبع ، من الممتع أكثر أن يلعب الشخص مع هذا الروبوت الذي
لا يختلس النظر (اللعب مع شخص آخر هو أكثر إثارة للاهتمام ، ولكن هذه قصة مختلفة).
وهنا يجدر اختيار لعبة مختلفة قليلاً عن الشطرنج (لأنني لست مستعدًا لتطوير روبوت "أمين" ألعب الشطرنج "بشكل أعمى"). هناك الكثير من هذه الألعاب ولا يمكن القول أنها أبسط من لعبة الشطرنج أو لعبة الداما. إنهم مختلفون فقط ويتطلبون نهجًا فرديًا.
على سبيل المثالهناك لعبة أطفال واحدة لم أتمكن بعد من تطوير الروبوت. يطلق عليه "الغابة" أو
Dou Shou Qi . الهدف من اللعبة هو اختراق أراضي العدو. كل لاعب لديه "دن" - حقل مركزي في السطر الأول. إذا دخل أي من شخصيات العدو إلى العرين ، فقد فاز (لا يمكنك احتلال العرين بأرقامك الخاصة).
الأرقام مرتبة حسب الأقدمية. يتفوق الفيل على جميع الأرقام ، يليه: الأسد ، النمر ، النمر ، الكلب ، الذئب ، القط والفأر. يمكن للفأر أن يتغلب على فيل وفأر آخر ، بالإضافة إلى ذلك ، هذا هو الرقم الوحيد الذي يمكن أن يتحرك في الماء (في منتصف اللوح يوجد خزانان). يمكن للنمر والأسد القفز فوق الماء ، ولكن فقط إذا كان الجرذ لا يسد الماء. باستثناء القفزات ، تتحرك جميع الأشكال بالطريقة نفسها - إلى حقل مجاور واحد عموديًا أو أفقيًا. عرين محاط بالفخاخ. الرقم في الفخ عرضة
لأي شخصية معادية.
كما ترى ، القواعد بسيطة جدًا. ما الذي يمنع تطور روبوت لهذه اللعبة؟ بادئ ذي بدء ، الأرقام منخفضة السرعة. إذا كانت هناك تهديدات ، يمكنني أن أقدر فوائد التبادلات ، ولكن بالنسبة لمعظم اللعبة ، يتم تشغيل القطع ببساطة واحدة تلو الأخرى على مسافات طويلة إلى حد ما. لا يمكنني عرض اللعبة لعدد كبير من التحركات للأمام (بسبب القيود المفروضة على مدة حساب الحركة) ، ونتيجة لذلك تقع التغييرات خارج أفق العرض وتصبح جميع الحركات متكافئة بالنسبة لي.
بادئ ذي بدء ، قررت أن أسهب في
الحديث عن
BanQi - الشطرنج الصيني الأعمى. هذه لعبة أصلية للغاية تحتوي على معلومات مخفية ، تشبه "الغابة". من المهم بالنسبة لي أن التطورات ، فيما يتعلق بإنشاء روبوت لهذه اللعبة ، يمكن استخدامها في ألعاب أخرى ، مثل
Dou Shou Qi أو
Luzhan Qi أو
Strategyo أو حتى (ربما)
Tafl .
سأخبرك عن القواعد. يتم تشغيل اللعبة على نصف اللوحة لـ "Chess Chinese" (
Xiang Qi ) ، بينما لا يلعب التصميم الأصلي للوحة أي دور. يتم وضع القطع داخل الخلايا (كما في الخلايا التقليدية) ، وليس عند تقاطعات الخطوط (كما هو الحال في الشطرنج الصيني). في بداية اللعبة ، يتم خلط جميع القطع تمامًا ووضعها لأسفل على اللوحة (نظرًا لأن القطع التقليدية من Syants هي نوع من البراميل ، ويتوافق عددها مع عدد الحقول في نصف اللوحة ، فلا توجد صعوبة).
بعد ذلك ، يتبادل اللاعبون تحركاتهم. عند إجراء نقلة ، يمكن للاعب قلب أي قطعة مغلقة ، أو تحريك قطعة مفتوحة مسبقًا من لونه. يتم تحديد ألوان اللاعبين من خلال الخطوة الأولى. إذا تم فتح أول قطعة سوداء ، فإن اللاعب الذي فتحها سيلعب باللون الأسود. تسير جميع الأرقام في اللعبة بنفس الطريقة (باستثناء "المدفع" في النسخة التايوانية ، والتي سأناقشها لاحقًا) - على خلية واحدة متجاورة رأسيًا أو أفقيًا. يتم تحديد إمكانية الاستلام حسب ترتيب أقدمية الأرقام:
عام> مستشار> فيل> عربة> حصان> مدفع> جنديتضرب الشخصيات القديمة الأصغر سنًا أو تساويهم ، باستثناء واحد: يضرب الجندي الجنرال (وهو نوع من "
مقص ورق مقوى "). يبقى أن نقول بضع كلمات عن BanQi التايواني:
- على عكس النسخة الصينية ، في تايوان BanQi ، لا يمكن للجنرال أن يضرب جنديًا.
- يتحرك المدفع وفقًا لقواعد XiangQi ، أي إلى أي عدد من الحقول المتعامدة بسرعة منخفضة (مثل عربة) أو يضرب أي شخصية معادية ، مع قفزة عبر "النقل" ، عند تنفيذ حركة هجوم.
هناك أيضًا إصدار هونغ كونغ ، لكنه لا يختلف عمليا عن الصينيين ، باستثناء أنه تم تغيير ترتيب أقدمية الأرقام. قررت التركيز على النسخة التايوانية من القواعد ، باعتبارها الأكثر تكتيكًا إثارة للاهتمام.
ما الذي يجب أن أبحث عنه عند تطوير روبوت؟أولاً ، تبدو اللعبة بسيطة للغاية ، ولكنها ليست كذلك. حتى إذا لم تفكر في الفروق الدقيقة المرتبطة بالبنادق التايوانية ، فإن تكلفة الأرقام غير بديهية. على الرغم من أن "المستشار" يمكنه التغلب على أرقام أقل من "الجنرال" ، فهو بطل الرواية الرئيسي في اللعبة. أولاً ، لدى اللاعب مستشاران. بالإضافة إلى ذلك ، فإن جنرال عدو واحد فقط يتفوق في القوة على كل مستشار ، في حين يمكن أن يهاجم الجنرال ما يصل إلى خمسة جنود! لنفس السبب ، فإن تكلفة الجندي في اللعبة أعلى من تكلفة الجنرالات. في النهاية ، يمكنه التغلب على أقوى شخصية! يقترح الاعتبار الثاني المهم أحد الألغاز "كانتربري" لهنري دودني.
هذه مهمة نكتة أكثر من لغز كامل. يمكن أن تذهب جميع الأشكال إلى حقل مجاور واحد عموديًا أو أفقيًا. يتحرك الأبيض أولاً ، بينما يقوم كل من الأبيض والأسود دائمًا بحركتين (بقطع مختلفة)! في هذه الظروف ، لا يستطيع البامون الأيسر الإمساك بالحمار الأيسر أبدًا ، ولا يستطيع البطل الأيمن التقاط البرج الأيمن أبدًا (يمكنك التحقق منه بنفسك). بالطبع ، يمكن للمهرج الأيمن أن يمسك الحمار الأيسر دون أي صعوبة. كل شيء عن التكافؤ!
أعطتني هذه المشكلة بعض الأفكار. أولاً ، مهمة البوت ، في ألعاب مثل BanQi أو DouShouQi ، هي أولاً إيجاد أقصر مسار. من كل من القطع النشطة (الخاصة أو الخصم) ، من الضروري بناء سلاسل من التحركات إلى جميع الأهداف المحتملة (بما في ذلك القطع الخاصة بهم ، لحساب التبادلات المحتملة). بعد ذلك ، يجب تقييم السلاسل والخيارات التالية ممكنة هنا.
- الرقم المهاجم يتفوق على المهاجم - سلسلة مربحة (مكافأة) تقدر بتكلفة الرقم المهاجم (ناقص تكلفة الشخص المهاجم ، إذا كان الأخير محميًا) ، مع مراعاة طول السلسلة.
- الرقم المهاجم يتفوق على المهاجم - وليس سلسلة (عقوبة) مربحة ، تقدر بقيمة الرقم المهاجم.
- تتغلب القطع على بعضها البعض (على سبيل المثال ، فهي متساوية) - هنا يعتمد كل شيء على التكافؤ ، والسلاسل الفردية مفيدة ، ويجب اعتبارها حتى جزاءات (إذا لم تكن هناك أرقام أخرى في هذا المجال ، فإن التكافؤ سيحدد نتيجة اللعبة تمامًا).
بالطبع ، كل شيء ليس بهذه البساطة. على الأقل ، يجب أن تتذكر المسار المحدد للمدافع في BanQi في تايوان (أما بالنسبة لـ "الغابة" ، فهناك المزيد من الحالات الخاصة) ، ولكن هنا يمكنك البدء. مع مجموعة كاملة من السلاسل المقيمة ، يمكنك تقييم الحركات. يجب أن تتكون تكلفة النقل من تكلفة السلاسل (المكافأة والمجانية) ، والتي تقلل من طولها.
بادئ ذي بدء ، من المهم أن نفهم أنه من غير المحتمل أن تكون قادرة على استخدام خوارزميات
minimax بشكل فعال هنا. الحركات التي تكشف عن القطع المخفية سابقًا تغير جذريًا تقدير الموقع. نظرًا لعدم وجود معلومات حول القطع المخفية ، يكاد يكون من المستحيل عرض موقف يتحرك كثيرًا إلى الأمام. لكن كل سحابة لها بطانة فضية ، ولكن يمكننا استخدام استدلال أكثر تعقيدًا (من حيث الحساب) لتقييم التحركات نفسها!
لدي بالفعل روبوت يقوم بتقييم التحركات من خلال استدلالهم (مطلوب
للعبة ممتعة واحدة). هذه خوارزمية بسيطة للغاية. يتم تصنيف جميع التحركات بترتيب تنازلي من مجريات الأمور (يتم تجاهل التحركات ذات القيمة الإرشادية السلبية بشكل عام) ، وبعد ذلك يتم مسحها بالترتيب. إذا كانت الخطوة التالية تؤدي إلى موقف لا يوجد منه رد فعل معاد يؤدي إلى نصر فوري ، فإن البوت يعتبرها الأفضل. باستخدام هذه الخوارزمية ، لا يمكنك أن تهتم بتقدير الموقع ، ولكن عليك أن تتعرق على
الاستدلال .
بادئ ذي بدء ، نبني سلاسلvar getChains = function(design, board) { var player = board.getValue(board.player); if (player === null) return []; if (_.isUndefined(board.chains)) { board.chains = []; var pieces = getGoals(design, board); var targets = getTargets(design, board, pieces); _.each(pieces.positions, function(pos) { var goals = pieces; var f = true; var piece = board.getPiece(pos); if (piece === null) return; if (!chinese && (piece.type == 12)) { goals = targets; f = false; } var group = [ pos ]; var level = []; level[pos] = 0; for (var i = 0; i < group.length; i++) { if (_.indexOf(goals.positions, group[i]) >= 0) {
بالطبع ، أقوم بتخزين جميع البيانات الوسيطة في حالة اللعبة ، حتى لا أقرأها عدة مرات. بالإضافة إلى ذلك ، يتم استخدام خدعة واحدة هنا ، وهي مفيدة جدًا في حساب المناطق المتصلة. أقوم بالتكرار على مصفوفة
المجموعة ، ووضع عناصر إضافية بداخلها في الحلقة ، حسب الحاجة. ترتبط جميع الصعوبات بالبنادق. بالنسبة لهم ، فإن أهداف السلاسل ليست هي الأرقام نفسها ، ولكن المجالات التي يمكن مهاجمة الأخيرة منها.
يتم تقييم السلاسل تمامًا كما قلت var getChainPrice = function(design, board, attacker, attacking, len) { var player = board.getValue(board.player); if ((player === null) || (attacker == null) || (attacking === null)) return 0; if (attacker.player == attacking.player) return 0; var isAttacking = isAttacker(design, attacker.type, attacking.type); var isAttacked = isAttacker(design, attacking.type, attacker.type); if (!chinese && (attacker.type == 12)) { isAttacking = true; isAttacked = (attacking.type == attacker.type) && (len == 1); } var price = 0; var f = (len % 2 == 0); if (attacker.player != player) f = !f; if (isAttacking) { if (isAttacked) { price = f ? (len - design.price[attacker.type]) : (design.price[attacking.type] - len); } else { price = design.price[attacking.type] - len; if (f) price = (price / 2) | 0; } } else { if (isAttacked) { price = len - design.price[attacker.type]; } } return price; }
... اعتمادًا على طول السلسلة وتعادلها ، بالإضافة إلى مراعاة تكاليف الهجوم والمهاجمين. ولكن هذه ليست سوى نصف المعركة! من الضروري تقييم كل من الحركات الممكنة باستخدام السلاسل المبنية. أقدم بنية وسيطة أخرى - ترغب في تجميع البيانات المتاحة. يتكون تقييم الدورة من تقييمات للرغبات ، والتي تفي بها:
شيء من هذا القبيل var addWish = function(board, comment, price, src, dst) { if (_.isUndefined(board.wish[src])) { board.wish[src] = []; } if (_.isUndefined(dst)) dst = src; if (_.isUndefined(board.wish[src][dst])) { board.wish[src][dst] = price; } else { board.wish[src][dst] += price; } } var getWish = function(design, board) { if (_.isUndefined(board.wish)) { ... } return board.wish; } Dagaz.AI.heuristic = function(ai, design, board, move) { var wish = getWish(design, board); if (move.isSimpleMove() && !_.isUndefined(wish[ move.actions[0][0][0] ]) && !_.isUndefined(wish[ move.actions[0][0][0] ][ move.actions[0][1][0] ])) { return wish[ move.actions[0][0][0] ][ move.actions[0][1][0] ]; } return 0; }
أما بالنسبة لوظيفة
getWish نفسها ، فإن السحر يبدأ هنا (وهذا هو المكان الذي من المحتمل أن أحرث فيه أكثر من مرة). بادئ ذي بدء ، أشارك تقييم التحركات على أساس المعلومات المفتوحة وإدخال قطع جديدة في اللعبة. هذا ليس صحيحًا تمامًا ، لكني حتى الآن لا أعرف كيفية التوفيق بين هذه الآراء المتنوعة. إذا لم يتم تشكيل رغبات بناءً على معلومات مفتوحة ، فسيحاول البوت فتح أرقام جديدة (هناك أيضًا بعض الحيل هنا).
- إذا كان مدفع العدو مفتوحًا ، محاطًا بأشكال مغلقة ، فمن المنطقي فتح أحد الأشكال المجاورة له ، لأنه من المحتمل أنه سيكون قادرًا على مهاجمة البندقية ، ولن يتمكن البندقية من ضربها ، على أي حال.
- إذا كان شكلًا بخلاف المدفع مفتوحًا ، فيمكنك محاولة فتح شكل يقع من خلال "الحامل" منه ، حيث توجد فرصة أن يكون مدفعًا.
- إذا كانت هناك سلسلة هجومية من جانب العدو ، يمكن فتح إحدى القطع ، بجانب السلسلة ، لاعتراض الهجوم.
- إذا لم تتمكن من حماية الرقم ، يمكنك فتح الشكل المجاور له ، في محاولة لتقليل الموقف إلى تبادل.
بالطبع ، من المفيد تقييم احتمالية فتح شخصية معينة. var getShadow = function(design, board) { var player = board.getValue(board.player); if (player === null) return []; if (_.isUndefined(board.shadow)) { board.shadow = []; _.each(design.allPositions(), function(pos) { var piece = board.getPiece(pos); if ((piece !== null) && (piece.type < 7)) { var value = piece.type + 7; if (piece.player != player) { value = -value; } board.shadow.push(value); } }); } return board.shadow; } var isFriend = function(design, x) { return x > 0; } var isPiece = function(design, x, y) { return x == y; } var isAttacker = function(design, x, enemy) { if (x < 0) return false; if ((x == 13) && (enemy == 7)) return true; if (!chinese && (x == 7) && (enemy == 13)) return false; if (!chinese && (x == 12)) return false; return x <= enemy; } var isDefender = function(design, x, enemy, friend) { if (!isAttacker(design, x, enemy)) return false; return design.price[friend] <= design.price[enemy]; } var estimate = function(design, board, p, y, z) { var shadow = getShadow(design, board); if (shadow.length == 0) return 0; var r = 0; _.each(shadow, function(x) { if (p(design, x, y, z)) r++; }); return (100 * r) / shadow.length; }
يمكن للاعب تقييم الاحتمالات من خلال تتبع الأرقام التي انسحبت من اللعبة. من حيث المبدأ ، يمكن للبوت أن يفعل الشيء نفسه ، ولكن هناك طريقة أسهل - للنظر إلى الأرقام التي لا تزال غير مفتوحة بكميات كبيرة وتقييم احتمال فتح الرقم المطلوب بناءً على المعلومات التي تم جمعها. علاوة على ذلك ، فإن نجاح الخطوة المختارة ليس مضمونًا ، ولكن إذا كان احتمال النتيجة المواتية منخفضًا ، فلن يتم تحديد الخطوة على الإطلاق.
من حيث المبدأ ، أعطى النهج ثماره ، ولكن لا يزال هناك عمل يجب القيام به.بينما التحركات الدفاعية ليست جيدة للغاية. تلتقي بعض الشخصيات بشجاعة مع العدو الأقوى ، بدلاً من الهروب منه (على الرغم من أن الهرب في حالتهم ، كقاعدة عامة ، غير مفيد بالفعل). أيضا ، هناك صعوبات في تنسيق أعمال الشخصيات المختلفة (يمكن أن يكون هذا مفيدا من أجل "دفع" بقايا شخصيات العدو). يبدو النهج نفسه واعدًا للغاية ، ولكن لا يزال يتعين التفكير في الاستدلال.
يمكن أن يكون الاستدلال على أساس "سلاسل" التحركات مفيدًا ليس فقط في BanQi ، ولكن أيضًا في العديد من الألعاب الأخرى ، مع غلبة القطع "بطيئة الحركة" (إن لم يكن كمعيار محدد ، ثم لتقييم أولي لجودة التحركات في خوارزميات أكثر تعقيدًا ، على الأقل الأقل). هذا النهج
مطلوب بشكل خاص في تلك الألعاب التي يكون فيها استخدام خوارزميات
minimax صعبًا أو حتى مستحيلًا (مثل
Yonin Shogi ، على سبيل المثال).
بالطبع ، سأستمر في العمل على الألعاب بمعلومات غير كاملة. تظهر الصورة "
لعبة الجنرالات " الفلبينية ، غير جاهزة بعد. هذه هي أسهل لعبة من عائلة كبيرة ، بما في ذلك ألعاب مثل
LuzhanQi و
Strategyo . وبالطبع ، ما زلت أتوقع عمل روبوت عمل لـ "
الغابة "!
وبالنسبة لأولئك الذين لا يزالون يقرؤونني ، يمكنني تقديم لعبة ألغاز أخرى ممتعة بمعلومات مخفية:
لقد لعبت في طفولتي ، على آلة حاسبة قابلة للبرمجة تسمى Fox Hunt. يتم إخفاء ثمانية ثعالب بشكل عشوائي في الحقل ، والتي يجب العثور عليها باستخدام "طريقة الوخز". عند اختيار منطقة فارغة ، يتم عرض إجمالي عدد الثعالب في جميع الاتجاهات الثمانية. من المستحيل أن تخسر ، ولكن يمكنك التنافس على الحد الأدنى من النقرات. وإذا كنت تلعب باستخدام سماعات الرأس ، فقم بخفض الصوت. ربما أفرطت في ذلك مع المؤثرات الصوتية.