🤖 AI

Strongly Solving 2048 4x3

تقدم هذه الورقة الحل القوي لنسخة 4×3 من لعبة 2048 العشوائية، والتي تحدد الدرجة المتوقعة المثلى بنحو 50,724.26 من خلال استخدام تقنية تقسيم قائم على العمر لإدارة فضاء حالتها الشاسع الذي يتجاوز 1.15 تريليون حالة يمكن الوصول إليها.

المؤلفون الأصليون: Tomoyuki Kaneko, Shuhei Yamashita

نُشر 2026-05-26

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Tomoyuki Kaneko, Shuhei Yamashita

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل لعبة الألغاز الشهيرة 2048 كأنها مطبخ فوضوي ضخم حيث تحاول دمج المكونات (البلاطات) لصنع أطباق أكبر وأكبر. في النسخة القياسية، لديك شبكة 4x4 (16 مكاناً). في هذه الورقة البحثية، قرر المؤلفون تصغير هذا المطبخ إلى شبكة 4x3 (12 مكاناً)، مما يجعل التحدي أكثر ضيقاً وازدحاماً.

إليك تفصيل بسيط لما فعلوه، وكيف فعلوه، وما وجدوه، باستخدام تشبيهات من الحياة اليومية.

1. التحدي الكبير: مكتبة ضخمة جداً للقراءة

أراد المؤلفون "حل النسخة الأصغر من اللعبة بشكل قوي". وبمصطلحات الألعاب، هذا لا يعني أنهم أرادوا معرفة أفضل حركة للبداية فحسب؛ بل أرادوا معرفة الحركة المثالية لكل موقف ممكن يمكن أن تصل إليه اللعبة.

تخيل مواقف اللعبة المحتملة كأنها مكتبة.

نسخة 3x3 الأصلية (Mini2048) كانت مثل رف كتب صغير يحتوي على حوالي 48,000 كتاب. سهلة القراءة.
أما نسخة 4x3 الجديدة فهي مكتبة ضخمة تحتوي على أكثر من 1.15 تريليون كتاب (حالات) وما يقرب من 740 مليار "كتاب وسيط" (حالات لاحقة).

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

2. الخدعة السحرية: "عمر" اللعبة

السر في نجاحهم كان مفهوماً أطلقوا عليه اسم "العمر" (Age).

تخيل أنك في كل مرة تلعب فيها اللعبة، فإنك تضيف وزناً إلى ميزان.

عندما تبدأ، يكون لديك بلاطتان (مثلاً، اثنتان من رقم 2). "العمر" هو مجموع كل الأرقام على اللوحة (2 + 2 = 4).
عندما تقوم بتحريك البلاطات ودمجها، تتضاعف الأرقام، لكن العمر يبقى كما هو تماماً. (دمج اثنين من رقم 2 ليصبحا 4 لا يغير المجموع الكلي).
الوقت الوحيد الذي يتغير فيه العمر هو عندما يقوم الكمبيوتر عشوائياً بإسقاط بلاطة جديدة (2 أو 4). هذا يضيف 2 أو 4 إلى العمر.

التشبيه:
فكر في اللعبة ليس كمتاهة، بل كمبنى متعدد الطوابق.

كل "طابق" في المبنى يمثل عمراً معيناً (مثلاً: الطابق 4، الطابق 6، الطابق 8...).
يمكنك التحرك بحرية داخل نفس الطابق (تحريك ودمج البلاطات) دون الصعود أو الهبوط.
أنت تنتقل فقط إلى الطابق التالي عندما يسقط الكمبيوتر بلاطة جديدة.

بما أن اللعبة تتحرك دائماً للأمام في العمر (أنت لا تعود أبداً إلى مجموع أقل)، استطاع المؤلفون التعامل مع المكتبة طابقاً تلو الآخر. لم يحتاجوا للاحتفاظ بالمكتبة بأكملها في ذاكرتهم دفعة واحدة. كانوا يحتاجون فقط للاحتفاظ بالطابق الحالي، والطابق التالي، والطابق الذي يليه. بمجرد انتهائهم من حساب أفضل الحركات للطابق 100، يمكنهم التخلص من بيانات الطابق 98 لإفساح المجال للطابق 102.

3. الضغط: وضع حوت في حقيبة ظهر

حتى مع خدعة "الطابق تلو الآخر" هذه، كانت البيانات لا تزال ضخمة. لو حاولوا كتابة كل حالة للعبة على الورق، فسيستغرق ذلك مساحة تقارب 4.4 تيرابايت من مساحة القرص الصلب (أي ما يعادل حجم مركز بيانات ضخم).

