Ku rupapuro rw'ibirimwo

kvizo

ca, kivuye

Ubutumwa 20

ururimi: Esperanto

Blua_Monto (Kwerekana umwidondoro) 15 Ntwarante 2021 01:03:21

Ludoviko kaj Johano ludas per 8 kartoj, sekvante suban regulon:

[regulo]
(i) Ili prenas karto(j)n alterne.
(ii) Ili rajtas preni unu, du aŭ tri karto(j)n po unu fojo, sed se unu el ili prenis tri kartojn, post tio, neniu el ili rajtas preni tri kartojn.
(iii) La persono, kiu akiris la okan karton, estas la venkanto de ĉi tiu ludo.
[/regulo]

Nun, jen estas demando: se Ludoviko estas la unua prenanto, kiom da karto(j)n Ludoviko unue devas preni, por ke Ludoviko venku malgraŭ kiel Johano prenas?

Blua_Monto (Kwerekana umwidondoro) 15 Ntwarante 2021 01:04:31

Mi penis forigi ambiguecon, sed se miaj frazoj estas neklaraj, bonvolu sciigi al mi kaj mi klarigos.

StefKo (Kwerekana umwidondoro) 15 Ntwarante 2021 10:17:37

Blua_Monto:L(...)
(ii) Ili rajtas preni unu, du aŭ tri karto(j)n po unu fojo, sed se unu el ili prenis tri kartojn, post tio, neniu el ili rajtas preni tri kartojn.
(...)
Pli ĝuste tiel?

(ii) Ili rajtas preni po unu, du aŭ tri karto(j)n unufoje (...)

Blua_Monto (Kwerekana umwidondoro) 15 Ntwarante 2021 22:06:21

Eble. La vorto po estas iom malfacila por mi…

Metsis (Kwerekana umwidondoro) 16 Ntwarante 2021 08:26:59

Tio estas konata ludo ene de la fako de la ludoteorio (ofte kun splitetoj aŭ ŝtonetoj anstataŭ kartoj). Temas pri tio, ke ambaŭ ludantoj havas kompletan informon pri la situacio aŭ la stato de la ludo kaj la nombro de alternativaj statoj en la ludo estas tre malalta. Do estas facile krei t.n. decidan arbon (decision tree) kun ĉiuj alternativoj. Ĉi tial eblas krei perfektan strategion, laŭ kiu unu el la ludantoj ĉiam venkas.

La konata solvo por tiaj ludoj estas, ke la dua ludanto ĉiam prenas komplementan amason de kartoj kaj tiel ĉiam venkas. Jen oni rajtas preni maksimume tri kartojn, do la komplementa amaso estas 4 minus kiom multajn kartojn la unua ludanto prenis. Tiel la dua ludanto ĉiam venkas. Sed via demando temas pri tio, kiel la unua ludanto povas venki. Alivorte vi serĉas la komplementon al tiu perfekta strategio.

La ŝlosilo estas la regulo "se unu el ili prenis tri kartojn, post tio, neniu el ili rajtas preni tri kartojn". Tio eblas al la unua ludanto fari tian movon, kiun la dua ludanto ne povas kontraŭi.

Lasu ni ekzameni la alternativojn.

Ludoviko komencas per preni unu karton

Laŭ la perfekta strategio Johano prenas 4-1=3 kartojn. Restas 4. Pro la aldona regulo Ludoviko povas preni nur unu aŭ du kartojn. Se li prenos unu, restos 3 kaj Johano ne povos preni ĉiujn. Do Ludoviko venkos. Se anstataŭe Ludoviko prenos du kartojn, restos 2 kaj Johano venkos.

Ludoviko komencas per preni du kartojn

Laŭ la perfekta strategio Johano prenas 4-2=2 kartojn. Restas 4, kaj vi povas vidi, ke iun ajn nombron Ludoviko nun prenos, Johano venkos.

Ludoviko komencas per preni tri kartojn

