الذكاء الاصطناعي للعبة الطاولة: خوارزمية Minimax: 8 خطوات

2024 مؤلف: John Day | [email protected]. آخر تعديل: 2024-01-30 07:38

هل تساءلت يومًا عن كيفية صنع أجهزة الكمبيوتر التي تلعب ضدها في لعبة الشطرنج أو لعبة الداما؟ حسنًا ، لا تنظر إلى أبعد من هذا Instructable لأنه سيوضح لك كيفية إنشاء ذكاء اصطناعي بسيط ولكنه فعال (AI) باستخدام خوارزمية Minimax! باستخدام خوارزمية Minimax ، يقوم الذكاء الاصطناعي بحركات جيدة التخطيط ومدروسة (أو على الأقل يحاكي عملية التفكير). الآن ، يمكنني فقط أن أعطيك رمز الذكاء الاصطناعي الذي صنعته ، لكن ذلك لن يكون ممتعًا. سأشرح المنطق وراء اختيارات الكمبيوتر.

في هذا Instructable ، سأوجهك عبر الخطوات الخاصة بكيفية إنشاء ذكاء اصطناعي لعطيل (AKA Reversi) في الثعبان. يجب أن يكون لديك فهم متوسط لكيفية البرمجة بلغة بيثون قبل معالجة هذا المشروع. فيما يلي بعض المواقع الجيدة التي يجب النظر إليها لإعدادك لهذا Instructable: w3schools أو learnpython. في نهاية Instructable ، يجب أن يكون لديك ذكاء اصطناعي يقوم بحركات محسوبة ويجب أن يكون قادرًا على هزيمة معظم البشر.

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

لقد تعلمت كيفية إنشاء هذا الذكاء الاصطناعي من خلال برنامج صيفي في Columbia SHAPE. لقد قضيت وقتًا ممتعًا هناك ، لذا ألق نظرة على موقع الويب الخاص بهم لمعرفة ما إذا كنت مهتمًا.

الآن بعد أن خرجنا من اللوجيستيات ، فلنبدأ في البرمجة!

(أضع بضع ملاحظات في الصور لذا تأكد من إلقاء نظرة عليها)

اللوازم

هذا سهل:

1) كمبيوتر به بيئة بيثون مثل Spyder أو IDLE

2) قم بتنزيل ملفات لعبة عطيل من جيثب الخاص بي

3) تثبيت عقلك بالصبر

الخطوة 1: قم بتنزيل الملفات الضرورية

عندما تذهب إلى GitHub الخاص بي ، يجب أن ترى 5 ملفات. قم بتنزيل 5 ووضعهم جميعًا في نفس المجلد. قبل أن نقوم بتشغيل اللعبة ، افتح جميع الملفات الموجودة في بيئة سبايدر.

إليك ما تفعله الملفات:

1) othello_gui.py ينشئ هذا الملف لوحة اللعبة للاعبين للعب عليها (سواء أكان إنسانًا أم كمبيوتر)

2) othello_game.py يقوم هذا الملف بتشغيل جهازي كمبيوتر ضد بعضهما البعض بدون لوحة اللعبة ويظهر فقط النتيجة وتحريك المواضع

3) ai_template.py هذا هو المكان الذي ستضع فيه كل التعليمات البرمجية الخاصة بك لإنشاء AI الخاص بك

4) randy_ai.py هذا ذكاء اصطناعي معروض مسبقًا يختار تحركاته بشكل عشوائي

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

6) الملفات الثلاثة الأخرى: Puma.py و erika_5.py و nathan.py ، التي أنشأتها أنا و Erika و Nathan على التوالي من برنامج SHAPE ، هذه ثلاثة أنظمة AI مختلفة برموز فريدة

الخطوة 2: كيفية فتح وتشغيل Python Othello

بمجرد فتح جميع الملفات ، في الركن الأيمن السفلي من الشاشة ، اكتب "Run othello_gui.py" واضغط على Enter في IPython Console. أو في محطة Mac ، اكتب "python othello_gui.py" (بعد أن تكون في المجلد الصحيح بالطبع). ثم يجب أن تظهر لوحة على شاشتك. هذا الوضع هو وضع الإنسان مقابل وضع الإنسان. يذهب الضوء في المرتبة الثانية والظلام أولاً. انظر إلى الفيديو الخاص بي إذا كنت في حيرة من أمرك. في الجزء العلوي ، توجد درجة كل بلاطة ملونة. للعب ، انقر فوق مساحة نقل صالحة لوضع بلاطة هناك ثم أعط الكمبيوتر لخصمك الذي سيفعل الشيء نفسه ويكرر.