لحل هذه المشكلة، استخدموا تقنية ضغط بيانات ذكية تسمى ترميز إلياس-فانو (Elias-Fano coding).

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

4. النتائج: ماذا تعلموا؟

من خلال حل اللعبة، قاموا بحساب الدرجة المتوقعة المثالية للاعب لا يرتكب أي خطأ.

النتيجة: إذا بدأت بالإعداد الأكثر شيوعاً (اثنان من رقم 2) ولعبت بشكل مثالي، يمكنك توقع الحصول على حوالي 50,724 نقطة.
عامل "سوء الحظ": وجدوا أن البدء ببلاطة رقم 4 بدلاً من اثنتين من رقم 2 يضعك في موقف أقل حظاً قليلاً (أقل بنحو 4 نقاط). الأمر يشبه بدء سباق بحمل حقيبة ظهر ثقيلة؛ عليك العمل بجهد أكبر لتعويض الفارق.
عقبة الـ "2048": أظهر الرسم البياني لنتائجهم "وديان" (انخفاضات في الأداء) كلما وصل العمر إلى مضاعفات 2048. وهذا يؤكد شعور العديد من اللاعبين: يصبح من الصعب للغاية الوصول إلى بلاطة 2048 لأنك تنفد من المساحة على لوحتك الصغيرة المكونة من 12 مربعاً. أنت بحاجة إلى ترتيب مثالي لتتسع لجميع الأرقام الأصغر (2، 4، 8... وصولاً إلى 1024) قبل أن تتمكن من دمجها.

ملخص

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

لقد أثبتوا أنه باستخدام كمبيوتر قياسي وعمل يستغرق بضعة أيام، يمكنك رياضياً إتقان لعبة تعتمد عادةً على الحظ والحدس.

ملخص تقني: الحل القوي للعبة 2048 على لوحة 4×3

تعريف المشكلة

تتناول هذه الورقة البحثية "الحل القوي" لنسخة عشوائية من لعبة لاعب واحد: لعبة 2048 على لوحة 4×3 (يُرمز لها بـ 2048 $^{4\times3}$ ). بخلاف نسخة 4×4 القياسية، تستخدم هذه النسخة شبكة مكونة من 12 خلية. يتم نمذجة اللعبة كعملية اتخاذ قرار ماركوف (MDP) حيث يختار الوكيل إجراءات (أعلى، أسفل، يسار، يمين) لدمج البلاطات المتجاورة ذات القيم المتساوية. بعد أي إجراء صالح، تنتقل حالة اللوحة حتمياً إلى "حالة لاحقة" (afterstate) (انزلاق ودمج البلاطات). بعد ذلك، تقوم البيئة عشوائياً بإنشاء بلاطة جديدة (القيمة 2 باحتمال 90%، والقيمة 4 باحتمال 10%) في خلية فارغة عشوائية، مما يؤدي إلى الانتقال إلى الحالة التالية.

الهدف هو حساب السياسة المثلى $\pi^*$ ودالة القيمة المثلى $v^*(s)$ ، والتي تمثل المكافأة التراكمية المتوقعة من أي حالة $s$ يمكن الوصول إليها. يكمن التحدي الرئيسي في حجم فضاء الحالات: تحتوي نسخة 4×3 على ما يقرب من $1.15 \times 10^9$ حالة يمكن الوصول إليها و $7.4 \times 10^8$ حالة لاحقة. هذا النطاق أكبر بنحو $10^4$ مرة من نسخة 3×3 التي تم حلها سابقاً (Mini2048)، مما يجعل عمليات الحصر والتخزين المباشرة غير ممكنة على الأجهزة القياسية.

المنهجية

يقترح المؤلفون حلاً يعتمد على تقسيم فضاء الحالات حسب "العمر" (age) والتمثيل البياني المدمج.

1. التقسيم القائم على العمر

الابتكار الجوهري هو تعريف عمر الحالة على أنه مجموع جميع أرقام البلاطات على اللوحة ( $age(s) = \sum c_i$ ).

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

2. التمثيل المدمج

للتعامل مع متطلبات التخزين (المقدرة بنحو 4.4 تيرابايت لمعرفات 48 بت الخام)، يستخدم المؤلفون أكواد إلياس-فانو (Elias-Fano codes) لتخزين مجموعات معرفات الحالات الفريدة.