Laŭ la perfekta strategio Johano prenas 4-3=1 karton. Restas 4. Nun per preni nur unu karton Ludoviko restos 3 kartoj, kiujn Johano ne povos preni per unu movo laŭ la aldona, limiganta regulo. Do Ludoviko venkos.

Ĉu estas aliaj alternativoj?

Eble vi demandas vin, kio okazos, se Johano faros movon, kiu ne estas laŭ la perfekta strategio. Do la rolojn de la ludantoj inversigas, kaj Ludoviko povas fari movon laŭ la perfekta strategio kaj venkos.

Ekzemple

vico 1: Ludoviko prenas unu karton. Restas 7 kartoj.
vico 2: Johano prenas unu karton. Restas 6 kartoj.
vico 3: Ludoviko ludas laŭ la perfekta strategio kaj prenas 4-1=3 kartojn. Restas 3 kartoj, kaj vi povas vidi, ke iun ajn nombron Johano nun prenos, Ludoviko venkos.

Blua_Monto (Kwerekana umwidondoro) 16 Ntwarante 2021 08:49:31

Tio estas perfekta respondo, tre organizita kaj facile legebla.
Ne, mi ne intencis neperfektan movon. Mi forgesis mencii pri tio…

sergejm (Kwerekana umwidondoro) 16 Ntwarante 2021 14:10:32

Estas erareto en la respondo de Metsis.
Se Ludoviko prenas unu karton kaj Johano tri, tiam Ludoviko prenas unu.
Johano ne povos preni tri pro escepta regulo: li jam prenis tri pasintfoje kaj Ludoviko venkas.

Metsis (Kwerekana umwidondoro) 17 Ntwarante 2021 07:14:53

sergejm:Estas erareto en la respondo de Metsis.
Se Ludoviko prenas unu karton kaj Johano tri, tiam Ludoviko prenas unu.
Johano ne povos preni tri pro escepta regulo: li jam prenis tri pasintfoje kaj Ludoviko venkas.
Bona observo, dankon. Mi korektis mian respondon.

Metsis (Kwerekana umwidondoro) 17 Ntwarante 2021 08:54:11

Mi daŭris pripensi la ludon kaj kreis la decidan arbon, al kiu mi ŝanĝis la nomojn al Sofia resp. Adamo. Vi povas elŝuti la arbon en PDF-formo el mia Dropbox (la elŝutado tuj komencas, ne bezonas registriĝi).

La aldona regulo ŝanĝas la ludon rimarkinde:
 
  • la ludo ne plu estas komplete determinisma, alivorte ne plu estas vojo kun perfektaj movoj, kiuj garantios venkon al iu ajn ludanto
  • ambaŭ ludantoj ne plu havas egalan ŝancon venki, sed la komencanto havas 38 vojojn al venko kontraŭ 35 de la dua ludanto (se mi kalkulis ĝuste)
Mi lasas kiel ekzerco kalkuli la mini-maks -valorojn de la nodoj.

sergejm (Kwerekana umwidondoro) 17 Ntwarante 2021 17:07:26

Vi povas fari simplan memlernantan aŭtomaton por ĉi tiu ludo.
Certe, se vi scipovas programi, vi povas uzi komputilan programon anstataŭe.
Prenu saketoj kun nombroj 1, 2, 3, 3', 4, 4', 5, 5', 6, 7, 8 kaj enmetu en ili ĵetonojn kun numbroj 1, 2 kaj 3. En saketoj 2, 3', 4' kaj 5' metu nur 1 kaj 2, en 1 - nur 1.
Se restas N kartojn kaj vi rajtas preni tri kartojn, uzu saketon N. Se vi ne rajtas preni tri kartojn, uzu saketon N'. Elprenu el la saketo hazardan ĵetonon kaj prenu tiom da kartoj, kiom estas skribita sur la ĵetono. Metu la ĵetonon apud la saketo.
Se vi venkas, metu la ĵetonojn reen en la saketojn kaj aldonu po unu la saman.
Se vi malvenkas, forigu malvenkajn ĵetonojn.

Subira ku ntango