إذا كنت لا تعرف كيف تلعب عطيل ، فاقرأ هذه القواعد من موقع الترا بورد:

الأسود دائمًا يتحرك أولاً. يتم إجراء الحركة بوضع قرص من لون اللاعب على اللوحة في وضع "يحيط بالخارج" لواحد أو أكثر من أقراص الخصم. يتم تغليف قرص أو صف من الأقراص عندما يكون محاطًا من الأطراف بأقراص من اللون المعاكس. قد يتفوق القرص على أي عدد من الأقراص في صف واحد أو أكثر في أي اتجاه (أفقي ، رأسي ، قطري)…. (إنهاء القراءة في موقع الويب الخاص بهم)

الفرق بين اللعبة الأصلية ولعبة البايثون هذه هو أنه عندما لا توجد حركات صالحة متبقية للاعب واحد تنتهي اللعبة

الآن بعد أن أصبح بإمكانك لعب اللعبة مع صديق ، فلنصنع ذكاءً اصطناعيًا يمكنك اللعب به.

الخطوة 3: خوارزمية Minimax: توليد السيناريوهات

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

الآن كيف ستحدد الخوارزمية الحركة الأفضل؟ توقف وفكر كيف ستختار الخطوة التالية. سيختار معظم الناس الحركة التي من شأنها أن تمنحهم أكبر عدد من النقاط ، أليس كذلك؟ أو إذا كانوا يفكرون في المستقبل ، فسيختارون الخطوة التي من شأنها أن تهيئ موقفًا يمكنهم فيه كسب المزيد من النقاط. الطريقة الأخيرة في التفكير هي الطريقة التي تفكر بها خوارزمية Minimax. إنه يتطلع إلى جميع إعدادات اللوحة المستقبلية ويقوم بالخطوة التي من شأنها أن تؤدي إلى أكبر عدد من النقاط.

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

الخطوة 4: Minimax: تقييم تكوينات مجلس الإدارة

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

الآن يمكننا تعيين قيم للمواقف لكل لوحة مجلس الدولة. عندما تشغل قطعة من مركز ما ، فإنك تعطي عددًا معينًا من النقاط اعتمادًا على الموضع. على سبيل المثال ، حالة اللوحة حيث تكون قطعة AI في الزاوية ، يمكنك منح مكافأة قدرها 50 نقطة ، ولكن إذا كانت في مكان غير موات ، فقد يكون للقطعة قيمة 0. بعد مراعاة جميع قيم المناصب ، يمكنك تعيين حالة المجلس قيمة. على سبيل المثال ، إذا كان الذكاء الاصطناعي يحتوي على قطعة في الزاوية ، فيمكن أن تحصل حالة اللوحة على 50 درجة في حين أن حالة اللوحة الأخرى مع وجود قطعة الذكاء الاصطناعي في المنتصف تحصل على درجة 10.

هناك العديد من الطرق للقيام بذلك ، ولدي ثلاث طرق مختلفة لتقييم قطع اللوحة. أنا أشجعك على عمل نوع خاص بك من الكشف عن مجريات الأمور. لقد قمت بتحميل ثلاثة أنواع مختلفة من أنظمة الذكاء الاصطناعي إلى جيثب الخاص بي بواسطة ثلاثة صانعين مختلفين ، بثلاثة أساليب استكشافية مختلفة: Puma.py ، erika5.py ، nathanh.py.

الخطوة 5: خوارزمية Minimax: اختيار أفضل حركة

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

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

التعاريف: العقدة الأم - العقدة التي تنتج أو تنشئ العقد تحتها ؛ أصل العقد الأبناء - العقد التي تأتي من نفس العقدة الأم

تمثل العقد الفارغة الحركة التي سيقوم بها الذكاء الاصطناعي للوصول إلى أفضل حالة للوحة. يبدأ بمقارنة أطفال العقدة الموجودة في أقصى اليسار: 10 ، -3 ، 5. نظرًا لأن اللاعب الأكبر سينتقل ، فسيختار الحركة التي ستمنحه أكبر عدد من النقاط: 10. لذلك ، نقوم بعد ذلك باختيار وتخزين ذلك تحرك مع درجة اللوحة واكتبها في العقدة الأم. الآن بعد أن أصبح الرقم 10 في العقدة الأم ، فقد حان دور اللاعبين المصغرين. ومع ذلك ، فإن العقدة التي سنقارن بها 10 فارغة ، لذلك يتعين علينا تقييم تلك العقدة أولاً قبل أن يتمكن لاعب التصغير من الاختيار. لذا نعود إلى الدور الأقصى للاعب ونقارن بين أبناء العقدة المجاورة: 8 ، -2. التعظيم سيختار 8 ونكتب ذلك في العقدة الأصلية الفارغة. الآن بعد أن انتهت الخوارزمية من ملء المساحات الفارغة لأطفال العقدة الموجودة فوقها ، يمكن للاعب التصغير مقارنة هؤلاء الأطفال - 10 و 8 واختيار 8. ثم تكرر الخوارزمية هذه العملية حتى يتم ملء الشجرة بأكملها. في نهاية هذا المثال ، لدينا النتيجة 8. هذه هي أعلى حالة للوحة يمكن أن يلعبها الذكاء الاصطناعي بافتراض أن الخصم يلعب على النحو الأمثل. لذلك سيختار الذكاء الاصطناعي الخطوة الأولى التي تؤدي إلى حالة اللوحة الثامنة ، وإذا لعب الخصم على النحو الأمثل ، فيجب أن يلعب الذكاء الاصطناعي جميع الحركات للوصول إلى حالة اللوحة 8. (اتبع الملاحظات الموجودة على صوري)

أعلم أن هذا كان كثيرًا. إذا كنت من تلك الأنواع التي تحتاج إلى أن يتحدث معك شخص ما لفهم شيء ما ، فإليك بعض مقاطع الفيديو التي شاهدتها لمساعدتي في فهم الفكرة الكامنة وراء هذا: 1 ، 2 ، 3.

الخطوة 6: خوارزمية Minimax: Pseudocode

بعد أن تفهم المنطق وراء خوارزمية minimax ، ألق نظرة على هذا الرمز الزائف (الوظائف العامة لجميع الرموز) من ويكيبيديا:

الدالة minimax (العقدة ، العمق ، maximizingPlayer) هي

إذا كان العمق = 0 أو العقدة هي عقدة طرفية إذن

إرجاع القيمة الاستكشافية للعقدة

إذا تعظيم لاعب ثم

القيمة: = −∞

لكل طفل من العقدة تفعل

القيمة: = max (value، minimax (child، deep - 1، FALSE))

قيمة الإرجاع

else (* تصغير المشغل *)

القيمة: = + ∞

لكل طفل من العقدة تفعل

القيمة: = min (value، minimax (child، deep - 1، TRUE))

قيمة الإرجاع

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

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

الخطوة 7: صنع الذكاء الاصطناعي الخاص بك باستخدام Ai_template.py

قبل إلقاء نظرة على كود Minimax AI الخاص بي ، حاول محاولة إنشاء AI الخاص بك باستخدام ملف ai_template.py والشفرة الزائفة التي تحدثنا عنها في الخطوة الأخيرة. هناك وظيفتان في قالب ai تسمى: def minimax_min_node (لوحة ، لون) و def minimax_max_node (لوحة ، لون). بدلاً من أن تستدعي الدالة minimax نفسها بشكل متكرر ، لدينا وظيفتان مختلفتان ، تستدعي كل منهما الأخرى. لإنشاء استكشافية لتقييم حالات اللوحة ، سيتعين عليك إنشاء وظيفتك الخاصة. هناك وظائف معدة مسبقًا في ملف othello_shared.py يمكنك استخدامها لبناء الذكاء الاصطناعي الخاص بك.

بمجرد حصولك على الذكاء الاصطناعي الخاص بك ، حاول تشغيله ضد randy_ai.py. لتشغيل جهازي ais مقابل بعضهما البعض ، اكتب "python othello_gui.py (أدخل اسم ملف ai).py (أدخل اسم الملف).py" في محطة mac أو اكتب "run othello_gui.py (أدخل اسم ملف ai).py (أدخل اسم الملف).py "وتأكد من أنك في الدليل الصحيح. أيضًا ، انظر إلى الفيديو الخاص بي لمعرفة الخطوات الدقيقة.

الخطوة الثامنة: حان الوقت لتقاتل منظمة العفو الدولية

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