Se pare că problema veche, dar nu am auzit încă despre asta. Împrumutat în LJ.
Se dă: Kashchei Nemuritorul care a furat prințesa de la Ivan Prințul. Și, de fapt, Ivan Tsarevich, care vrea să-și întoarcă mireasa.
Kashchei poate ucide. Există 10 puțuri cu otrăvire, forța otravei de la fântână până la fântână crește treptat. Otrava mai puternică este un antidot pentru cei mai slabi (dacă bei mai întâi de la 2 puțuri, iar apoi de la 3 - nu va fi nici o otrăvire). Dacă amestecați cele două otrăvuri, amestecul va dobândi proprietățile celor mai puternice.
Bătălia însăși: rivalii vin la stadion cu o ceașcă în mână. Dați paharul adversarului care bea conținutul. Dar ticălosul Kashchei a construit o cetate în jurul ultimelor 10 puțuri, ceea ce este inaccesibil lui Ivan. Astfel, Kashchei are acces la cea mai puternică otravă, dar Ivan nu are.
Scopul: să învingem Kashchei și să supraviețuim.
Poate că te gândești, dar poți să te uiți imediat la mine.
Când am citit prima dată problema, am crezut că este doar pentru teoria jocurilor și tabelele cu minimax. Dar mai întâi a trebuit să ghiciți toate acțiunile pe care le pot face jucătorii. Am împărțit aceste acțiuni în patru grupe:
- Bea ceva înainte de lupta (sau nu bea nimic înainte de lupta)
- Oferiți unui rival o ceașcă (în ceașcă poate fi o otravă din fântână sau un lichid inofensiv, dar la gustul căruia este imposibil să se determine otravă sau nu)
- Se amestecă conținutul ceștii adversarului cu ceva (sau nu se amestecă cu nimic), apoi bea
- Bea ceva după bătălie (sau nu bea nimic după luptă)
În consecință, Kashchei poate folosi pentru fiecare grup de acțiuni o otravă din 10 puțuri, iar Ivan numai din 9. Noi luăm toate acțiunile posibile și numărăm minimax în program.
În joc, Ivan are 10000 de oportunități, în Kashchei 14641
Compunem tabelul minimax ...
Soluția
Ivan
înainte de stadionul bea otravă DRINK_1,
dă adversarului o ceașcă cu otrava GIVE_9,
cel mai amestecă ceașcă adversarului cu otrava MIX_2,
și apoi bea o otravă NICIODATĂ
Deci, Ivan bea otravă din primul fântână, dă adversarului o ceașcă cu cea de-a 9-a otravă și amestecă conținutul cupei de la Kashchei cu otrava din al doilea fântână, bea și rămâne în viață. Să ne uităm la situația din partea lui Kashchei:
Kashchei
înainte de stadion să bea otravă NICIODATĂ,
dă adversarului o ceașcă cu otrava GIVE_9,
cel mai amestecă ceașcă adversarului cu otrava MIX_1,
și apoi bea o otravă DRINK_10
Dispunând de cel mai puternic antidot, Kashchey se teme doar de faptul că Ivan îi va aduce un lichid inofensiv, iar apoi va bea cea de-a zecea otravă, va pierde. Pentru a vă asigura că oferta lui Ivan conține otravă, el doar adaugă prima otravă la ceașcă și o bea cu antidotul său. Să fim atenți la faptul că calculatorul în locul lui Kashchei sa oferit să dea cea de-a 9-a ceașcă lui Ivan, și nu a 10-a. În acest lucru nu există nici o logică ascunsă, tocmai a jucat rolul procedurii de evaluare a acțiunilor calculatorului. A zecea otravă va juca, de asemenea.
Și acum vom compara cele două tactici unii cu alții. Iată ce a dat computerul:
Șansele lui Ivan să supraviețuiască cu acțiune rezonabilă Kashchei: a supraviețuit
Șansele lui Kashchei de a supraviețui sub acțiunea rezonabilă a lui Ivan: au supraviețuit
Deci, alegerea celor mai bune strategii, ambele personaje rămân în viață. Dar Ivan nu-și atinge scopul - prințesa. Apoi, poate că există o astfel de tactică atunci când unul dintre personaje moare? Word la computer:
Ivan va muri dacă Kashchei alege altă opțiune și el însuși va urma o strategie rezonabilă: nu
Kashchei va muri dacă Ivan va alege orice altă variantă de acțiune și va adera la o strategie rezonabilă: nu
Astfel, cu același succes, Kashchei și Ivan ar putea bea bere unul cu celălalt. Sau dă prințesă o otravă. Oricum, niciuna dintre ele, ca urmare a acestui joc, nu va obține rezultatul dorit.
Acum, să vedem dacă sa schimbat ceva dacă Kashchei și Ivan se aflau în aceleași condiții și ar avea acces egal la toate cele 10 puțuri. Strategia ambelor ar arăta astfel:
înainte de stadionul bea otravă DRINK_1,
dă adversarului o ceașcă cu otrava GIVE_10,
cel mai amestecă ceașcă adversarului cu otrava MIX_2,
și apoi bea o otravă NICIODATĂ
În această situație, ambii ar avea o strategie, aproape de strategia lui Ivan. Din nou, totul este redus la egalitate: ambii vor supraviețui. Astfel, eforturile lui Kashchei de a construi o cetate în jurul celui de-al 10-lea nivel nu au nici un sens. Cu atât mai bine pentru Ivan, pentru că acest lucru dovedește nerezonabilitatea lui Kashchei.
Ivan este un om cinstit și bun, așa că nu ar trebui să încalce regulile. Dar Kashchei este o persoană vicleană, așa că ne vom gândi la el.
În general, sarcina este redusă la egalitate, chiar dacă pentru Ivan rămân cele două cele mai slabe puțuri, iar restul opt vor fi înconjurate de cetăți Kashchei. Pentru a construi fortărețe în această cantitate, evident, nu a fost posibil pentru Kashchei din cauza costului proiectului. Dar dacă te gândești la asta, atunci puneți cetatea, să zicem, în a 8-a fântână, Kashchei oferă o victorie necalificată, dar cu o mică viclenie. El nu spune asta lui Ivan, dar în mod insidios toarnă ochelari din a 10-a fântână în fântâni de la primul la al șaptelea și în al nouălea. Din cauza proprietăților otrăvului, în nouă godeuri din zece va fi cea mai puternică otravă, iar cea mai slabă otravă - cea de-a opta va fi în Kashchei. Rulați programul:
În joc, Ivan are 10000 de oportunități, în Kashchei 14641
Compunem tabelul minimax ...
Soluția
Ivan
înainte de stadionul bea otravă DRINK_1,
dă adversarului o ceașcă cu otrava GIVE_10,
cel mai amestecă ceașcă adversarului cu otrava MIX_2,
și apoi bea o otravă NICIODATĂ
Kashchei
înainte de stadionul bea otravă DRINK_8,
da adversarului o ceasca cu otrava GIVE_1,
cel mai amestecă ceașcă adversarului cu otrava MIX_1,
și apoi bea o otravă NICIODATĂ
Șansele lui Ivan să supraviețuiască cu acțiune rezonabilă Kashchei: a murit
Șansele lui Kashchei de a supraviețui sub acțiunea rezonabilă a lui Ivan: au supraviețuit
Ivan va muri dacă Kashchei alege orice altă variantă de acțiune și el însuși va urma o strategie rezonabilă: da
Kashchei va muri dacă Ivan va alege orice altă variantă de acțiune și va adera la o strategie rezonabilă: nu
Rezumat. planificați în mod corect bugetele, insidiosul meu.
Codul sursă al programului care alcătuiește tabelul minimax.
Navigare după înregistrări
Articole similare
Trimiteți-le prietenilor: