عن المشروع

MarkovJunior هي لغة برمجة احتمالية حيث تكون البرامج عبارة عن مجموعات من قواعد إعادة الكتابة ويتم الاستدلال عبر انتشار القيود. سُميت على اسم عالم الرياضيات أندريه أندرييفيتش ماركوف، الذي عرّف خوارزميات ماركوف. في شكلها الأساسي، برنامج MarkovJunior هو قائمة مرتبة من قواعد إعادة الكتابة. على سبيل المثال، يستخدم نموذج MazeBacktracker قاعدتين: `RBB=GGR` و `RGG=WWR`. في كل خطوة تنفيذ، يجد المفسر أول قاعدة لها تطابق على الشبكة، ويجد جميع التطابقات، ويطبق واحدة عشوائية. يتوقف المفسر عندما لا تتطابق أي قواعد. الاستدلال الاحتمالي يسمح بفرض قيود على الحالات المستقبلية، مما يولد فقط عمليات التشغيل التي تؤدي إلى مستقبلات مقيدة. على سبيل المثال، الاستدلال في قواعد سوكوبان يجعل الوكلاء ينظمون الصناديق في أشكال محددة. يتضمن المستودع العديد من المولدات الاحتمالية للأقبية والهندسة المعمارية والألغاز والمحاكاة. تشمل المفاهيم الأساسية: - **قواعد إعادة الكتابة**: قواعد بسيطة مثل `(B=W)` تحول المربعات السوداء العشوائية إلى بيضاء. قواعد أكثر تعقيدًا مثل `(WBB=WAW)` تولد متاهات بسطر واحد من التعليمات البرمجية. أحرف البدل (`*`) تسمح بأي لون في الإدخال أو الإخراج غير المتغير. - **عُقد القواعد**: تجمع بين قواعد متعددة، على سبيل المثال للمشي العشوائي الممحو الحلقي أو توليد متاهة ألدوس-برودر. - **عُقد التسلسل**: تشغيل عُقد القواعد واحدة تلو الأخرى، على سبيل المثال بناء مخططات فورونوي لوديان الأنهار. - **عُقد ماركوف**: تسمح بالعودة إلى العُقد السابقة، مما يتيح خوارزميات مثل توليد الأقبية لبوب نيستروم. - **الاستدلال**: يستخدم انتشار القيود (أحادي الاتجاه أو ثنائي الاتجاه) لربط الحالات، مع معامل درجة حرارة للصرامة. يمكنه حل ألغاز مثل سوكوبان أو توليد مسارات هاميلتونية. تشمل المواد الإضافية نظرة عامة على بناء جملة XML، ولقطات شاشة عالية الدقة، وملاحظات تقنية غير رسمية. يناقش المشروع مشكلات مفتوحة مثل تركيب البرامج للتوليد الإجرائي وتركيب النماذج من الأمثلة. يستشهد بتأثيرات من خوارزميات ماركوف، وإيماججرام، وريفال، وخرائط ديكسترا، والخوارزميات الكلاسيكية مثل بحث A*. يستخدم المفسر مطابقة أنماط سريعة مع خوارزمية بوير-مور متعددة الأبعاد ويدعم الاسترخاء العشوائي للتحسين القائم على التدرج.