الهيكل: يتم تقسيم المعرفات الفريدة المرتبة إلى بتات عالية الرتبة ( $h_i$ ) وبتات منخفضة الرتبة ( $l_i$ ). تُخزن البتات المنخفضة في متجه بت متصل، بينما يتم ترميز البتات العالية في متجه بت متفرق $H$ باستخدام عمليات التصنيف (rank).
التحسينات:
- تقليل التماثل: يتم تطبيع المعرفات إلى الحد الأدنى من القيم بين التماثلات الأفقية والرأسية وتماثل الدوران 180 درجة.
- تكييف القاعدة: يتم تعديل قاعدة الترميز بناءً على أقصى قيمة للبلاطة لعمر محدد.
- إسقاط الخلية: يتم إسقاط معلومات خلية واحدة أثناء الترميز لأن المجموع (العمر) يقيد الإجمالي، مما يسمح بإعادة البناء الكامل لاحقاً.
الكفاءة: يقلل هذا من تخزين جميع معرفات الحالات اللاحقة من ~4.4 تيرابايت إلى حوالي 1.4 تيرابايت مع الحفاظ على قدرات البحث الفعال. بالنسبة للعب الأمثل تحديداً، يقلل تمثيل متخصص (باستخدام خوارزمية BuRR) المتطلبات إلى أقل من 300 جيجابايت.

النتائج الرئيسية

إحصائيات فضاء الحالات: إجمالي عدد الحالات التي يمكن الوصول إليها هو 1,152,817,492,752، وعدد الحالات اللاحقة هو 739,648,886,170.
الدرجة المتوقعة المثلى: بالنسبة لأكثر الحالات الأولية شيوعاً (بلاطتان بقيمة 2)، فإن الدرجة المتوقعة تحت استراتيجية مثلى هي حوالي 50,724.26.
- الحالات الأولية التي تبدأ ببلاطة بقيمة 4 (عمر 6) تعطي درجة متوقعة أقل قليلاً (~50,720.62).
- الحالات الأولية التي تبدأ ببلاطتين بقيمة 4 (عمر 8) تعطي الدرجة الأقل (~50,708.99)، مما يشير إلى عيب طفيف في البدء ببلاطات ذات قيم أعلى.
توزيع الحالات: عدد الحالات لكل عمر قابل للإدارة بشكل عام (أقل من $3 \times 10^6$ لكل عمر)، مما يسمح للخوارزمية بالاحتفاظ بعدة طبقات عمر في الذاكرة.
الحالات النهائية: تحدث "وديان" في توزيع عدد الحالات عند الأعمار التي هي مضاعفات لـ 2048، مما يعكس صعوبة تشكيل بلاطات كبيرة بمساحة لوحة محدودة. بعض الأعمار (مثل 8190، 12286) لديها صفر حالات لاحقة صالحة لأن تشكيل تلك المجاميع يتطلب بلاطات أكثر مما تسمح به الـ 12 خلية المتاحة.
حساسية الإجراء: يبلغ الفرق في القيمة بين الإجراءات المثلى وغير المثلى ذروته بالقرب من الأعمار 2048 و 4096، مما يشير إلى أن القرارات المبكرة مباشرة بعد تشكيل بلاطات كبيرة هي قرارات حاسمة.

الأهمية والادعاءات

تدعي الورقة أنها قامت بحل قوي لنسخة 2048 $^{4\times3}$ ، وهي مهمة كانت تعتبر سابقاً مستعصية بسبب حجم فضاء الحالات. تكمن أهمية هذا العمل في:

القابلية للتوسع: إثبات أن لعبة تحتوي على أكثر من $10^9$ حالة يمكن حلها على جهاز كمبيوتر شخصي في غضون أيام قليلة من خلال الاستفادة من الخصائص الهيكلية للعبة (العمر) بدلاً من طرق البحث الشامل (brute-force).
المساهمة المنهجية: يسمح تقديم تقنية تقسيم "العمر" بحصر وحساب قيم عمليات اتخاذ القرار الماركوفية (MDPs) العشوائية حيث تعتمد قيم الحالات على التوقعات، مما يتجاك بفعالية الحاجة إلى تقليم $\alpha\beta$ (الذي يكون غير فعال في البيئات العشوائية).
توافر البيانات: يقدم المؤلفون دالة القيمة المثلى وتمثيلاً مدمجاً لفضاء الحالات، مما يعمل كخط أساس لأبحاث التعلم المعزز وتحليل الألعاب في المستقبل.
كفاءة التخزين: إن التطبيق الناجح لأكواد إلياس-فانو لضغط مجموعة ضخمة من حالات اللعبة إلى ~1.4 تيرابايت يجعل مجموعة البيانات متاحة للباحثين الذين يمتلكون موارد حوسبة متوسطة (مثل أقراص SSD بسعة 4 تيرابايت).

يشير المؤلفون إلى أنه بينما كان الهدف الأساسي هو حل اللعبة، فإن مجموعة البيانات الناتجة ومفهوم "العمر" قد يشكلان أساساً لمزيد من الدراسات في الألعاب العشوائية وتقييم التعلم المعزز.