بيرلكامب يغير أسلوب لعبه

لعبة بيرلكامب للتبديل هي لعبة رياضية اقترحها عالم الرياضيات الأمريكي إلوين بيرلكامب . ^{[ 1 ]} تُعرف أيضًا باسم لعبة غيل-بيرلكامب للتبديل ، نسبةً إلى ديفيد غيل الذي اكتشفها بشكل مستقل، ^{[ 2 ]} أو لعبة الأضواء غير المتوازنة . ^{[ 3 ]} تتضمن اللعبة نظامًا من المصابيح الكهربائية يتم التحكم فيه بواسطة مجموعتين من المفاتيح، حيث يحاول أحد اللاعبين تشغيل أكبر عدد ممكن من المصابيح بينما يحاول الآخر إبقاء أكبر عدد ممكن منها مطفأً. يمكن استخدامها لتوضيح مفهوم نصف قطر التغطية في نظرية الترميز .

تتكون معدات لعب اللعبة من غرفة تحتوي على مجموعة مستطيلة من المصابيح الكهربائية، بأبعاد${\displaystyle a\times b}$بالنسبة لبعض الأرقام${\displaystyle a}$و${\displaystyle b}$بنك من${\displaystyle ab}$تتحكم مفاتيح على أحد جانبي الغرفة بكل مصباح على حدة. يؤدي قلب أحد هذه المفاتيح إلى تغيير حالة المصباح من مطفأ إلى مضاء أو العكس، حسب حالته السابقة. وعلى الجانب الآخر من الغرفة توجد مجموعة أخرى من${\displaystyle a+b}$مفاتيح، واحد لكل صف أو عمود من المصابيح. عند تشغيل أي من هذه المفاتيح، يتغير وضع كل مصباح في الصف أو العمود الذي يتحكم به من مطفأ إلى مضاء أو العكس، حسب حالته السابقة. عند تشغيل أكثر من مفتاح، لا يؤثر ترتيب التشغيل على النتيجة: ستظل المصابيح نفسها مضاءة في نهاية سلسلة التشغيل بغض النظر عن ترتيب التشغيل.

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

عمل بيرلكامب في مختبرات بيل في موراي هيل، نيو جيرسي، من عام 1966 إلى عام 1971. ^{[ 4 ]} وخلال فترة عمله هناك، قام بتصميم نموذج مادي لهذه اللعبة لعرضه في العلبة.${\displaystyle 10\times 10}$في غرفة الاستراحة بقسم الرياضيات. ^{[ 1 ] [ 2 ]} كما اخترع ديفيد غيل اللعبة بشكل مستقل، في وقت ما قبل عام 1971. ^{[ 5 ]}

تضمنت الأبحاث المبكرة حول المشكلات ذات الصلة منشورات أندرو إم. جليسون ( 1960 ) ، والذي يمكن تفسير تجاربه الحاسوبية على أنها طلب، من أجل ${\displaystyle 15\times 15}$في هذه اللعبة، مدى جودة أداء اللاعب الثاني ضد لاعب أول يلعب عشوائيًا، ^{[ 6 ]} وقد تناول جيه دبليو مون وليو موزر ( 1966 ) سؤال جليسون نظريًا، موضحين أنه بالنسبة لجميع خيارات اللاعب الأول تقريبًا، في حالة أحجام رقعة اللعبة الكبيرة، تكون قيمة اللعبة المثلى قريبة من ${\displaystyle {\tfrac {1}{2}}n^{2}}$[ ^{7 ]​}

رياضياً، يمكن وصف الأضواء التي أضاءتها حركة اللاعب الأول بأنها مجموعة${\displaystyle S}$وأقل عدد من الأضواء التي يمكن تحقيقها من خلال أفضل أداء للاعب الثاني كرقم${\displaystyle f(S)}$أفضل خيار للاعب الأول هو اختيار مجموعة${\displaystyle S}$الذي يحقق أقصى قدر${\displaystyle f(S)}$لذلك، يمكن وصف أكبر عدد من الأضواء التي يمكن تحقيقها من خلال أفضل أداء للاعب الأول بأنه عدد${\textstyle R_{a,b}=\max _{S}f(S)}$وبعيدًا عن مسألة كيفية اللعب الجيد في لعبة فردية، فإن السؤال الأوسع الذي كان موضوعًا للبحث الرياضي هو تحديد قيمة${\displaystyle R_{a,b}}$بشكل عام، كدالة لـ${\displaystyle a}$و${\displaystyle b}$، لتحديد سلوكها كدالة، أو لحساب قيمتها لأكبر عدد ممكن من تركيبات${\displaystyle a}$و${\displaystyle b}$قدر الإمكان.

حالة المربع${\displaystyle n\times n}$تم حل المصفوفة لـ${\displaystyle n\leq 12}$بالإضافة إلى ذلك، الحدود الدنيا لـ${\displaystyle R_{n,n}}$لم يتم العثور على${\displaystyle n\leq 20}$[ ^{8 ] [ 9 ] [ 10 ] [ 11 ] هذه} الأرقام هي:

حلول لـ${\displaystyle n\times n}$

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${\displaystyle R_{n,n}}$	0	1	2	4	7	11	16	22	27	35	43	54	≥ 60	≥ 71	≥ 83	≥ 96	≥ 107	≥ 122	≥ 139	≥ 148

تتزايد هذه الأرقام بشكل تقاربي مع${\displaystyle {\tfrac {n^{2}}{2}}-\Theta (n^{3/2})}$[ ^{2 ] [ 5 ] [ 12 ]​}

