Pagoj

En multaj dupersonaj tabulaj ludoj estas nur du eblaj rezultoj: Gajnas unu aŭ la alia ludanto. (Foje eblas sendecida ludo, ekzemple en ŝako.) En tia ludo la celo de la ludanto estas simple "gajni".

Sed ekzistas ludoj, en kiuj la ludantoj ricevas aŭ perdas varian kvanton da mono, ĵetonoj aŭ io alia. La celo tiam estas maksimumigi la ricevitan kvanton resp. minimumigi la perdon. Multaj kartludoj estas de tiu speco. Ĉar la ludantoj alterne decidas kaj havas malsamajn, ofte eĉ kontraŭajn interesojn, ankaŭ la maksimumigenda funkcio alternas.

Ekzemplo: Ĉesi ĝustatempe

En ekzempla ludo du ludantoj decidas po kvindekfoje, ĉu antaŭtempe fini la ludon; post la 100-a (duon-)movo ĝi nepre finiĝas. Kiu finas la ludon en la n-a duonmovo, ricevas (n+1) monunuojn, lia kontraŭulo (n-1). Se post la 100-a duonmovo neniu finis la ludon, la unua ludanto ricevas 102, la dua 100.

Kiam oni ĉesu?

La algoritmo de Zermelo-Kuhn estas aplikebla ankaŭ tie ĉi. En ĉiu movo la movanta ludanto nun elektas ne simple venkan strategion, sed la strategion, kiu donas al li maksimuman garantiatan gajnon. Do oni same retrospuras la arbon de la movoj kaj donas al ĉiu nodo valoron, kiu estas la maksimumo de la gajnoj, kiujn la movanta ludanto povas atingi per sia decido, do la maksimumo de la valoroj de la subnodoj. Sed ĉar nun la kontraŭuloj eble havas ne rekte kontraŭajn interesojn, la nodoj havas du valorojn, unu por ĉiu ludanto. Ĉiu ludanto klopodas maksimumigi nur sian valoron, sen atenti tiun de la alia(j).

Ni desegnu parton de la arbo de la priskribita ludo; ĉar la arbo estas iomete "degeneriĝinta", ni prezentas ĝin unudimensie:

movo 1 2 3 ... 99 100 fino
gajnoj en okazo de ĉeso 2;0 1;3 4;2 ... 100;98 99;101 102;100

Nun ni aldonu al ĉiu movo la indikon, kiu decidas, kaj la valoron de la koncerna nodo, do la maksimumon de la valoroj de la subnodoj:

movo 1 2 3 ... 99 100 fino
decidas ludanto 1 2 1 ... 1 2 -
valoro 2;0 1;3 4;2 ... 100;98 99;101 -
gajnoj en okazo de ĉeso 2;0 1;3 4;2 ... 100;98 99;101 102;100

Videblas, ke en la lasta movo la 2a ludanto decidas, ĉu gajni "101" (per ĉeso) aŭ 100. Kompreneble li ĉesas kaj gajnas 101, lasante 99 al la unua ludanto. En la antaŭa movo la unua ludanto decidas inter tiuj 99 aŭ 100, kiujn li gajnas per ĉeso; do ankaŭ li ĉesas. Tiel oni alvenas al la konkludo, ke prefere la unua ludanto ĉesu en la unua movo, gajnante 2. Tute ne gravas, kiom da eblaj paŝoj la ludo havas.

Se (kontraŭe al la donita ekzemplo) unu ludanto perdas tion, kion la alia gajnas, la dua valoro estas simple la negativaĵo de la unua. Tiam oni simple alterne maksimumigas kaj minimumigas la saman funkcion, ĉar maksimumigo de la negativaĵo egalas al minimumigo.

Ni vidas, ke en tiaj ludoj kun alternaj movoj la analizo ne estas tre malfacila. Kiam la ludantoj decidas samtempe, la afero fariĝas pli interesa, ĉar tiam la scio de la ludantoj ne estas egala. Pri tiaj diferencoj de scio ni okupiĝos sekve.

Specimenaj demandoj

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