Tabulaj ludoj sen hazardo

La plej multaj konataj tabulaj ludoj sen hazardo ("sen ludkubo"), inkluzive de "tri venkas", havas tri komunajn ecojn: La ludantoj ludas ("movas") alterne, la ludo finiĝas ene de difinita tempo, kaj ne ekzistas sekretoj, do la aktuala stato de la ludo estas egale perfekte konata al ĉiuj. Nekonata estas nur la estonteco, t. e. la okazontaj decidoj de la ludantoj. Tiaj ludoj nomiĝas "ludoj kun kompleta informo".

Ludoj de tiu speco estas "solveblaj" per la algoritmo de Zermelo-Kuhn, nomata ankaŭ "retrospurado". Ĝi konsistas el jenaj paŝoj:

  1. Kompleta notado de ĉiuj eblaj partioj de la ludo. Ĉar la ludmaterialo estas finia kaj ankaŭ la ludodaŭro, tio estas farebla. La rezulto estas grafo en la formo de arbo, kiu eliras de la start-situacio kaj kies folioj estas la finitaj partioj.
  2. Por ĉiu partio konstato de la rezulto (gajninto, aŭ egaleco), la "valoro" de la partio.
  3. Por ĉiu interna nodo de la arbo (t. e. por ĉiu lud-situacio) difini valoron laŭ jena maniero: listigi ĉiujn valorojn de la sub-nodoj kaj elekti tiun valoron, kiu estas plej bona por la ludanto, kiu "movas" en la koncerna situacio. Por fari tion necesas komenci ĉe la folioj de la arbo, do la ludfinaj situacioj, kaj "retrospuri" la vojojn en la arbo; tial la nomo "retrospurado".
  4. La valoro de la arbo-radiko, do de la komenca situacio, estas la valoro de la ludo. Se ĉiuj ludantoj ludas plej bone, la ludo havos la kalkulitan rezulton.

Por la plej multaj ludoj tiu arbo estas konsiderinde granda. Eĉ por la naŭkampa ludo "tri gajnas" ĝi estas ne malgranda; la ludoj ja povas havi po naŭ movojn, kaj en ĉiu movo povas esti pluraj ebloj. Tial ni provu per malpli granda ludo, la kvar-kampa ludo "du gajnas", en kiu ni tamen por gajno de la unua ludanto ("x") postulas diagonalan vicon de du egalaj simboloj, kaj aliokaze gajnigas la duan ludanton ("o", defendanto), kiu evidente ne povas kiel unua vicigi du siajn simbolojn.

Oni facile vidas, ke kun ignoro de simetriaĵoj ekzistas nur du eblaj rezultoj, el kiuj unu venkigas la komencanton kaj la alia la defendanton:

Same facile videblas, ke la dua ludanto "o" povas ĉiam malhelpi venkon de "x", blokante en sia unua movo la kampon diagonale kontraŭan al la movkampo de la komencanto. La lud-arbo de la ludo estas, denove kun ignoro de simetriaĵoj, jena:

Ni redesegnu la arbon, aldonante en maldekstra kolumno la simbolon de la movanta ludanto kaj en ĉiu kampo dekstre la simbolon de la ludanto, kiu per sia ĝusta decido povas atingi la venkon.

x o
o o
x x o
o o x o
o o

Decido-arbo de la ludo "du gajnas". La unua kolumno montras la ludanton, kiu movas ("x" aŭ "o"). Apud ĉiu bildo de lud-situacio dekstre staras la simbolo de la ludanto, kiu per racia agado povas venki en la koncerna situacio.

El aroj da simetriaj situacioj aperas nur po unu reprezentanto.

Videblas, ke dufoje en la ludo estas vera "decido": unue en la dua "duon-movo" (la unua movo de "o") "o" povas decidi pri la rezulto de la ludo: Metante sian simbolon diagonale al tiu de "x" li gajnas, alie malgajnas. Tio videblas el la fakto, ke la du sub-situacioj havas malsamajn rezultojn (do eblas gajno kaj malgajno), kaj ĉar la ludanto "o" havas en tiu situacio la decidon, li kompreneble decidas tiel, ke li gajnu. Tian konduton, kiu celas al la propra avantaĝo, la ludoteorio nomas "racia", kaj tian ludanton "racia aganto".

Se "o" en tiu situacio ne decidas la ludon, sed (malracie) metas sian cirklon apud la krucon, tiam "x" en la tria duonmovo decidas pri la rezulto de la ludo. Denove tiu situacio havas du sub-situaciojn kun malsamaj rezultoj.

Se ni ne eliminus la simetriajn situaciojn kaj movojn, ni havus pli da decidoj, sed ili ne influus la rezulton de la ludo.

Ŝako

Ankaŭ ŝako estas ludo kun alternaj movoj kaj kompleta informo kaj finia ludodaŭro (kiam dum 50 movoj ne okazas forigo de peco aŭ movo de peono, la ludo finiĝas sendecide). Do ankaŭ ĝi estas solvebla per retro-spurado laŭ Zermelo-Kuhn, kaj ekzistas optimuma strategio. Tiu strategio kondukas aŭ al egaleca rezulto aŭ al la venko de difinita ludanto. Ĉar ŝako estas sufiĉe kompleksa, oni ĝis nun ne sukcesis kalkuli tian optimuman strategion, do la ludo restas provizore interesa. Sed el ludoteoria vidpunkto la ludoj kun kompleta informo estas ne tre interesaj, ĉar la solvado estas sufiĉe klara.

antaŭa leciono antaŭa leciono komenco komenco sekva leciono sekva leciono