لعبة التمركز

تُعدّ لعبة المواقع ^{[ 1 ]}^{[ 2 ]} في نظرية الألعاب نوعًا من الألعاب التوافقية للاعبين. ويتم وصفها كما يلي:

$X$ – مجموعة محدودة من العناصر. غالبًا $X$ يُطلق عليها اسم اللوحة ، وتُسمى عناصرها بالمواقع .
${\mathcal {F}}$ – مجموعة من المجموعات الفرعية من $X$ تُسمى هذه المجموعات الفرعية عادةً بالمجموعات الفائزة .
معيار للفوز باللعبة.

خلال اللعبة، يتناوب اللاعبون على شغل المواقع التي لم يتم شغلها سابقًا، حتى يفوز أحدهم. إذا تم شغل جميع المواقع في $X$ إذا تم اتخاذ قرار بعدم فوز أي لاعب، تُعتبر المباراة تعادلاً.

المثال الكلاسيكي للعبة تعتمد على الموقع هو لعبة إكس أو . فيها، $X$ تحتوي على مربعات لوحة اللعبة التسعة، ${\mathcal {F}}$ تتضمن اللعبة ثمانية خطوط تحدد الفوز (ثلاثة أفقية، وثلاثة رأسية، واثنان قطريان)، ومعيار الفوز هو: اللاعب الذي يمتلك أولاً مجموعة فائزة كاملة يفوز. ومن الأمثلة الأخرى على الألعاب الموضعية لعبة هيكس ولعبة شانون للتبديل .

في كل لعبة استراتيجية، توجد ثلاثة خيارات فقط: إما أن يمتلك اللاعب الأول استراتيجية رابحة ، أو أن يمتلك اللاعب الثاني استراتيجية رابحة، أو أن يمتلك كلا اللاعبين استراتيجيات تؤدي إلى التعادل. ^{[ 2 ]}^{: 7} السؤال الرئيسي الذي يهم في دراسة هذه الألعاب هو أي من هذه الخيارات الثلاثة ينطبق على أي لعبة معينة.

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

المصطلحات البديلة

غالباً ما تُعتبر مدخلات لعبة تحديد المواقع بمثابة رسم بياني فائق . في هذه الحالة:

عناصر $X$ وتسمى الرؤوس (أو النقاط )، ويرمز لها بالرمز V ؛
عناصر ${\mathcal {F}}$ وتسمى هذه الحواف ( أو الحواف الفائقة )، ويرمز لها بالحرف E أو H.

المتغيرات

توجد العديد من أنواع الألعاب القائمة على المواقع، وتختلف في قواعدها ومعايير الفوز فيها.

معايير فوز مختلفة

لعبة قوية تعتمد على التمركز (وتسمى أيضاً لعبة صانع الألعاب): The first player to claim all of the elements of a winning set wins. If the game ends with all elements of the board claimed, but no player has claimed all elements of a winning set, it is a draw. An example is classic tic-tac-toe.
Maker-Breaker game: The two players are called Maker and Breaker. Maker wins by claiming all elements of a winning set. If the game ends with all elements of the board claimed, and Maker has not yet won, then Breaker wins. Draws are not possible. An example is the Shannon switching game.
Avoider-Enforcer game: The players are called Avoider and Enforcer. Enforcer wins if Avoider ever claims all of the elements of a winning set. If the game ends with all elements of the board claimed, and Avoider has not claimed a winning set, then Avoider wins. As in maker-breaker games, a draw is not possible. An example is Sim.
Discrepancy game: The players are called Balancer and Unbalancer. Balancer wins if he ensures that in all winning sets, each player has roughly half of the vertices. Otherwise Unbalancer wins.
Scoring game: Comparing at the end the winning sets obtained by the players, whoever has the winning set with the highest score wins, where the score of each winning set is given in the instance. An example is the Largest Connected Subgraph Game, where the positions are the vertices of a graph, the winning sets are connected subgraphs and the winner is the one who obtains the largest connected subgraph.

Different game rules

Waiter-Client game (also called Picker-Chooser game): The players are called Waiter and Client. In each turn, Waiter picks two positions and shows them to Client, who can choose one of them.
Biased positional game: Each positional game has a biased variant, in which the first player can take p elements at a time and the second player can take q elements at a time (in the unbiased variant, p=q=1).

Specific games

The following table lists some specific positional games that were widely studied in the literature.


Name	Positions	Winning sets
Multi-dimensional tic-tac-toe	All squares in a multi-dimensional box	All straight lines
Shannon switching game	All edges of a graph	All paths from s to t
Sim	All edges between 6 vertices.	All triangles [losing sets].
Clique game (aka Ramsey game)	All edges of a complete graph of size n	All cliques of size k
Connectivity game	All edges of a complete graph	All spanning trees
Hamiltonicity game	All edges of a complete graph	All Hamiltonian paths
Non-planarity game	All edges of a complete graph	All non-planar sub-graphs
Arithmetic progression game	الأعداد {1، ...، ن}	جميع المتتابعات الحسابية ذات الحجم k

انظر أيضاً

اللعبة الطوبولوجية ، وهي تعميم للعبة الموضعية إلى مجموعات لانهائية
لعبة باناش-مازور ، وهي لعبة تُلعب على فضاء طوبولوجي عن طريق الاختيار بين مجموعات فرعية معينة، مع شروط فوز تشبه شروط لعبة صانع-محطم.

مراجع

↑ بيك، جوزيف (2008). الألعاب التوافقية: نظرية لعبة إكس أو . كامبريدج: مطبعة جامعة كامبريدج. ISBN 978-0-521-46100-9.
1 2 حيفتس، دان؛ كريفيليفيتش, مايكل ; ستوياكوفيتش، ميلوش؛ زابو، تيبور (2014). الألعاب الموضعية . ندوات أوبرولفاخ. المجلد. 44. بازل: Birkhäuser Verlag GmbH. رقم ISBN 978-3-0348-0824-8.

[beck08-1] بيك، جوزيف (2008). الألعاب التوافقية: نظرية لعبة إكس أو . كامبريدج: مطبعة جامعة كامبريدج. ISBN 978-0-521-46100-9.

[pg14-2] 1 2 حيفتس، دان؛ كريفيليفيتش, مايكل ; ستوياكوفيتش، ميلوش؛ زابو، تيبور (2014). الألعاب الموضعية . ندوات أوبرولفاخ. المجلد. 44. بازل: Birkhäuser Verlag GmbH. رقم ISBN 978-3-0348-0824-8.

[ 1 ]

[ 2 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