Joc poset

En teoria de jocs combinatoris, els jocs poset són jocs matemàtics d'estratègia, que generalisen molts jocs coneguts com Nim i Chomp. En tals jocs, dos jugadors comencen en un poset (un conjunt parcialment ordenat) i es turnan per a elegir un punt en el poset, eliminant-ho i tots els punts que són majors. El jugador que es queda sense un punt per a elegir, pert.

Joc

Donat un conjunt parcialment ordenat (P , <), siga

$P_x=P-\{a\mid a\ge x\}$

denotar el poset format per mig de l'eliminació de x de P.

Un joc poset en P, jugat entre dos jugadors convencionalment cridats Alice i Bob, és el següent:

• Alice elegix un punt x ∈ P; reemplaçant aixina P en P_x, i després passa la tanda a Bob, qui juga en P_x, i passa la tanda a Alice.
• Un jugador pert si és la seua tanda i no hi ha punts per a elegir.

Eixemples

Si P és un conjunt finito totalment ordenat, llavors el joc en P és exactament el mateix que el joc en un joc de Nim en un montó de tamany | P |. Perque, en abdós jocs, és possible elegir un moviment que conduïxca a un joc del mateix tipo el tamany del qual siga qualsevol número menor que | P |. De la mateixa manera, un joc poset en una unió disjunta d'órdens totals és equivalent a un joc de Nim en múltiples montons en tamanys iguals a les cadenes del poset.

Un cas especial d'Hackenbush, en el que totes les vores són verdes (pot ser tallat per qualsevol dels jugadors) i cada configuració pren la forma d'un bosc, pot expressar-se de manera similar, com un joc poset en un poset en el que, per a cada element x, hi ha com a màxim un element i per al que x cobrix i. Si x cobrix i, llavors i és el pare de x en el bosc en el que es juga el joc.

Chomp pot expressar-se de manera similar, com un joc poset sobre el producte del total de demanats dels que s'ha eliminat l'infimum.