الجزء الأول (تحليل الكود) هنا:
https://habr.com/post/420725/ .
خوارزمية
الوصف
تقوم الخوارزمية باستمرار بالخطوات التالية:
- ينتظر حتى يتم إنشاء tetrimino جديد.
- للتحقق من نوع tetrimino الذي تم إنشاؤه حديثًا ، ونوع tetrimino التالي (الشكل في حقل المعاينة) ومحتويات الملعب.
- يستكشف كل الطرق الممكنة لإضافة اثنين من tetriminos إلى الملعب ويقيم كل احتمال.
- تحريك tetrimino الذي تم إنشاؤه حديثًا بحيث يتطابق مع موقع أفضل الاحتمال المكتشف.
يتم وصف كل من هذه الخطوات بالتفصيل أدناه.
قفل البحث
ضع في اعتبارك إصدارًا مبسطًا من Tetris ، حيث لا تقع الأشكال تلقائيًا. الطريقة الوحيدة لإسقاط الرقم هي خفضه برفق. بعد إزالة التوقيتات من اللعبة ، يمكننا وصف حالة tetrimino النشطة بشكل كامل من خلال موقعها واتجاهها. يحتوي الشكل على مكان معروف للإنشاء الأولي ، ويتم استخدام العمليات التالية للتحويل من حالة إلى أخرى:
- خطوة واحدة للأسفل
- تركت خطوة واحدة
- انقل خطوة واحدة إلى اليمين
- أدر خطوة واحدة عكس اتجاه عقارب الساعة
- دوران في اتجاه عقارب الساعة
هذه العمليات قابلة للتطبيق فقط عندما تتوافق مربعات tetrimino الناتجة مع الخلايا الفارغة في الملعب. عندما يكون من المستحيل التحرك خطوة واحدة إلى أسفل ، تعتبر الدولة محظورة. ومع ذلك ، نظرًا لأننا قمنا بتبسيط Tetris وانتظار القفل بشكل أساسي لا نهائي ، يمكن تحويل الحالة المقفلة بشكل أكبر من خلال عمليات أخرى عن طريق الانزلاق والتمرير.
يمكن العثور على العديد من الحالات المحظورة مع الحد الأدنى من العمليات التي تنشئها باستخدام البحث الأول (BFS). كما هو موضح أدناه ، فإنه يستخدم قائمة انتظار لتخزين النتائج الوسيطة.
- ننتظر الدولة عند الخلق.
- نستنتج شرط من قائمة الانتظار.
- نحصل على الحالات التالية باستخدام عملية التحويل.
- إذا لم تكن هناك حركة هبوطية بينهما ، فسيتم حظر الحالة التي تمت إزالتها من قائمة الانتظار.
- نضع في قائمة انتظار الحالات اللاحقة التي لم نقم بزيارتها بعد.
- إذا لم تكن قائمة الانتظار فارغة ، كرر من الخطوة 2.
يمثل البرنامج كل حالة ككائن مع الحقول التالية:
{ x, y, rotation, visited, predecessor }في عملية التحضير ، ينشئ البرنامج مجموعة ثلاثية الأبعاد من كائنات الحالة (20 صفًا × 10 أعمدة × 4 أدوار) ، وتهيئة
x و
y rotation وفقًا لذلك.
يتم تمييز الحقل الذي
visited عند وضع الدولة في قائمة الانتظار. في BFS ، يكون هذا صحيحًا لأن كل حالة لاحقة تزيد من إجمالي طول المسار بمقدار 1. وهذا يعني أنه من خلال زيادة طول المسار ، من المستحيل إنشاء حالة لاحقة تحتاج إلى إدراجها في مكان آخر غير نهاية قائمة الانتظار للحفاظ على النظام.
يشير الحقل
predecessor إلى كائن الحالة الذي اشتقت منه الحالة الحالية. يتم تعيينه عندما يتم وضع الدولة في قائمة الانتظار. دولة الخلق ليس لها حالات سابقة.
يتم تحديد مجموعة الحالات المحظورة التي تم اكتشافها أثناء البحث من خلال نوع tetrimino والكتل المعبأة في الملعب. يمكن توضيح تسلسل التحركات التي تم إنشاؤها (بالترتيب العكسي) باتباع الروابط
predecessor إلى حالة الإنشاء. عندما يتم تعيين
PLAY_FAST الثابت على
true في بداية البرنامج ، فإنه يتخطى الحالات السابقة تمامًا عن طريق وضع tetrimino مباشرة في الحقل وحظره.
يتم تجميع مجموعة ثلاثية الأبعاد من كائنات الحالة وقائمة انتظار و BFS في فئة. لديه طريقة بحث تستقبل الملعب (صفيف ثنائي الأبعاد) ، ونوع tetrimino والمستمع. في كل مرة يتم الكشف عن حالة قفل ، يتم تحديث الملعب عن طريق إضافة tetrimino إلى الموقع المناسب. بعد ذلك ، يتم نقل الملعب المتغير مع معلومات حول التغييرات إلى المستمع للمعالجة. بعد انتهاء المستمع من العودة ، يتم استعادة الملعب.
يستخدم المستمع لدمج العديد من عمليات البحث في سلسلة ، مما يجعل من الممكن العثور على جميع الطرق الممكنة لإضافة اثنين (أو أكثر) من tetriminos إلى الملعب. يقوم محرك البحث الأول في السلسلة بتنفيذ BFS مرة واحدة فقط. ومع ذلك ، يقوم محرك البحث الثاني بتنفيذ BFS في كل مرة يكتشف فيها البحث الأول حالة قفل. وهكذا ، إذا كانت هناك محركات بحث أخرى في السلسلة.
يقوم مستمع محرك البحث الأخير بتقييم الملعب المتغير. عندما يجد مجال اللعب أفضل مما تم التحقيق فيه سابقًا ، يكتب الكائن المستخدم للحالة المقفلة ، والذي يستخدم في الوقت الحالي أول محرك بحث في السلسلة. نظرًا لأن محرك البحث الأول ينفذ BFS مرة واحدة فقط ، تظل الحقول
predecessor لكائنات حالته صالحة حتى الانتهاء من عملية البحث بأكملها. أي أن المستمع الأخير يسجل بشكل أساسي المسار الذي يجب أن يسلكه tetrimino الأول للوصول إلى أفضل تكوين في الملعب نتيجة لذلك.
دالة التقييم
تقوم وظيفة التسجيل بتعيين قيمة لمجال اللعب المتغير - وهو مجموع مرجح لمعلمات التأثير المختلفة. تعتمد وظيفة التقييم المستخدمة في هذه الحالة على الوظيفة التي طورها
إسلام العشي . يستخدم المعلمات التالية:
- العدد الإجمالي للصفوف التي تم مسحها : هذا هو العدد الإجمالي للصفوف التي سيتم مسحها بإضافة اثنين من tetriminos.
- إجمالي ارتفاع الحجب : ارتفاع الحجب هو الارتفاع فوق أرضية الملعب حيث يتم قفل الشكل. هذه هي المسافة العمودية التي قد يسقطها الرقم المقفل إذا قمت بإزالة جميع المربعات المشغولة الأخرى من ملعب اللعب والحفاظ على اتجاه الشكل. إجمالي ارتفاع الحجب هو مجموع ارتفاعات الحجب لل tetriminos.
- العدد الإجمالي لخلايا "البئر" : خلية البئر هي خلية فارغة تقع فوق كل الخلايا المشغولة في عمود بحيث يكون جيرانها الأيمن والأيسر خلايا مشغولة ؛ عند تحديد الآبار ، تعتبر جدران الملعب خلايا مشغولة. الفكرة هي أن البئر عبارة عن هيكل مفتوح في الأعلى ، مغلق في الأسفل ومحاطة بجدران على كلا الجانبين. يعني احتمال وجود فجوات متقطعة في جدران البئر أن خلايا البئر لا تحدث بالضرورة في كومة مستمرة داخل العمود.
- العدد الإجمالي للثقوب في الأعمدة : الثقب في العمود عبارة عن خلية فارغة تقع مباشرة أسفل الخلية المشغولة. لا يتم مقارنة جنس الملعب مع الخلية الموجودة فوقه. لا توجد ثقوب في الأعمدة الفارغة.
- إجمالي عدد الانتقالات في الأعمدة : الانتقال في الأعمدة هو خلية فارغة مجاورة لخلية مشغولة (أو العكس) داخل عمود واحد. لا يعتبر توليف كتلة العمود المشغولة بأعلى مع مساحة فارغة فوقها انتقالًا. وبالمثل ، لا يتم أيضًا مقارنة أرضية الملعب بالخلية الموجودة فوقه. لذلك ، لا توجد انتقالات في عمود فارغ تمامًا.
- إجمالي عدد الانتقالات في الصفوف : الانتقال في الصفوف هو خلية فارغة مجاورة لخلية مشغولة (أو العكس) داخل الصف نفسه. تعتبر الخلايا الفارغة بالقرب من جدران الملعب مرحلة انتقالية. يتم احتساب المبلغ الإجمالي لجميع خطوط الملعب. ومع ذلك ، لا يتم أخذ الأسطر الفارغة تمامًا في الاعتبار في إجمالي عدد الانتقالات.
اقترح العشي أنه يمكن العثور على أوزان مفيدة باستخدام خوارزمية تحسين سرب الجسيمات (PSO) ، والتي تعمل بشكل متكرر على تحسين مجموعة الحلول عن طريق محاكاة سلوك السرب الملاحظ في الطبيعة. في حالتنا ، كل حل هو ناقل الوزن ، ويتم تحديد ملاءمة الخيار من خلال اللعبة في Tetris ؛ هذا هو العدد الإجمالي ل tetriminos التي نجا خلالها حتى نهاية اللعبة.
يتم تطبيق هذه الأفكار في إصدار Java الموضح أدناه ؛ يتم تشغيلها خارج FCEUX ويمكن تكوينها للعبة غير رسومات في الذاكرة تعمل بسرعة أعلى بكثير. بعد إعداد PSO ، فوجئت برؤية أن الخوارزمية لا تتحرك أكثر بعد التكرار الأولي. بعد هذا التكرار ، لعبت العديد من متغيرات الحلول التي تم إنشاؤها عشوائيًا بالفعل بشكل جيد. لعدة أيام ، انخفض حجم هذه المجموعة حتى بقي خيار واحد فقط. فيما يلي قيم هذا الحل:
| معلمة | الوزن |
|---|
| تم مسح إجمالي عدد الصفوف | 1.000000000000000 |
| إجمالي ارتفاع الحجب | 12.885008263218383 |
| العدد الإجمالي لخلايا البئر | 15.842707182438396 |
| العدد الإجمالي للثقوب في الأعمدة | 26.894496507795950 |
| العدد الإجمالي للتحولات في الأعمدة | 27.616914062397015 |
| إجمالي يقفز الخط | 30.185110719279040 |
تم تقدير الملعب من خلال ضرب المعلمات في أوزان كل منها وإضافة النتائج. كلما انخفضت القيمة ، كان الحل أفضل. نظرًا لأن جميع المعلمات والأوزان لها قيم إيجابية ، فإن جميع المعلمات تضر بالتقييم الشامل ؛ يجب التقليل من كل واحد منهم. وهذا يعني أيضًا أن أفضل نتيجة هي 0.
نظرًا لاختيار هذه الأوزان عشوائيًا ، يمكن أن يكون نطاق القيم المناسبة واسعًا جدًا. هذه المجموعة المحددة من الأرقام والأهمية النسبية المقدرة لكل معلمة قد لا تكون ذات صلة. ومع ذلك ، سيكون من المثير للاهتمام مشاهدتها عن كثب.
المعلمة الأقل ضررًا هي إجمالي عدد الصفوف التي تم محوها. حقيقة أن هذا الخيار ضار هو غير بديهي. لكن الهدف الرئيسي للذكاء الاصطناعي هو البقاء. إنه لا يسعى للحصول على أكبر عدد من النقاط. بدلاً من ذلك ، يلعب بشكل متحفظ ، وعادة ما يزيل الرتب في كل مرة. للحصول على Double أو Triple أو Tetris ، يجب أن تنمو مجموعة تتعارض مع الهدف طويل المدى.
التالي في القائمة هو إجمالي ارتفاع الحجب. يمكن تقليله عن طريق خفض tetrimino بالقرب من الأرض قدر الإمكان. هذه إستراتيجية بسيطة تساهم على المدى الطويل في البقاء ، وعلى المدى القصير في تغليف القطع بجودة عالية.
يبدو الوزن المعين للعدد الإجمالي لخلايا البئر مفاجئًا بعض الشيء ، لأن اللاعبين ذوي الخبرة عادة ما يبنون عمدًا آبارًا عميقة لجمع عدة Tetris (تركيبات من أربعة أسطر) على التوالي. ولكن كما ذكرنا أعلاه ، فهذه لعبة محفوفة بالمخاطر ، على عكس الهدف الرئيسي - البقاء. بالإضافة إلى ذلك ، يعد عدد الآبار مؤشرًا على "خشونة" الوبر. يكون مستوى معين من التفاوت مفيدًا عند وضع أرقام أو مجموعات معينة من الأشكال. لكن الخشونة العالية تتسبب في تلف العبوة الضيقة.
العدد الإجمالي للثقوب في الأعمدة هو تقريبًا نصف العدد الإجمالي للتحولات في الأعمدة. يمكن دمج هذه المعلمات وطيها في معلمة مشتركة ذات صلة ، للحصول على معلمة أكثر شمولاً وأكثرها ضررًا: إجمالي عدد الانتقالات.
تحتوي المناطق المكتظة بالسكان على عدد قليل من التحولات في جميع الاتجاهات. لذلك ، يمكن وصف الاستراتيجية الرئيسية ، مدفوعة بالذكاء الاصطناعي ، بإيجاز على النحو التالي: حزم القطع في أقرب وقت ممكن لبعضها البعض.
خيارات أخرى
فيما يلي قائمة ببعض المعلمات الإضافية التي جربتها أثناء تطوير الذكاء الاصطناعي:
- ارتفاع الكومة : يمكن أن تتدلى الكتل المشغولة فوق الخلايا الفارغة ، مما يخلق نتوءات وثقوب ؛ ومع ذلك ، لا يمكن تأمين الكتل المشغولة على أسطر فارغة تمامًا. لذلك ، ارتفاع الكومة هو عدد الصفوف التي تحتوي على كتلة مشغولة واحدة على الأقل.
- إجمالي عدد الأعمدة المشغولة : هذا هو عدد الأعمدة التي تحتوي على خلية مشغولة واحدة على الأقل.
- إجمالي عدد الخلايا المشغولة : عدد الخلايا المشغولة في الملعب.
- إجمالي عدد المناطق المتصلة : يتم استخدام خوارزمية التعبئة هنا لحساب عدد المناطق المتصلة بشكل مستمر. بالإضافة إلى العثور على "جزر" محتلة ، اكتشف ثقوبًا تمتد على طول المحورين.
- تشتت ارتفاع العمود : هذا مقياس إحصائي للتغير في ارتفاعات العمود. إنه مؤشر لخشونة السطح.
- إجمالي قيمة التكيف : لحساب قيمة التكيف الخاصة بالكومة للرقم المجهول التالي. يحسب العدد الإجمالي للطرق التي يمكن من خلالها إضافة 7 أنواع من الأشكال إلى الملعب دون ظهور ثقوب جديدة. من أجل العد الدقيق ، سوف تكون هناك حاجة إلى الاستخدام المتكرر ل BFS. ولكن لإجراء حساب تقريبي ، يمكن اقتطاع شجرة البحث بشكل كبير.
- متوسط التقييم للرسم التالي : تعمق هذه المعلمة البحث من خلال تحليل جميع الاحتمالات للرقم غير المعروف التالي. يستخدم معلمات أخرى لفصل موقع كل نوع من الأشكال ، ثم إرجاع المتوسط لـ 7 تقييمات. لكل موضع من الشكل ، مطلوب BFS.
- لعبة المحاكاة المتوسطة : تحاكي المعلمة سلسلة من الألعاب في Tetris ، واختيار القطع باستخدام مولد الأرقام العشوائي الزائف الخاص بها واستخدام AI للعمل معهم. في نهاية كل لعبة ، يتم تقييم الملعب باستخدام معلمات أخرى. يتم إرجاع متوسط القيمة لكافة الدفعات.
يمكن تخصيص جميع المعلمات بإضافة عوامل مخصصة. على سبيل المثال ، بدلاً من مجرد حساب الصفوف التي تم مسحها ، يمكنك تعيين أوزانك الخاصة لـ Single و Double و Triple و Tetris ، لمحاكاة نظام النقاط. إذا أضر التنظيف المتزامن للعديد من الصفوف بالهدف طويل المدى المتمثل في البقاء على قيد الحياة ، فيمكن تعيين وزن سلبي للصفوف الفردية ، بينما يمكن أن تصبح الصفوف الأخرى إيجابية.
عامل مفيد آخر هو قيمة الإزاحة. على سبيل المثال ، يحتوي سطح مستوٍ تمامًا على كومة على تشتت ارتفاعات العمود 0. لكن السطح المستوي تمامًا لا يتكيف مع S و Z ، بالإضافة إلى مجموعات أخرى من الأشكال. لذلك ، من خلال طرح الثابت ، يجب أن يتمحور التباين حول الخشونة المثلى.
يمكن رفع المعلمات المعدلة والمتحيزة إلى حد ما حتى قبل حساب المجموع المرجح يمكنهم قياس اللوغاريتمات أو الأسي. يمكن اعتبار كل هذه الاحتمالات أوزانًا إضافية يمكن تحسينها بطرق مثل PSO.
تعطي العديد من المعلمات فهمًا لمدى قدرة الكومة على التعامل مع قطع إضافية ، على سبيل المثال ، تلك التي تتعامل مع خشونة السطح ، ولكن "إجمالي مقدار التكيف" و "متوسط تقييم الشكل التالي" و "متوسط لعبة المحاكاة" يقيمان الملعب المتغير إدخال الأشكال غير المدرجة في الاثنين المعروفين. في دراسة الأرقام اللاحقة ، بسبب الإزالة السريعة للسلسلة ، تقل كمية المعرفة الإضافية التي تم الحصول عليها بعمق. هذا يعني أن المسار الطويل للحزب ليس مهمًا جدًا ، وأن مسار الحزب في المستقبل البعيد ليس مهمًا أيضًا. في الواقع ، إذا تم تعيين سلسلة قصيرة من الأرقام بشكل غير صحيح بشكل غير صحيح ، فإن الذكاء الاصطناعي يعيد اللعبة بسرعة ، باستخدام الأشكال القليلة التالية لمسح الصفوف المتأثرة. يتطلب تحديد القيمة المثلى لتحليل الأرقام اللاحقة مزيدًا من البحث.
جانب آخر من فائدة المعلمة هو التكلفة الحسابية. تزداد التكاليف بشكل كبير لأن وظيفة التقييم تستدعي لكل موضع محتمل لرقمين. نظرًا لأن الذكاء الاصطناعي يجب أن يكون قادرًا على لعب Tetris في الوقت الفعلي ، يمكن استبدال عوامل التكلفة التي توفر معلومات قيمة للحصول على تقنيات أكثر تقريبًا تعمل بشكل أسرع.
تدريب الذكاء الاصطناعي
هناك تسلسل مرضي يمكن أن يؤدي إلى Game Over ، بغض النظر عن الاستراتيجية. أبسط مثال على ذلك هو التسلسل اللامتناهي لـ tetrimino S و Z ، والذي ، كما هو موضح في الرسوم المتحركة ، يؤدي بسرعة إلى فقدان الذكاء الاصطناعي.
نظرًا لأن الأمر يستغرق أيامًا لتشغيل متغير AI قبل إكمال عدة دفعات وحساب المتوسط ، فمن غير العملي تمامًا استخدام متوسط مدة الدفعة كمقياس للتحكم في PSO. بدلاً من ذلك ، يمكنك زيادة تعقيد اللعبة بسرعة محكومة عن طريق زيادة وتيرة S و Z ، الأمر الذي سيؤدي بمرور الوقت إلى إنشاء بديل لهذا الزوج من الأشكال فقط.
لقد حاولت استخدام طريقة التدريس هذه ، لكنني وجدت أن تعليم الذكاء الاصطناعي للعمل مع S و Z المتكررين يضر بالفعل بالقدرة على التعامل مع الأشكال العشوائية الموزعة بالتساوي.
في طريقة بديلة مستوحاة من لعبة B-Type ، يتحكم مقياس PSO في تكرار تنظيف الصفوف. مجال اللعب عبارة عن رسم تخطيطي مكون من 10 أسطر لكتل القمامة العشوائية ، وفي كل مرة يتم مسح الخط ، يظهر أدناه خط قمامة جديد ، يعيد ارتفاع كومة الذاكرة المؤقتة. نظرًا لأن مجال اللعب يبلغ عرضه 10 أعمدة ، وتتكون كل tetrimino من 4 مربعات ، في المتوسط ، يجب على AI مسح صف كل 2.5 tetrimino. وللتخلص من القمامة ، يجب أن يفعل ذلك بشكل أسرع.
لسوء الحظ ، لم تحسن هذه التقنية الأداء أيضًا. أحد الأسباب المحتملة هو أن ثقوب القمامة العشوائية لا تتطابق تمامًا مع الأوتار التي يتعامل معها الذكاء الاصطناعي في اللعبة الحقيقية. بالإضافة إلى ذلك ، تنظيف الصف هدف قصير المدى. تنظيف الصف الجشع لا يحسن بالضرورة البقاء على المدى الطويل. من وقت لآخر ، لا ينبغي لمس الصفوف لمعالجة مجموعات معينة من الأرقام اللاحقة.
اقترح
كولين فاي نهجًا مختلفًا على صفحته على الويب. قام بإنشاء الرسوم البيانية التي تظهر النسبة المئوية للأشكال التي تم حظرها في كل صف أثناء الكثير من التجارب. من المثير للاهتمام أن جميع الرسوم البيانية تبدو متطابقة تقريبًا بغض النظر عن عدد الأشكال التي تم إنشاؤها. بناءً على ذلك ، اقترح أنه يمكنك استخدام صورة تقريبية للدالة لأي دفعة تجريبية عند تقييم التوقع الإحصائي لحظر الرقم في خط الإنشاء ، وبالتالي الحصول على الوقت الذي ستلعب فيه AI حتى نهاية اللعبة. قررت استكشاف هذا الاحتمال.
فيما يلي خريطة حرارية للعديد من مجموعات التجارب ، تحتوي في المجموع على 2،039،900،000 tetrimino. يتم تلوين كل خلية بناءً على النسبة المئوية للأشكال المقفلة فيها. لتعزيز التباين البصري ، يتم تحديد لوحة غير خطية. تم إنشاء الخريطة عن طريق تطبيع قيم الخلايا عن طريق القسمة على النسبة المئوية القصوى للخلايا ، ثم الإعلان عن قوة 0.19 (انظر
"تصحيح غاما" ).
| | اللون | النسبة المئوية |
|---|
| ■ | 0.00000000 | | ■ | 0.00000315 | | ■ | 0.00024227 | | ■ | 0.00307038 | | ■ | 0.01860818 | | ■ | 0.07527774 | | ■ | 0.23582574 | | ■ | 0.61928352 | | ■ | 1.42923040 | | ■ | 2.98867416 | | ■ | 5.78182519 |
|
الخطوط البرتقالية الداكنة والحمراء في الخطين 17 و 18 تعني أن الغالبية العظمى من الأشكال تنتهي هناك. اللون الأخضر الباهت من الأسفل هو نتيجة لهندسة الأشكال: 4 فقط من 7 أنواع من tetrimino يمكن أن تظهر في الخط السفلي. الزوايا السفلية سوداء لأنه من المستحيل الوصول إليها.
اللون على طول كل خط متساوي تقريبًا ، وهذا يشير إلى أن الأشكال موزعة بشكل أفقي بالتساوي. يمكن تفسير الفجوات الطفيفة من خلال النظر إلى الرسوم البيانية للأنواع الفردية من الأشكال:
يتبين أن T هو النوع الأكثر شمولاً: مخططه البياني هو أكثر تجانسًا من جميع الأنواع الأخرى. الشذوذ في الرسم البياني J - نتيجة تأثير الجدران ؛ يمكن فقط أن يكون كل من
Jr و
Jl في الأعمدة الجانبية ، مما يجعل AI يستخدم العمودين 1 و 9 في كثير من الأحيان للتعويض. وينطبق الشيء نفسه على L. يبدو أن المدرج التكراري Z و S متشابهين تقريبًا ، مما يؤكد عدم التوازن بسبب حقيقة أن
Zv و
Sv ليست صور مرآة مثالية لبعضها البعض. يقتصر النوع O على ملعب 19 × 9 ، ويبدو أن الذكاء الاصطناعي من المرجح أن يستخدم O على الجوانب أكثر من المركز. تتحول Tetrimino I إلى اليمين ، لأن نقطة انطلاقها تقع هناك ؛ لذلك ، من النادر تأمين القفل في العمود 1.
يوضح الجدول النسبة المئوية للأرقام المحظورة في كل صف.
| سلسلة | النسبة المئوية |
|---|
| 0 | 0.0000000000 |
| 1 | 0.0000000000 |
| 2 | 0.0000004902 |
| 3 | 0.0000026472 |
| 4 | 0.0000066180 |
| 5 | 0.0000172557 |
| 6 | 0.0000512280 |
| 7 | 0.0001759400 |
| 8 | 0.0006681210 |
| 9 | 0.0023187901 |
| 10 | 0.0077928820 |
| 11 | 0.0259672043 |
| 12 | 0.0866187068 |
| 13 | 0.2901315751 |
| 14 | 0.9771663807 |
| 15 | 3.3000408353 |
| 16 | 10.6989059268 |
| 17 | 28.5687976371 |
| 18 | 50.0335706162 |
| 19 | 6.0077671454 |
هنا رسم بياني للقيم:
إذا لم يؤخذ السطر 19 في الاعتبار ، فإن الرسم البياني يظهر نموًا أسيًا.
فيما يلي قائمة بنسب عدد الأشكال المقفلة في الصفوف المجاورة.| السلسلة A / السلسلة B | النسبة (٪) |
|---|
| 1/2 | 0.00 |
| 2/3 | 18.52 |
| 3/4 | 40.00 |
| 4/5 | 38.35 |
| 5/6 | 33.68 |
| 6/7 | 12/29 |
| 7/8 | 26.33 |
| 8/9 | 28.81 |
| 9/10 | 29.76 |
| 10/11 | 01/30 |
| 11/12 | 29.98 |
| 12/13 | 29.85 |
| 13/14 | 29.69 |
| 14/15 | 29.61 |
| 15/16 | 30.84 |
| 16/17 | 37.45 |
| 17/18 | 57.10 |
| 18/19 | 832.81 |
16–19تأخذ الخطوط في الاعتبار الأشكال التي تتفاعل مع أرضية الملعب ، بحيث يمكن التخلص منها. في الصفوف ، يكون 0–5التحديد أصغر من أن يكون له معنى. النسب المتبقية ، أزواج 6 / 7-14 / 15 ، متطابقة تقريبًا ؛ متوسط قيمتها 29.24٪. هذا يعني أن احتمال نمو كومة الذاكرة المؤقتة بخط واحد هو نفسه تقريبًا بغض النظر عن ارتفاع كومة الذاكرة المؤقتة. هذا أمر منطقي ، لأن قواعد Tetris تحد من التفاعل في الجزء العلوي من كومة الذاكرة المؤقتة عندما تكون معبأة بإحكام.يوضح الرسم البياني التالي سجل 10 في المائة من الأشكال في السطور 6-15.إنه قريب من خط مستقيم تمامًا مع معامل تحديد قريب من 1 . تعطينا الصيغة المشتقة من الانحدار الخطي الموضح أعلاه التقاطع مع المحور Y ، بافتراض أن النسبة المئوية للأشكال في الصف 0 تبلغ تقريبًا 10 −7.459 ٪. ويعكس معكوس هذه القيمة توقعًا إحصائيًا يبلغ 2،877،688،349 tetrimino أو 1،151،175،340 صفًا حتى نهاية اللعبة.هذا يجعلنا نفهم ذلك السجل 10تظل النسبة المئوية للأرقام في كل سطر خطية حتى السطر 0. ومع ذلك ، عندما يصل كومة الذاكرة المؤقتة تقريبًا إلى سقف الملعب ، تكون حرية الحركة مقيدة إلى حد انتهاك هذه الخاصية. بالإضافة إلى ذلك ، فإن حظر قطعة على الخط 0 لا يعني بالضرورة انتهاء اللعبة ؛ لا يزال بإمكانك حفظها إذا كان هناك مكان لإنشاء أرقام جديدة.طريقة أخرى لتقييم قوة الذكاء الاصطناعي هي قياس متوسط عدد الأشكال التي تم إنشاؤها بين التطهير الكامل للملعب. يمكن الحصول على التنظيف الكامل باستخدام 5 tetriminos فقط. على سبيل المثال ، من بين الاحتمالات الأخرى ، يمكن تحقيق ذلك من خلال خمسة أرقام O الموضوعة على أرضية الملعب. بشكل عام ، نظرًا لأن كل tetrimino يتكون من 4 مربعات وعرض الملعب 10 مربعات ، يجب أن يكون عدد الأشكال التي تم إنشاؤها بين التنظيف الكامل مضاعفًا 5 ( منذ ذلك الحين4 × 5 ن = 2 × 10 ن ).يحتوي My AI على متوسط عدد الأشكال التي تم إنشاؤها بين عمليات التنظيف الميدانية الكاملة التي تبلغ 1،181 - وهو عدد قليل إلى حد ما. نظرًا لأن التنظيف الكامل يشبه إعادة تشغيل اللعبة ، يمكن رؤية مجموعة كاملة على أنها سلسلة طويلة للغاية من عمليات إعادة تشغيل اللعبة ، يتبعها تقدم سريع إلى اللعبة. مثل تسلسل البدائل الموصوفة أعلاه SZ، عادة ما تكون التسلسلات المرضية التي تؤدي إلى نهاية اللعبة قصيرة جدًا.يوضح الرسم البياني أدناه الاحتمال (بالنسبة المئوية) بأن الذكاء الاصطناعي سوف يحقق تطهيرًا كاملاً للحقل بعد العدد المحدد من الأشكال التي تم إنشاؤها.يحدد ترتيب الدرجة في الصيغة أعلاه معدل الانخفاض ، ويفترض ، قوة الذكاء الاصطناعي. وفقًا لهذه الصيغة ، ينتهي ما يقرب من 0.4 ٪ ، أو حوالي 1 من أصل 253 لعبة تبدأ بملعب فارغ ، بتطهير كامل في 5 tetriminos فقط.على عكس ما اقترحه فاي ، تتطلب الثوابت في التقريبات الخطية والأسية حجم عينة كبير جدًا بحيث R 2اقترب 1 ، لذلك هذه الطريقة لا تنطبق على PSO. ومع ذلك ، يمكن استخدام الثوابت التي تم الحصول عليها باستخدام مجموعات طويلة لتحسين وظيفة التقريب التي تنشئ قيمًا ثابتة محتملة للدفعات القصيرة. في نوع من حلقات التغذية الراجعة التطويرية ، يمكن استخدام وظيفة التقريب المحسنة في PSO ، مما يعمل على تحسين الذكاء الاصطناعي ، والذي يمكن استخدامه بدوره لحساب الثوابت الجديدة ، بمثابة معايير مرجعية لوظيفة التقريب.نسخة جافا
عن البرنامج
بالنسبة إلى المطورين غير المعتادين على Lua ، أضفت منفذ Java AI إلى ملف zip المصدر . الفئات عبارة عن ترجمة سطرية لكائنات Lua استنادًا إلى عمليات الإغلاق .الحزم
ينقسم الرمز إلى حزمتين:tetris.ai يحتوي على فصول وواجهات AI.tetris.gui يخلق نموذجًا رسوميًا للملعب.
دروس وواجهات AI
Tetriminosتصف فئة تحمل الاسم المناسب tetrimino. يتم استخدامه بشكل مشابه enumويحتوي على ثوابت لجميع أنواع tetrimino: public static final int NONE = -1; public static final int T = 0; public static final int J = 1; public static final int Z = 2; public static final int O = 3; public static final int S = 4; public static final int L = 5; public static final int I = 6;
NONEيعني قيمة غير محددة. يتم استخدامه للخلايا الفارغة في الملعب. يحتويأيضًا Tetriminosعلى نموذجين من جدول التوجيه. PATTERNS- هذا هو صفيف صحيح 4-أبعاد (النوع × دوران × مربع × إحداثيات) يحتوي على الإحداثيات النسبية للمربعات ؛ يتم ترتيب الخطوط بحيث يكون اتجاه إنشاء الشكل في كل نوع هو الأول. ORIENTATIONSهو نموذج آخر ، صفيف ثنائي الأبعاد (نوع × دوران) من الكائنات Orientation. Orientationيحتوي كل منها على إحداثيات المربع كمصفوفة من الكائنات Point. يحتوي أيضًا على حقول تصف نطاق المواضع المسموح بها للاتجاه المقابل. public class Orientation { public Point[] squares = new Point[4]; public int minX; public int maxX; public int maxY; ... }
public class Point { public int x; public int y; ... }
يتم استخدام Tetrimino rotation (الفهرس الثاني في كل من جدولي التوجيه) في الكائنات Stateالتي يتعامل معها BFS. public class State { public int x; public int y; public int rotation; public int visited; public State predecessor; public State next; ... }
x، yو rotationمعا وصف الموقف والتوجه من هذا الرقم. نظرًا لأن نوع Tetrimino يظل ثابتًا من لحظة الإنشاء إلى الحظر ، فإن المجال الخاص به اختياري. تنشئالفئة Searcherالتي تحتوي على خوارزمية BFS مجموعة كاملة من جميع الكائنات المحتملة Stateعند إنشائها: private void createStates() { states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4]; for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) { for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) { for(int rotation = 0; rotation < 4; rotation++) { states[y][x][rotation] = new State(x, y, rotation); } } } }
على الرغم من أن Java تحتوي على واجهة برمجة تطبيقات Collections API الغنية ، إلا أنها Searcherتحتوي على تطبيق خاص بها لقائمة الانتظار. Queueيستخدم الفصل لربط State.nextالكائنات Stateفي قائمة مرتبطة. نظرًا لأن جميع الكائنات Stateمحددة مسبقًا ، Stateويمكن إضافة كل منها إلى قائمة الانتظار ليس أكثر من مرة واحدة ، يمكن أن تعمل قائمة الانتظار في مكانها ، مما يلغي الحاجة إلى كائنات حاوية مؤقتة غير ضرورية تستخدم في تطبيقات قائمة الانتظار العامة."قلب" BFS هي الطريقة الموضحة أدناه search. public boolean search(int[][] playfield, int tetriminoType, int id) { int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1; int mark = globalMark++; if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) { return false; } while(queue.isNotEmpty()) { State state = queue.dequeue(); if (maxRotation != 0) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == 0 ? maxRotation : state.rotation - 1); if (maxRotation != 1) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == maxRotation ? 0 : state.rotation + 1); } } addChild(playfield, tetriminoType, mark, state, state.x - 1, state.y, state.rotation); addChild(playfield, tetriminoType, mark, state, state.x + 1, state.y, state.rotation); if (!addChild(playfield, tetriminoType, mark, state, state.x, state.y + 1, state.rotation)) { lockTetrimino(playfield, tetriminoType, id, state); } } return true; }
يفرز طابورًا مع حالة tetrimino التي تم إنشاؤها ، ثم يسترد العناصر الفرعية بالتسلسل من الحالات التي تم إزالتها من قائمة الانتظار ، ويضيفها مرة أخرى إلى قائمة الانتظار عندما تظهر في الملعب. يتم تمرير حقل اللعبة الذي يحتوي على مجموعة من الخلايا المشغولة والخالية ، ونوع Tetrimino الذي تم إنشاؤه ، ومعرف عشوائي إلىالطريقة search. أثناء تنفيذ BFS ، يتم استدعاء المستمع عندما يتم الكشف عن موقف القفل. public interface ISearchListener { public void handleResult(int[][] playfield, int tetriminoType, int id, State state); }
يستمع المستمع إلى ساحة لعب متغيرة تحتوي على tetrimino مقفل في مكانه. يتم أيضًا إرسال نوع Tetrimino الذي تم إنشاؤه ومعرف عشوائي. المعلمة الأخيرة هي Stateالتي يتم فيها حظر tetrimino. باتباع سلسلة الارتباطات State.predecessor، يمكنك استعادة كل طريق إلى Stateإنشاء شكل.State.visitedيمكن تنفيذها على النحو boolean؛ ولكن مع كل التسهيلات اللازمة لفرز قبل تفتيش Stateللإغاثة visitedعلى false. بدلاً من ذلك ، قمت بعمل visitedقيمة intمقارنة بالعداد ، تزداد مع كل مكالمة.الطريقةaddChildما قبل الطابور الحالات اللاحقة. يجب أن تكون الحالة اللاحقة داخل الحقل وأن تكون موجودة على 4 خلايا فارغة في الملعب. بالإضافة إلى ذلك ، يجب عدم النظر في الحالة اللاحقة State. إذا كان الموقف غير مقبول، addChildعودة true، حتى لو فشلت الدولة اللاحقة لوضعها في المكان لأنه قد زار بالفعل. تستخدمالطريقة القيمة المرجعة لتحديد ما إذا كان يمكن إنشاء شكل. إذا لم يتم إنشاء الشكل ، فحينئذٍ يصل كومة الذاكرة المؤقتة إلى القمة ولم يعد من الممكن إجراء البحث ؛ لذلك يعود . قابل للإرجاعsearchaddChildfalseaddChildأهمية يجري دراستها أيضا لإمكانية النزول خطوة أخرى. إذا كان لا يمكن القيام بذلك ، فإن الحالة الحالية هي موضع القفل وتبدأ المكالمة lockTetrimino. تقوم الطريقة lockTetriminoبتغيير الملعب ، واستدعاء المستمع ، ثم استعادة الملعب.يحتوي كل صف من المصفوفة playfieldعلى عنصر إضافي واحد ، يخزن عدد الخلايا المشغولة في الصف. يتم تنفيذ زيادة عنصر بواسطة الطريقة lockTetriminoلأنه يميز الخلايا بأنها مشغولة.عندما يتلقى المستمع ساحة لعب معدلة ، يتصلPlayfieldUtil.clearRowsلحذف الصفوف المعبئة يتعرف عليها الأسلوب عن طريق التحقق من القيمة في العنصر الإضافي للصفيف. لإزالة سلسلة ، تستفيد الشفرة من حقيقة أنه في Java ، تعد المصفوفات ثنائية الأبعاد هي في الأساس صفائف من المصفوفات ؛ فإنه يدفع فقط روابط إلى سلاسل. PlayfieldUtilيحتوي على خطوط مجانية ؛ يكمل عملية التنظيف بإدخال رابط لأحدها. قبل إجراء النقل ، يتم تخزين فهرس الصف الذي يتم محوه في عنصر صف إضافي. ثم يتم دفع الرابط إلى الخط على المكدس.ثم يتصل المستمعPlayfieldUtil.restoreRowsلتجاهل التغييرات التي تم إجراؤها على أرض الملعب. يتم إلغاء الخطوات بترتيب عكسي. أولاً نحصل على صف مجاني من الأعلى. ثم ، يتم استرداد الصف المعبأ من المكدس ويتم استعادة الفهرس من العنصر الإضافي. يتم استخدامه لتحويل مراجع الخط والعودة إلى مكان الخط المحذوف. أخيرًا ، يتم استعادة عنصر إضافي ، ويتم تعيين قيمة عرض الملعب - عدد الخلايا المشغولة في الصف المملوء.هناك PlayfieldUtilأيضًا طريقة evaluatePlayfieldتحسب وتكتب 4 معلمات تقييم في فئة الحاوية الموضحة أدناه. public class PlayfieldEvaluation { public int holes; public int columnTransitions; public int rowTransitions; public int wells; }
يدير الصف كل هذا AI. يحتوي على شيئين Searcherمتصلان معًا من قبل المستمع الموضح أدناه. public void handleResult( int[][] playfield, int tetriminoType, int id, State state) { if (id == 0) { result0 = state; } Orientation orientation = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation]; int rows = playfieldUtil.clearRows(playfield, state.y); int originalTotalRows = totalRows; int originalTotalDropHeight = totalDropHeight; totalRows += rows; totalDropHeight += orientation.maxY - state.y; int nextID = id + 1; if (nextID == tetriminoIndices.length) { playfieldUtil.evaluatePlayfield(playfield, e); double fitness = computeFitness(); if (fitness < bestFitness) { bestFitness = fitness; bestResult = result0; } } else { searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID); } totalDropHeight = originalTotalDropHeight; totalRows = originalTotalRows; playfieldUtil.restoreRows(playfield, rows); }
AIيمكن للفئة التعامل مع أي عدد من الكائنات Searcher، لكن Nintendo Tetris لا تعرض سوى شكل واحد مقدمًا. Searcherيتم تخزين الكائنات في مصفوفة ، ويعمل الرمز الموضح أعلاه كمستمع مشترك لها. المعرف العشوائي الذي تم تمريره إلى الطريقة Searcher.searchهو في الواقع فهرس المصفوفة ، وهو أيضًا عمق البحث. عندما يتم استدعاء المستمع ، يوجه المعرف المكالمة إلى التالي Searcherفي السلسلة. إذا وصل إلى نهاية المصفوفة ، ثم يقيم الملعب. وعندما يجد ساحة لعب ذات درجة لياقة أعلى ، يكتب المدرج المحظور Stateمن الأول Searcherفي السلسلة.AIيحتوي على طريقة searchتستقبل الملعب وصفيف يحتوي على أنواع tetrimino التي تم إنشاؤها والتالي. يعودStateتحتوي على الموضع والدوران الذي يجب فيه حظر التتريمينو الأول. لا يركز على tetrimino الثاني ؛ في المرة التالية التي يتم استدعاؤها ، تقوم بإعادة حساب النتيجة. إذا كانت كومة الذاكرة المؤقتة عالية جدًا Searcherوفشل السلسلة في وضع كل من tetriminos ، AI.searchفسوف تعود null. public State search(int[][] playfield, int[] tetriminoIndices) { this.tetriminoIndices = tetriminoIndices; bestResult = null; bestFitness = Double.MAX_VALUE; searchers[0].search(playfield, tetriminoIndices[0], 0); return bestResult; }
تحدي الذكاء الاصطناعي
نظرًا لأن إصدار Java غير مرتبط بـ FCEUX ، فمن المحتمل استخدامه في مشاريع أخرى. بالنسبة لأولئك الذين يرغبون في دمج الذكاء الاصطناعي في مكان آخر ، يصف هذا القسم كل ما تحتاجه.أولاً ، قم بإنشاء مثيل AIومثال PlayfieldUtilوصفيف لاحتواء جميع أنواع tetrimino المعروفة. بالإضافة إلى ذلك ، قم بإنشاء PlayfieldUtil.createPlayfieldمثيل من الملعب عن طريق الاتصال ؛ تقوم بإرجاع صفيف ثنائي الأبعاد مع عمود إضافي ، الذي درسناه أعلاه. ربما ستحتاج أيضًا إلى مولد رقم عشوائي. AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random();
في البداية ، يكون الملعب فارغًا ، وجميع الخلايا ذات صلة Tetriminos.NONE. إذا قمت بملء الخلايا برمجيًا ، فلا تنسَ كتابة playfield[rowIndex][AI.PLAYFIELD_WIDTH]عدد الخلايا المشغولة في كل صف.املأ مجموعة أنواع tetrimino بأنواع الشكل الذي تم إنشاؤه مبدئيًا والشكل التالي ، اللذين يتم تحديدهما يدويًا عادةً. tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7);
ثم نمرر مجال اللعب ومجموعة الأنواع إلى الطريقة AI.search. سيعود Stateحيث تحتاج إلى حظر tetrimino الأول. إذا عاد null، فإن اللعبة انتهت لا مفر منها. State state = ai.search(playfield, tetriminos);
إذا كنت بحاجة إلى طريقة من إنشاء شخصية إلى قفل ، فمررها إلى Stateالطريقة AI.buildStateList. State[] states = ai.buildStatesList(state);
لتحديث الملعب ، سنمرره PlayfieldUtil.lockTetriminoمع نوعه وشيءه State. تقوم هذه الطريقة بمسح الصفوف المملوءة تلقائيًا. playfieldUtil.lockTetrimino(playfield, tetriminos[0], state);
قبل الاتصال مرة أخرى ، AI.searchتحتاج إلى تحديد tetrimino التالي بشكل عشوائي. tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7);
معًا ، يبدو هذا كما يلي: AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); while(true) {
بدلاً من عرض الملعب في شكل نصي ، يمكنك استخدام طريقة أكثر إثارة للاهتمام لعرض ما يحدث ...عرض مجال اللعب
TetrisFrameيقلد الفصل رسومات Nintendo Tetris ، بما في ذلك الميزات السلوكية الموضحة في الجزء السابق من المقالة.لرؤيتها في العمل ، قم بتشغيلها tetris.gui.Main. كما هو الحال مع إصدار Lua ، يمكننا ضبط سرعة اللعبة عن طريق تغيير القيمة الثابتة في بداية الملف. public static final boolean PLAY_FAST = true;
TetrisFrame4 طرق للتعامل مع الشاشة. الطريقة displayTetriminoتجعل tetrimino النشط في الإحداثيات المحددة. يتلقى معلمة تأخير ، مما يؤدي إلى انتظار الطريقة قبل إرجاع العدد المحدد من إطارات الرسوم المتحركة. public void displayTetrimino(int type, int rotation, int x, int y, int delay)
الطريقة lockTetriminoتقفل الشكل في مكانه. يتم تحديث عدادات الصف والنقاط والمستوى وألوان tetrimino وفقًا لذلك ، لتوضيح السلوك الغريب المتوقع عندما تتجاوز القيم القيم المسموح بها. يتضمن تعيين animateقيمة لمعلمة trueرسومًا متحركة لتنظيف الصف وخفقان الشاشة عند تلقي Tetris. يتم حظر الطريقة حتى انتهاء الرسوم المتحركة. public void lockTetrimino(int type, int rotation, int x, int y, boolean animate)
updateStatisticsAndNext يقوم بزيادة عداد الإحصائيات لـ tetrimino الذي تم إنشاؤه حديثًا وتحديث عرض الشكل التالي. public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino)
dropTetriminoتخلق الطريقة شكلاً وتسمح لها بالنزول تحت تأثير "الجاذبية" ، دون القيام بأي محاولات لتدويرها أو تحريكها. Mainيستخدمه لآخر رقمين عندما AI.searchيعود null. إذا كانت المعلمة animateتعيين true، ثم عندما يكون من المستحيل لخلق شخصية الستار اللعبة. كما هو الحال مع جميع الطرق الأخرى ، يتم حظر هذه الطريقة حتى انتهاء الرسوم المتحركة. trueلا تعود إلا عندما يمكنها إنشاء شخصية في ساحة لعب مزدحمة. public boolean dropTetrimino(int type, boolean animate)
يجب أن يتم استدعاء هذه الطرق الأربعة بواسطة سير العمل ، ولكن TetrisFrameيجب أن يتم تكوينها في سلسلة ارسال الحدث نفسها. لترى كيف يتم ذلك ، انظر الفصل Main.من أجل الاهتمام ، Mainيستخدم فئة Randomizerتحاكي مولد الأرقام العشوائية الزائفة المتحيز من Nintendo Tetris. تحتويالحزمة tetris.gui.imagesعلى ملفات متعلقة بالعرض. tiles.png- هذا هو جدول نمط يحتوي على جميع رسومات البلاط. background.datيخزن معرفات البلاط التي تشكل الخلفية ؛ البيانات المستخرجة من $BF3F. و colors.datيحتوي بايت توليد الساحات غير عادية اللون التي تظهر على مستوى 138.ImageLoaderيحتوي NES الجدول لوحة، و ImagePaneمخازن مجموعة كاملة من القيم مستويات المعروض.مشاريع أخرى
من المحتمل أن يتم استخدام الرمز بدلاً من الكتابة للوضع التجريبي. في الواقع ، يمكن تقديم مثل هذا العرض التوضيحي إلى الأبد ، مع الاستفادة من مدى سرعة الذكاء الاصطناعي في مسح مجال اللعب بالكامل. لتحقيق ذلك ، في مولد الأرقام العشوائية الزائفة ، تحتاج إلى استخدام بعض الثابت التعسفي كبذرة ، الأمر الذي سيعطينا تسلسلًا حاسمًا من tetrimino. سيتم تسجيل أول تسلسلين tetrimino. عندما يصل الذكاء الاصطناعي إلى تنظيف الحقل الكامل ، ستتم مقارنة الروتينين التاليين مع أول اثنين من التسلسل. إذا كانا متطابقين (هذا الحدث متوقع كل 49 عملية تنظيف حقل كاملة) ، عندها يمكن تمرير مولد الأرقام العشوائية الزائفة بنفس ثابت البذور ، مما سيؤدي إلى إنشاء حلقة عرض لانهائية. يمكن أن تكون مدة الدورة طويلة جدًا لإخفاء حقيقة أنها دورة. أيضايمكن أن يبدأ العرض التوضيحي عند نقطة عشوائية في الحلقة ، مما يؤدي إلى إنشاء عرض توضيحي جديد في كل مرة.هناك إمكانية أخرى لاستخدام الذكاء الاصطناعي وهي إنشاء وضع "لاعب مقابل كمبيوتر". في لعبة Tetris متعددة اللاعبين ، أثناء مسح العديد من الخطوط في نفس الوقت ، تظهر خطوط القمامة في الجزء السفلي من حقل الخصم ، مما يرفع الملعب. يجب أن يكون الذكاء الاصطناعي قادرًا على حماية نفسه من الحطام لنفس السبب الذي يمكنه من لعب ألعاب من النوع B. ومع ذلك ، كما ذكرنا سابقًا ، يلعب الذكاء الاصطناعي بشكل متحفظ ، وعادة ما يسعى إلى مسح سطر واحد في كل مرة. أي أنه سيكون قادرًا على الدفاع عن نفسه من الهجمات ، لكنه غير قادر على الهجوم. لكي أتمكن من تغيير سلوكه ، أنشأت واجهة تسمى IChildFilter. public interface IChildFilter { public boolean validate(int[][] playfield, int tetriminoType, int x, int y, int rotation); }
AIلديه منشئ بديل يحصل على التنفيذ IChildFilter. إذا كان متاحًا ، IChildFilter.validateفهو بمثابة فحص إضافي للحصول على إذن من الدولة الفرعية ؛ إذا عاد false، لا يتم وضع الحالة التابعة في قائمة الانتظار.WellFilterهو تنفيذIChildFilterتهدف إلى التقاط أربعة صفوف (تتريس). مثل اللاعبين الأحياء ، تقوم ببناء بئر تدريجيًا في العمود الموجود في أقصى يمين الملعب ، وترتفع خطًا تلو الآخر من الأسفل إلى الأعلى. نظرًا لأنه يعمل سطرًا بسطر ، فإنه يرفض الحالات الفرعية التي تضيف مربعًا إلى العمود الموجود في أقصى اليمين. عندما يكون الصف بأكمله ، باستثناء عمود البئر ، ممتلئًا تمامًا ، ينتقل الذكاء الاصطناعي إلى الصف التالي. عندما تكون 4 أو أكثر من هذه الخطوط جاهزة ، فإنها تسمح لـ "العصا" بالسقوط في البئر والحصول على تتريس. بالإضافة إلى ذلك ، يتم تتبع ارتفاع كومة الذاكرة المؤقتة ؛ إذا أصبح كبيرًا جدًا ، فإنه WellFilterيتوقف عن التأثير على الذكاء الاصطناعي.لاختباره في العملية ، قم بإجراء Mainالتغييرات التالية: AI ai = new AI(new WellFilter());
WellFilterيعمل ، ولكن ليست فعالة بشكل خاص. يحتوي على مجريات ارشادية بسيطة مصممة لتوضيح المفهوم. للحصول على Tetris في كثير من الأحيان ، تحتاج إلى استخدام استراتيجية أكثر تعقيدًا ، ربما استراتيجية يمكن تحسينها باستخدام PSO.بالإضافة إلى ذلك ، يمكنك استخدام تصفية الحالة الفرعية لإنشاء أنماط. فيما يلي مثال على ما يستطيع PatternFilter.PatternFilterيبني الصور سطرا بسطر من الأسفل إلى الأعلى ، على غرار طريقة عملها WellFilter؛ ومع ذلك ، بدلاً من الحفاظ على العمود الموجود في أقصى اليمين ، فإنه PatternFilterيوافق فقط على الحالات الفرعية التي تتوافق مع نمط معين. يحصلالمنشئ PatternFilterعلى اسم إحدى الصور الموجودة في الحزمة tetris.gui.patterns، والتي يستخدمها كقالب. تحتوي كل صورة 20 × 10 على بيكسلات سوداء وبيضاء تتوافق مع الخلايا في الملعب. AI ai = new AI(new PatternFilter("tetriminos"));
يخلق سطر الكود الموضح أعلاه الصور الظلية لسبعة أنواع من tetrimino.مثال آخر مع tetrimino T كبير يدور بزاوية.مثال آخر. إذا نظرت عن كثب ، سترى اسم اللعبة.مثل WellFilter، PatternFilterليس أكثر من إثبات للمفهوم. تقتصر الأنماط التي يعالجها على الجزء السفلي من الملعب نظرًا لحقيقة أن محاولات الحصول عليها تنتهي عادةً مع انتهاء اللعبة. ومع ذلك ، هذه فكرة مثيرة للاهتمام تستحق المزيد من الدراسة.إصدار غمبد
يتجاهل برنامج Lua النصي وجافا الجاذبية. بالنسبة لهم ، سرعة الهبوط ليست مهمة ، لأنه اعتمادًا على التكوين ، إما أن ينقلوا الأرقام فورًا إلى الموقع المطلوب ، أو يسحبون على أي مسار مختار. بطريقة ما ، هم فقط يحاكيون تتريس ، لا يلعبونها. ومع ذلك ، في ملف مضغوط مع المصادر ، هناك نص Lua آخر يلعب عن طريق توليد إشارات أزرار لوحة الألعاب ، والتي تسمح للعبة بالتحكم في حركة الأشكال والجاذبية وكل شيء آخر.تؤدي إضافة الجاذبية إلى توسيع مساحة البحث بشكل كبير ، مما يجبر الذكاء الاصطناعي على مراعاة القواعد الماكرة للتلاعب بالأشكال. يتم وصف تفاصيل هذه القواعد في الجزء الأول من المقالة ، ويمكن تقديرها بالكامل من خلال دراسة مباشرة للكود. فيما يلي أهمها:
- : , .
- «» .
- «» «» .
- .
- .
- .
- .
- , .
- A B .
- «» «» 6 16 . «» «» , .
- «» 3 .
- 96 . , — .
لاستيعاب جميع هذه القواعد ، يجب تضمين المعلومات التاريخية في حالات البحث. يحتاجون إلى حقول يتم فيها تخزين عدد الإطارات المعلقة لكل زر وعدد الإطارات بعد آخر إصدار تلقائي. تميز كل مجموعة فريدة من القيم ، بما في ذلك الإحداثيات x، yودوران tetrimino حالة منفصلة وفريدة. لسوء الحظ ، فإن عدد الاحتمالات كبير للغاية لدرجة أن البحث الكامل عن هذه المساحة غير عملي. تستكشف نسخة AI الخاصة بلوحة الألعاب مجموعة فرعية فقط منها.يستخدم AI كائنًا Stateمع الحقول التالية: { x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor }
بدلاً من استخدام التحول التلقائي للذكاء الاصطناعي في الإطارات البديلة ، اضغط على زر التحول ثم حرره. لذلك ، يحتاج فقط إلى مراقبة ما إذا كان الزر مضغوطًا ، وليس طول الضغط عليه. نظرا لعدم التناوب التلقائي، وتنطبق نفس الفكرة إلى أزرار A و B. لذا الميدان Left، Right، Aو Bيمكن أن تفسر على أنها سرد يحتوي على إحدى القيم التالية: { RELEASED, PRESSED }
من ناحية أخرى ، بالنسبة للنزول الناعم ، يجب عليك أولاً الضغط باستمرار على الزر "لأسفل" لثلاثة إطارات ، الأمر الذي يتطلب وجود 4 حالات: { RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES }
Downيزداد تدريجياً من القيمة RELEASEDإلى PRESSED_FOR_3_FRAMES، حيث يحدث نزول ناعم. بعد ذلك ، يمكن أن تتلقى قيمة RELEASEDأو تعود إليها PRESSED_FOR_2_FRAMES، مما يسبب نزولًا ناعمًا كل إطار ثان بعد التأخير الأولي. لا يمكن أن يكون RELEASEDمن PRESSED_FOR_1_FRAMEأو من PRESSED_FOR_2_FRAMES.في الواقع ، يستخدم رمز لوا ثابت عدد صحيح ، ولكن المبدأ هو نفسه.وبالمثل، visitedو predecessor، fallTimerيتم تعيينه القيمة التي تم الحصول عليها عند الكتابة في ولاية طابور الفرعية؛ أنه fallTimerسيكون واحدا أكثر من قيمة الدولة الأم. شرط يحتوي علىfallTimer، يساوي سرعة الهبوط ، يعني أن الهبوط التلقائي يحدث في هذا الإطار ، وبالنسبة للحالات اللاحقة من هذه الحالة fallTimerستكون القيمة 0.كل Searcherتعريف مسبق 8-لصفيف يحتوي على جميع الحالات الممكنة ( 20 × 10 × 4 × 2 × 2 × 4 × 2 A × 2 B) ، ويتم تنفيذ BFS بشكل مشابه للطريقة المعروضة Slide = (Left == PRESSED) or (Right == PRESSED) Rotate = (A == PRESSED) or (B == PRESSED) if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then if Down == RELEASED then nextDown = PRESSED_FOR_1_FRAME else nextDown = PRESSED_FOR_2_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end if Slide then addChild() if not Rotate then addChild(A = PRESSED) addChild(B = PRESSED) end else addChild(Left = PRESSED) addChild(Right = PRESSED) if not Rotate then addChild(Left = PRESSED, A = PRESSED) addChild(Left = PRESSED, B = PRESSED) addChild(Right = PRESSED, A = PRESSED) addChild(Right = PRESSED, B = PRESSED) end end else if Down == PRESSED_FOR_1_FRAME then nextDown = PRESSED_FOR_2_FRAMES else nextDown = PRESSED_FOR_3_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end end
كما هو موضح في الكود الزائف أدناه ، addChildتأخذ الوظيفة في الاعتبار ترتيب الأحداث التي تحدث في كل إطار (على سبيل المثال ، التحول والتناوب والنزول). nextFallTimer = fallTimer + 1 if Left == PRESSED and testPosition(x - 1, y, rotation) then x = x - 1 elseif Right == PRESSED and testPosition(x + 1, y, rotation) then x = x + 1 end if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then rotation = nextClockwiseRotation elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then rotation = nextCounterclockwiseRotation end if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then if testPosition(x, y + 1, rotation) then y = y + 1 nextFallTimer = 0 else lockTetrimino() return end end childState = states[y][x][rotation][Left][Right][Down][A][B] if not childState.visited then childState.visited = mark childState.predecessor = state childState.fallTimer = nextFallTimer queue.enqueue(childState) end
كما في الإصدار السابق ، تقوم AI.searchبإرجاع سلسلة من الكائنات State. ولكن في هذه الحالة ، Stateيحتوي كل منها على العديد من الأزرار التي يجب الضغط عليها في كل إطار. الحقول x، yولا يتم rotationاستخدامها لمعالجة الأشكال ، ولكن يمكن استخدامها للتحقق من الحركة الصحيحة للأشكال.على الرغم من تقليص مساحة البحث بشكل كبير بسبب القيود الموضحة أعلاه ، يستغرق إكمال البحث من 1 إلى 3 ثوانٍ. إذا قمت بتشغيله ، ستلاحظ وقفة بعد إنشاء كل tetrimino. بالإضافة إلى ذلك ، تبدو الحركات غير طبيعية للغاية. عادة ما يتم إجراء منعطف فوري قبل القفل. ومع ذلك ، يلعب هذا الذكاء الاصطناعي تقريبًا نفس طريقة الإصدار الذي تجاهل الجاذبية ، حتى بأقصى سرعة.للتحقق من ذلك ، قم بتشغيله lua/NintendoTetrisAIGamepadVersion.lua، الموجود في ملف مضغوط مع المصادر .طريقة أبسط لحساب الجاذبية هي الحد من حركة الأشكال فقط عن طريق الدوران ، يليه التحول ، ثم النزول إلى الأسفل. الفكرة هي أنه إذا تخلصت من الانزلاق والتمرير ، فإن السرعة الرأسية للأرقام لن يكون لها تأثير يذكر على الذكاء الاصطناعي ؛ كل ما يحتاجه هو تسليم الرقم إلى العمود المطلوب ، وستقوم الجاذبية بالباقي. ميزة أخرى لهذه التقنية هي أن مساحة البحث صغيرة جدًا ، مما يسمح لك باللعب في الوقت الفعلي ، دون تأخير للحسابات. ومع ذلك ، فإن العيب في هذا النهج هو أنه بدون الانزلاق والتمرير ، يلعب الذكاء الاصطناعي أسوأ بكثير. ومع ذلك ، فإن Tetris AI ، غير قادر على اللعب في الوقت الحقيقي ، لا قيمة له عمليًا.إضافة
في وقت سابق ، كتبت مكونًا إضافيًا يحاكي لاعبًا في Tetris إجرائيًا. ومع ذلك ، كان لمشروعي بعض العيوب:- قام البوت بإيقاف تشغيل الجاذبية ، مما يسمح لك بأداء الإنزلاق والتمرير ، متجاوزًا قدرات اللاعب عند الحد الأدنى من Nintendo Tetris. لم يقم أبدًا برفع الأرقام لأسفل ، ولكن الطريقة الوحيدة لخفض الأرقام لأسفل هي الهبوط الناعم الخاضع للرقابة. أي أنه يلعب في عالم نظري ومثالي. بصراحة ، يغش.
- . — , . Double, Triple Tetris, — , . 90. , , 29 - .
- . . . , Tetris .
في هذا القسم ، سأتحدث عن روبوت متقدم يلعب نينتندو تتريس دون تعطيل الجاذبية. يقوم بتقييم المخاطر وإدارتها ، ويسعى جاهدًا للحصول على أقصى عدد من النقاط قبل الوصول إلى سرعة نزول عالية.
فيديو
شاهد البوت يكسب الحد الأقصى من نقاط Nintendo Tetris بدءًا من المستوى 19 في جميع مقاطع الفيديو الموضحة أدناه.
تنزيل
TetrisAI_2018-01-28.zip يحتويالملف .zipعلى:src - شجرة رمز المصدر.TetrisAI.jar - ملف ثنائي مترجم.lgpl-2.1.txt - رخصة البرمجيات الحرة.
إطلاق
المتطلبات الأساسية
- Nintaco هو محاكي NES / Famicom.
Tetris (U) [!].nes - ملف Nintendo Tetris ROM.
إطلاق البرنامج المساعد
- قم بتشغيل Nintaco وفتح
Tetris (U) [!].nes. - مقتطف
TetrisAI.jarمن التنزيل .zip. - افتح نافذة Run Program باختيار Tools | تشغيل البرنامج ...
- JAR Find JAR… .
- Load JAR, .
- Run.
- ,
GAME TYPE MUSIC TYPE . D-pad ( ) A-TYPE . Start (Enter), . A-TYPE D-pad ( ) LEVEL 9 . , A Start ( X Enter), 19, .
تجدر الإشارة إلى أن البوت مصمم فقط للمستوى 19 وما فوق. في المستويات الدنيا ، لن يتمكن من التحكم في القطع.مرجع السرعة
لتشغيل اللعبة بشكل أسرع ، حدد Machine | السرعة | ماكس
التفاصيل
هضبة
تحت المستوى 10 ، تكون سرعة الهبوط في كل مستوى أعلى قليلاً من المستوى السابق. ولكن عند المستوى 10 وما فوق ، هناك العديد من الهضاب التي تظل فيها السرعة ثابتة لعدة مستويات. هذا نتيجة الطريقة التي تعمل بها آلية الزناد. يتم تقديم السرعة على أنها عدد الإطارات لكل نزول ، وهي قيمة عددية. أي ، بالنسبة للمستويات الأعلى ، لا يوجد العديد من الخيارات المتبقية: 10-12 ، 13-15 ، 16-18 ، 19-28 و 29+ هي 5 ، 4 ، 3 ، 2 ، وإطار واحد للنزول.تم تطوير البوت مع مراعاة هضبة 19-28 فقط. في الإطارات الزوجية ، ينقر على لوحة الألعاب "Left" أو "Right" أو A أو B أو لا شيء. وفي الإطارات الفردية ، يسمح بالنزول التلقائي دون الضغط على أي أزرار. يبدو أن اللعبة لا تدرك الحركة الأفقية التي تتزامن مع الدوران ؛ لذلك ، يتم الضغط على كل زر بشكل مستقل في الإطارات الزوجية.على عكس الأساتذة الذين يلعبون على مستويات عالية ، لا يستفيد البوت من التحول المؤجل (DAS) ، المعروف أيضًا باسم التكرار التلقائي ، والتقنيات ذات الصلة. عمله يذكرنا أكثر بتقنية الإبهام الاهتزازية لثور أكيرلوند . ومع ذلك ، فإنه يزيد من تردد الاهتزاز إلى الحد الأقصى النظري الذي تسمح به اللعبة.يكافأ اللاعبون بـ 40 و 100 و 300 و 1200 نقطة للفرد والمزدوج والثلاثي وتتريس. ويتم ضرب النقاط في رقم المستوى بالإضافة إلى 1. وبعبارة أخرى ، للحصول على أقصى درجة ، يجب على اللاعب أن يسعى للحصول على أقصى عدد من Tetris ، حيث يلعب لأطول فترة ممكنة عند مستويات عالية.المستوى 19 هو أعلى مستوى يمكن اختياره على أنه المستوى الأولي ، والذي يسمح للبوت بالقفز مباشرة إلى الهضبة 19-28. ومع ذلك ، نظرًا لوجود خطأ في آلية حساب المستوى التي ذكرتها في الجزء السابق ، ستنتقل اللعبة إلى المستوى 20 بعد مسح 140 صفًا ، بدلاً من 200 صف متوقع. وبعد ذلك ، ستغير اللعبة المستويات كل 10 صفوف. ومع ذلك ، بعد الوصول إلى 230 صفًا ، سوف يرتفع البوت من الهضبة ويستسلم بسرعة. أي أنه يحتاج إلى طلب أكبر عدد ممكن من Tetris قبل تنظيف 230 صفًا.أصل ناعم
يمكن أن يزيد النسب اللين أيضًا عدد النقاط. للحصول على نقاط ، يجب خفض الرقم برفق ليغلق على أرض الملعب. أي نزول ناعم قصير المدى يحدث على طول الطريق عند وضع الرقم لن يؤثر على النتيجة. إذا نجح الهبوط ، سيحصل اللاعب على نقطة واحدة لكل خط يتم تجاوزه أثناء الهبوط الناعم. ولا يتم ضرب القيمة الناتجة في رقم المستوى ، حتى إذا أدى الهبوط الناعم إلى مسح الصفوف.النسب اللين له تأثير ضئيل على النتيجة الإجمالية. ومع ذلك ، إذا كان ذلك ممكنًا ، يكمل البوت وضع الرقم عن طريق النقر على "أسفل" للحصول على هذه النقاط. في حالات نادرة ، يمكنه متوسط الفرق بين درجة عالية جدًا وتجاوز الحد الأقصى للدرجة.خوارزمية الذكاء الاصطناعي
عند إنشاء شكل ، يستكشف البوت كل موضع ممكن للأشكال الحالية والتالية. الموضع المسموح به هو الوضع الذي يرتكز فيه الشكل إما على الخلايا المشغولة أو على أرضية الملعب. من مكان إنشاء الشكل ، يمكن الوصول إلى هذا الموقف من خلال سلسلة من الحركات الأفقية والانعطافات والنزول. تم العثور على مواقع صالحة وتسلسلات مسار باستخدام BSF.إن وضع قطعة على أرض الملعب له عواقب: 4 خلايا فارغة مشغولة ، ويتم مسح جميع الصفوف المملوءة ، والسماح للصفوف بالنزول. لكل موضع مسموح به للرقم الحالي والعواقب المرتبطة به ، يقوم البوت بفحص كل موضع صالح للرقم التالي ، وتقييم مجموعة النتائج. يتم تقديم سلسلة البحث هذه SearchChain.يتم نقل كل من النتائج المجمعة إلى دالة التقييم التي تحسب محتويات الملعب. تركيبة مع أقل درجة تفوز والقطعة الحالية توضع وفقًا لذلك. نتائج سلسلة البحث تؤثر فقط على الشكل الحالي. عند إنشاء الشكل التالي ، يتم تقييمه مع الشكل الذي يليه ، وهكذا.دالة التقييم
دالة التقييم هي مجموع مرجح للمعلمات التالية:- العدد الإجمالي للصفوف التي تم مسحها هو عدد الصفوف التي تم مسحها بإضافة كل من tetriminos.
- – , . — , , .
- - – .
- – , -.
- – , . . .
- – . , 1. , , .
- – , . — , — .
- – . , (20).
- – . , 0.
- – , ( ) .
- : — , ( ) . . . .
- – . , 1 , 1, — 0.
- – .
- – .
- – .
- – . .
- – .
التعلم الآلي
للعثور على أوزان دالة التقييم ، استخدمنا متغيرًا لطريقة تحسين سرب الجسيمات (PSO) الموضحة في الحاشية السفلية [1]. للحصول على سلوك التقارب الجيد ، يتم تطبيق معاملات القصور الذاتي والتسارع. ويتم تحديد الأحجام القصوى لخطوات الجسيمات عن طريق تحديد قيم سرعتها.خلال كل تكرار ، تم تقييم الجسيمات بالتوازي للاستفادة الكاملة من موارد الحوسبة المتاحة. بالإضافة إلى ذلك ، بعد اكتشاف التقارب (لم يحدث تحسن بعد عدد معين من التكرارات) ، تم ضبط PSO على إعادة التشغيل تلقائيًا بأوزان مختارة عشوائيًا ، مما سمح لنا بمزيد من استكشاف مساحة البحث.تم تقييم كل متجه موقف الجسيمات عن طريق محاكاة الانتهاء من 100 دفعة على هضبة من المستويات 19-28. تتضمن المجموعة الكاملة تنظيف 230 صفًا ، ولكن انتهى العديد منها بتدفق الحقل. تم فرز درجات الدُفعة ، وتم تحديد درجات الجسيمات كمتوسط 33 دفعة من أصل 100 دفعة. كانت الفكرة هي الاختيار على أساس العدوانية. تعتاد الجسيمات في الثلث العلوي فقط على التسلسلات المرغوبة من الأرقام ، مما يحد من الحاجة إلى لعبة محافظة. نتيجة لذلك ، يميلون إلى دفع اللعبة المعتادة إلى حافة الهاوية ، في انتظار "العصا" التالية.تم إنشاء تسلسلات الأنماط لـ 100 مجموعة قبل PSO ، وتم استخدام نفس التسلسلات مرارًا وتكرارًا. كان ذلك ضروريًا لإصلاح مساحة البحث ، بحيث يمكن مقارنة خيارات الحل مع بعضها البعض. تم إنشاء التسلسلات باستخدام منطق PRNG Nintendo Tetris الحقيقي ، والذي تم تصميمه لتقليل فرص التكرار بعد بعضها البعض. لكن PRNG لديها أيضًا نقاط ضعف (انظر قسم "اختيار Tetrimino" من مقال سابق): لا تحدد الأرقام بالتساوي.أدت المحاولات الأولية إلى أن الروبوتات تعمل بقوة. إذا تغلبوا على الهضبة 19-28 ، فعادة ما يحصلون على الدرجة القصوى. ولكن ، لسوء الحظ ، غالبًا ما أدت في وقت مبكر جدًا إلى تجاوزات الحقل. رداً على ذلك ، تم اتخاذ أربع خطوات "لتهدئة" البوتات:- : Tetris, . «» . . ; 230 . , Tetris . Single, Double Triple. ; .
- . , , 7 . .
- , , . , 7 .
- , , . , . , .
بعد تطبيق كل هذه القواعد لتهدئة البوتات ، أعطت طريقة PSO الأوزان التالية:| معلمة | الوزن |
|---|
| تم مسح إجمالي عدد الصفوف | 0.286127095297893900 |
| إجمالي ارتفاع الحجب | 1.701233676909959200 |
| العدد الإجمالي لخلايا البئر | 0.711304230768307700 |
| إجمالي عدد الآبار العميقة | 0.910665415998680400 |
| العدد الإجمالي للثقوب في الأعمدة | 1.879338064244357000 |
| إجمالي ثقوب الأعمدة | 2.168463848297177000 |
| العدد الإجمالي لأعماق الثقب في الأعمدة | .260.265587111961757270 |
| الحد الأدنى لعمق ثقب العمود | 0.289886584949610500 |
| الحد الأقصى لعمق ثقب العمود | 0.362361055261181730 |
| العدد الإجمالي للتحولات في الأعمدة | −0.028668795795469625 |
| إجمالي يقفز الخط | 0.874179981113233100 |
| إجمالي ارتفاعات الأعمدة | .500.507409683144361900 |
| ارتفاع كومة الذاكرة المؤقتة | .12.148676202831281000 |
| مرتفعات العمود مبعثر | .181.187558540281141700 |
| العدد الإجمالي للخلايا المشغولة | .62.645656132241128000 |
| إجمالي العدد المرجح للخلايا المشغولة | 0.242043416268706620 |
| عمود مرتفعات التشتت | 0.287838126164431440 |
بما أن السلسلة تسعى إلى تركيبة تقلل من وظيفة التقييم ، يمكن اعتبار المعلمات التي لها أوزان إيجابية مكافآت ، والباقي - الغرامات. لكن الأوزان لا تظهر بالضرورة أهمية المعلمات المقابلة ؛ لم يتم تطبيعها ، لذلك لا يمكن مقارنتها.قوة الذكاء الاصطناعي
لتقييم قوة الذكاء الاصطناعي ، تم جمع ما يقرب من 1.7 مليون نتيجة (بالنقاط) من ألعاب المحاكاة على هضبة من 19 إلى 28. لا تعكس النتيجة اللعبة عند المستوى 29 أو أعلى ، ولا تأخذ في الاعتبار النقاط التي تم الحصول عليها من الأصل الناعم. ومع ذلك ، فإنه يشمل الألعاب التي تم الانتهاء منها قبل الأوان بسبب تجاوزات الملعب. تم استخدام منطق Nintendo Tetris PRNG لإنشاء تسلسلات Tetrimino.من بين هذه النتائج ، كانت أكبر درجة هي 1،313،600 ، والحد الأدنى هو 0.المتوسط هو 816،379 ، ويبدو أنه صغير. ولكن كما هو مذكور أدناه ، فإن البيانات مشوهة ، لذا فإن النتيجة المتوسطة 989200 نقطة تعطي فكرة أفضل عن القيمة النموذجية.كما هو مذكور أعلاه ، قام PSO بتحسين الأوزان بناءً على متوسط أفضل ثلث الدفعات. في هذه الحالة ، متوسط الدرجات لأفضل الثلث هو 1 108860. في الواقع ، متوسط الدرجات لأفضل 75٪ هو 1000000.البوت لديه احتمال 47٪ للوصول إلى حد النقطة إلى المستوى 29. لديه احتمال 61٪ من الحصول على 900000 نقطة ل 29. يوضح الرسم البياني أدناه احتمالات تسجيل حتى المستوى 29.يبدو أن الاحتمال ينخفض خطيًا إلى حوالي 900000 نقطة. ثم يذهب إلى منحنى سيني مقلوب.فيما يلي رسم بياني سلس مع عدد الأطراف لكل نقطة تم تسجيلها. يتم تحديد شكله من خلال مشتق الرسم البياني الموضح أعلاه.إذا تجاهلت التقلبات ، فإن ما يصل إلى حوالي 900.000 يكون مستويًا ، ثم ينتقل إلى التوزيع الطبيعي مع المركز حوالي 1.050.000 نقطة. أسباب التقلبات ليست واضحة. يبدو أن عدد النقاط يفضل القفز بزيادات قدرها 20000 نقطة. ربما يرجع ذلك إلى دورة بناء الكومة والحصول على تتريس.تخصيص ذاكرة الوصول العشوائي وذاكرة القراءة فقط
لمعالجة ذاكرة وحدة المعالجة المركزية ، ونقل نقرات الزر وتلقي أحداث عرض الإطار ، يستخدم المكون الإضافي واجهة برمجة تطبيقات Nintaco . تم اكتشاف جميع عناوين الذاكرة باستخدام أدوات تصحيح Nintaco ، وتمت إضافة المعلومات إلى Data Crystal ROMhacking.net wiki . في كود المصدر ، تبدو مثل الثوابت في الواجهة Addresses.
المراجع
- van den Bergh, F.; Engelbrecht, AP (2006)
A study of particle swarm optimization particle trajectories
In: Information Sciences 176 (2006) (pp. 937–971)
Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf