Hackenbush

Una configuració inicial per al joc de Hackenbush

Hackenbush és un joc per a dos jugadors inventat pel matemàtic John Horton Conway. Es pot jugar en qualsevol configuració de segments de llínea de colors conectats entre sí pels seus punts finals i a una llínea de "terra".

Jugabilitat

El joc comença en els jugadors dibuixant una llínea de "sol" (convencionalment, pero no necessàriament, una llínea horisontal en la part inferior del paper o una atra àrea de joc) i varis segments de llínea de modo que cada segment de llínea estiga conectat al sol, ya siga directament en un punt final, o indirectament, a través d'una cadena d'atres segments conectats per punts finals. Qualsevol número de segments pot trobar-se en un punt i, per lo tant, pot haver múltiples camins a terra.

En la seua tanda, un jugador "curta" (borra) qualsevol segment de llínea de la seua elecció. Cada segment de llínea que ya no està conectat al sol per cap camí "cau" (és dir, es borra). Segons la convenció de joc normal de la teoria de jocs combinatoris, el primer jugador que no puga moure's pert.

Els taulers de Hackenbush poden constar d'un número finito de segments de llínea (en el cas d'un "tauler finito") o infinits (en el cas d'un "tauler infinit"). L'existència d'un número infinit de segments de llínea no viola el supòsit de la teoria de jocs de que el joc pot terminar-se en un periodo de temps finito, sempre que només hi haja un número finito de segments de llínea que "toquen" directament el sol. En un tauler infinit, segons el disseny del tauler, el joc pot continuar per a sempre, assumint que hi ha infinits punts tocant el sol.

Variants

Una chiqueta Hackenbush blava-roja, presentada en el llibre Winning Ways for your Mathematical Plays

En la versió folklòrica original de Hackenbush, qualsevol jugador pot tallar qualsevol vora: com a est és un joc imparcial, és relativament senzill donar un anàlisis complet usant el teorema de Sprague-Grundy. Per lo tant, les versions de Hackenbush d'interés en la teoria de jocs combinatoris són jocs partisanos més complexos, lo que significa que les opcions (moviments) disponibles per a un jugador no serien necessàriament les disponibles per a l'atre jugador si fora la seua tanda de moure's donada la mateixa posició.. Açò es conseguix de dos formes:

• Hackenbush original: tots els segments de llínea són del mateix color i qualsevol dels jugadors pot tallar-los. Açò significa que els pagaments són simètrics i que cada jugador té les mateixes operacions segons la posició a bordo (en este cas, l'estructura del dibuix).
• Hackenbush blau-roig : cada segment de llínea és de color roig o blau. Un jugador (generalment el primer jugador o l'esquerre) solament pot tallar segments de llínea blava, mentres que l'atre jugador (generalment el segon jugador o el dret) solament pot tallar segments de llínea roja.
• Hackenbush blau-roig-vert : cada segment de llínea és de color roig, blau o vert. Les regles són les mateixes que per a Hackenbush blava-roig, en l'estipulació adicional de que qualsevol jugador pot tallar segments de llínea verda.

Hackenbush Blau-Rojo és simplement un cas especial de Hackenbush blau-roig-vert, pero val la pena senyalar-ho per separat, ya que el seu anàlisis sol ser molt més simple. Açò es deu a que Hackenbush Blau-Rojo és un joc cridat fret, lo que significa, essencialment, que mai pot ser una ventaja tindre el primer moviment.

Anàlisis

Hackenbush s'ha utilisat a sovint com un joc d'eixemple per a demostrar les definicions i conceptes en la teoria de jocs combinatoris, començant en el seu us en els llibres On Numbers and Games i Winning Ways for your Mathematical Plays d'alguns dels fundadors del camp. En particular, Hackenbush blau-roig es pot utilisar per a construir números surreales com nimbers: els taulers finitos Blue-Ret Hackenbush poden construir números racionals diàdics, mentres que els valors d'infinits taulers Blue-Ret Hackenbush representen números reales, ordinals i molts valors més generals que no són cap. Hackenbush blau-roig-vert permet la construcció de jocs adicionals els valors dels quals no són número real, com a estrela i tots els demés nimbers.

Es pot realisar un anàlisis més detallat del joc utilisant la teoria de grafos considerant el tauler com una colecció de vèrtiços i arestes i examinant els camins a cada vèrtiç que es troba en el sol (que deu considerar-se com un vèrtiç distinguit; no fa mal identificar tots els punts del sol junts, en lloc de com una llínea en el gràfic).

En la versió imparcial de Hackenbush (la que no té colors especificats pel jugador), es pot pensar en usar montons nim dividint el joc en varis casos: vertical, convergent i divergent. Jugat exclusivament en piles verticals de segments de llínea, també coneguts com tallos de bambú, el joc es convertix directament en Nim i es pot analisar directament com a tal. Els segments divergents, o arbres, agreguen una arruga adicional al joc i requerixen l'us del principi de dos punts, indicant que quan les branques es junten en un vèrtiç, es poden reemplaçar les branques per un talle no ramificado de llongitut igual a la seua nim suma. Este principi canvia la representació del joc a la versió més bàsica dels tallos de bambú. L'últim conjunt possible de gràfics que es poden fer són els convergents, també coneguts com a gràfics de raïl arbitrària. En usar el principi de fusió, podem afirmar que tots els vèrtiços de qualsevol cicle es poden fusionar sense canviar el valor del gràfic. Per lo tant, qualsevol gràfic convergent també es pot interpretar com un simple gràfic de talle de bambú. Combinant els tres tipos de gràfics podem agregar complexitat al joc, sense canviar mai la suma nim del joc, lo que permet que el joc adopte les estratègies de Nim.