نظراً لوجود عدد هائل من الخيارات فيما يتعلق بالمفاتيح التي يجب قلبها، فإن البحث الشامل عن الخيار الأمثل غير ممكن بالنسبة للأجهزة الكبيرة${\displaystyle n}$، مما يطرح السؤال حول مدى قدرة اللاعبين ذوي القدرات الحسابية المحدودة على لعب هذه اللعبة.

يمكن للاعب الأول أن يتسبب في أن تكون القيمة المتوقعة للعبة${\displaystyle {\tfrac {n^{2}}{2}}-O(n^{3/2})}$عن طريق اللعب عشوائياً. وبالمثل، يمكن للاعب الثاني الحصول على قيمة يكون متوسط ​​المسافة المتوقعة منها${\displaystyle {\tfrac {n^{2}}{2}}}$يكون${\displaystyle \Omega (n^{3/2})}$عن طريق اللعب عشوائياً؛ قد تكون هذه القيمة أكبر أو أصغر من${\displaystyle {\tfrac {n^{2}}{2}}}$لكن إذا كانت القيمة أكبر، يمكن للاعب الثاني قلب جميع مفاتيح الصفوف للحصول على قيمة أصغر بنفس المقدار. ^{[ 2 ] [ 5 ] [ 12 ]} يمكن جعل هذه الاستراتيجية العشوائية للاعب الثاني غير عشوائية باستخدام طريقة الاحتمالات الشرطية ، مما يوفر خوارزمية ذات زمن متعدد الحدود تضمن نفس قيم الحل. وتؤدي عملية إزالة عشوائية مختلفة إلى خوارزمية متوازية في فئة التعقيد NC . ^{[ 13 ]}

يُعدّ إيجاد الخيار الأمثل للاعب الثاني في اللعبة، بعد أن يختار اللاعب الأول المصابيح التي سيضيئها، مسألةً صعبة الحل (NP-hard) . ^{[ 14 ]} ومع ذلك، توجد طريقة تقريبية متعددة الحدود لحل هذه المسألة.${\displaystyle n\times n}$لعبة يمكنها إيجاد خيار للاعب الثاني لا يترك سوى${\displaystyle (1+\varepsilon )}$مضروبًا في الحد الأدنى الممكن لعدد المصابيح المضاءة، لأي${\displaystyle \varepsilon >0}$مع مرور الوقت${\displaystyle O(n^{2})+2^{O(1/\varepsilon ^{2})}}$[ ^{15 ]​}

يمكن استخدام لعبة تبديل بيرلكامب في نظرية الترميز كمثال توضيحي لنصف قطر التغطية لرمز خطي ثنائي معين . رمز خطي ثنائي بطول${\displaystyle n}$والأبعاد${\displaystyle d}$يُعرَّف بأنه${\displaystyle d}$الفضاء الخطي ذو الأبعاد n من${\displaystyle n}$فضاء متجهي ذو أبعاد${\displaystyle \mathbb {F} _{2}^{n}}$على الحقل المنتهي ذي العنصرين ،${\displaystyle \mathbb {F} _{2}}$تُسمى عناصر الفضاء الجزئي بالكلمات المشفرة، ونصف قطر التغطية هو أصغر عدد${\displaystyle r}$بحيث تكون كل نقطة من${\displaystyle \mathbb {F} _{2}^{n}}$يقع ضمن مسافة هام${\displaystyle r}$كلمة سرية.

يترك ${\displaystyle n=ab}$و ${\displaystyle d=a+b-1}$بالنسبة لقيم هذه المعلمات، فإن الفضاء المتجهي${\displaystyle \mathbb {F} _{2}^{n}}$يصف جميع الأنماط الممكنة للمصابيح المضاءة على${\displaystyle a\times b}$مجموعة من المصابيح الكهربائية، مع عملية جمع متجهات تجمع بين نمطين بإضاءة المصابيح التي تظهر في أحد النمطين فقط ( عملية الفرق المتناظر على مجموعات المصابيح المضاءة). يمكن تعريف فضاء فرعي خطي يتكون من جميع الأنماط التي يمكن للاعب الثاني إطفاءها تمامًا، أو ما يعادلها من جميع الأنماط التي يمكن للاعب الثاني إنشاؤها بدءًا من لوحة مطفأة تمامًا. على الرغم من أن اللاعب الثاني لديه${\displaystyle 2^{a+b}}$خيارات لكيفية ضبط المجموعة الثانية من المفاتيح، هذه المساحة الفرعية تحتوي على${\displaystyle 2^{a+b-1}}$عناصر، مما يمنحها بُعدًا${\displaystyle a+b-1}$لأن قلب جميع مفاتيح اللاعب الثاني ليس له أي تأثير على نمط المصابيح المضاءة.

ثم${\displaystyle R_{a,b}}$يمثل نصف قطر تغطية هذا الرمز. مجموعة المصابيح المضاءة التي يختارها اللاعب الأول، بأفضل أداء، تعطي نقطة من${\displaystyle \mathbb {F} _{2}^{n}}$هذا هو أبعد ما يمكن عن الفضاء الخطي الفرعي. مجموعة المصابيح التي يغير اللاعب الثاني حالتها، مع أفضل أداء، تعطي أقرب نقطة في الفضاء الخطي الفرعي. مجموعة المصابيح التي تبقى مضاءة بعد هذه الاختيارات هي تلك التي يحدد عددها مسافة هامينغ بين هاتين النقطتين. ^{[ 1 ]}

• لعبة Lights Out ، وهي لغز مختلف يتضمن إطفاء المصابيح الكهربائية باستخدام مفاتيح تتحكم في عدة مصابيح.
• عرض توضيحي للعبة 10x10 بصيغة HTML