Puhdas ja sekalaiset strategiat. Pelit puhtaissa strategioissa

Lopullisista peleistä, jotka ovat käytännöllisiä, on suhteellisen harvinaisia \u200b\u200bpelejä, joissa on satulapiste; Tapaus on tyypillisempi. "Kun alempi ja huippu hinta on erilaisia \u200b\u200bpelejä. Tällaisten pelien matriisin analysointi päätimme, että jos jokainen pelaaja valmistui

yksi on ainoa strategia. Kohtuullisen vihollisen laskennassa tämä valinta on määritettävä minimaxin periaatteella. Holdingin maksimistrategiaan missä tahansa vihollisen käyttäytymisessä tietoisesti takaavat voitot, jotka ovat yhtä suuria kuin pelin alhaisempi hinta. Luonnollinen kysymys syntyy: onko olemassa keskimääräisten voittojen taata, suurempi, jos käytät yhtä yksittäistä "puhdasta" strategiaa ja vaihtoehtoisia satunnaisesti Useita strategioita?

Tällaiset yhdistelmät, jotka koostuvat useiden puhtaiden strategioiden soveltamisesta, jotka vuorottelevat satunnaislain mukaan tietyn taajuussuhteen kanssa pelien teoriassa kutsutaan sekalaisiksi strategioiksi.

On selvää, että jokainen nettostrategia on erityinen tapaus sekoitettu, jossa kaikki strategiat, paitsi yksi, käytetään nolla-taajuuksilla, ja tämä - taajuus 1.

On osoittautunut, että soveltamalla paitsi puhtaaksi vaan myös sekalaiset strategiat, on mahdollista, että jokainen lopullinen peli saada ratkaisu eli tällainen (yleisesti sekoitetut) strategiat, jotka soveltavat molempia pelaajia, voitot ovat yhtä suuret kuin peli ja jossa tahansa yksipuolinen poikkeama Optimaalinen strategia, voitot voidaan muuttaa vain sivulle, kannattamattomat poikkeavat.

Hyväksyntä on ns. Pelien teorian ns. Theoremin sisältö. Tämä teorema osoittautui ensin Neumananin taustalla vuonna 1928, tunnetuista teoremista on suhteellisen monimutkainen; Siksi annamme vain sanamuodon.

Jokaisella lopullisella pelillä on vähintään yksi ratkaisu (mahdollisesti sekalaisten strategioiden alalla).

Ratkaisun tuloksena saadut voitot kutsutaan pelin hintaan. Tärkein teoremista seuraa, että jokaisella lopullisella pelillä on hinta. On selvää, että peli V: n hinta on aina pelin alhaisemman hinnan ja pelin ylemmän hinnan välillä:

Itse asiassa on maksimaalinen taattu voitto, jota voimme tarjota itsellesi vain puhtaita strategioita. Koska sekalaiset strategiat sisältävät yksityisenä kotelona ja kaikki puhtaat, sitten sallitaan, paitsi puhtaaksi, sekoitetaan

strategiat, meillä on joka tapauksessa pahentaa valmiuksiamme; siten,

Samoin ottaen huomioon vihollisen kykyä, näytämme sen

siitä, mistä eriarvoisuus osoittautui (3.1).

Esittelemme erityisen merkityksen seka strategioille. Jos esimerkiksi seka strategiamme koostuu Al: n strategioiden käytöstä taajuuksilla, ja merkitsemme tämän strategian

Samoin sekaveden vihollisen strategia merkitään:

missä - taajuudet, joissa strategioita sekoitetaan

Oletamme, että olemme löytäneet pelin ratkaisun, joka koostuu kahdesta optimaalisesta strategiasta S, S. Yleensä kaikki tämän pelaajan käytettävissä olevat nettostrategiat sisältyvät optimaaliselle seka-strategiaan, mutta vain joitain. Soitamme strategioihin, jotka sisältyvät optimaaliseen sekaryhmän strategiaan, sen "hyödyllisiä" strategioita.

On osoittautunut, että pelin päätöksellä on toinen ihana omaisuus: Jos joku pelaajista noudattaa optimaalista strategiaa 5 (5). Tämä voitto pysyy ennallaan ja yhtä suuri kuin peli V, riippumatta siitä, mikä tekee toisen pelaajan, jos hän. Älä vain ylitä sen "hyödyllisiä" strategioita. Hän voi esimerkiksi käyttää mitä tahansa "hyödyllisiä" strategioita puhtaassa muodossaan ja voi myös sekoittaa ne millä tahansa mittasuhteessa.

Todistamme tämän lausunnon. Olkoon pelin päätös. Oletetaan, että optimaalinen sekaisinstrategia koostuu kolmesta sekteestä

"Hyödyllisiä" strategioita vastaavasti koostuu kolmesta "hyödyllisestä" strategiasta

ja väitetään, että jos noudatamme strategiaa S, vihollinen voi soveltaa strategioita millä tahansa mittasuhteissa, ja voitto pysyy ennallaan ja peli on edelleen sama

Vaikka lopetin Fysikaco-teknisen tiedekunnan, en lukenut pelien teoriaa yliopistossa. Mutta koska olen opiskelijavuodet Pelasin paljon ensinnäkin mieltymyksessä, ja sitten silta, olin kiinnostunut pelejä teoriasta, ja hallitsin pienen opetusohjelman. Ja äskettäin sivuston Reader Mikhail ratkaista tehtävän teorian tehtävän. Tajusin, että tehtävää ei annettu minulle, päätin virkistää tietoni pelien teoriasta. Tarjoan sinulle pienen kirjan - suosittu selvitys pelit teorian elementteihin ja joitain tapoja ratkaista matriisipelejä. Se ei lähes sisällä todisteita ja osoittaa esimerkkien teorian tärkeimmät määräykset. Kirja kirjoitti matemaatikkoa ja PHOPURIZER ELENA SERGEEVNA VENCEL. Useat sukupolvet Neuvostoliiton insinöörit tutkivat sen oppikirjan "todennäköisyysteoria". Elena Sergeevna kirjoitti myös useita kirjallisuus toimii Pseudonym I. Grekovin alla.

Elena Vencel. Pelin teorian elementtejä. - M.: FIZMATGIZ, 1961. - 68 s.

ladata lyhyt abstrakti muodossa tai

§ 1. Pelin teorian aihe. Peruskonseptit

Ratkaista useita käytännön tehtäviä (taloustieteen, sotilaskotelon jne.), On tarpeen analysoida tilannetta, jossa on kaksi (tai useampia) sotivia puolueita, jotka harjoittavat vastakkaisia \u200b\u200btavoitteita ja kunkin tapahtuman seurauksena Yksi osapuolista riippuu siitä, mitä toiminta toimia valitsee vastustajan. Soitamme tällaisiin tilanteisiin "konfliktitilanteisiin".

Lukuisat esimerkit konfliktitilanteista voidaan tuoda eri harjoittajilta. Vihamiesten aikana syntyvä tilanne kuuluu konfliktitilanteisiin: Jokainen taisteluala ottaa kaikki sen käytettävissä olevat toimenpiteet estääkseen vihollisen menestyksen saavuttamiseksi. Konflikti kuuluu ja tilanteita, jotka johtuvat aseen valinnasta, taisteluettelon menetelmiä ja yleensä sotilasoperaatioiden suunnittelussa: kukin tämän alan ratkaisuista olisi otettava huomioon vihollisen vähiten hyödyllisillä toimilla. Useat tilanteet taloustieteen alalla (erityisesti vapaan kilpailun läsnä ollessa) kuuluu konfliktitilanteisiin; Käsittelemien osapuolten roolissa kauppayritykset, teollisuusyritykset jne.

Tarve analysoida tällaisia \u200b\u200btilanteita aiheutti erityisen matemaattisen laitteen elämälle. Pelien teoria on oleellisesti mitään muuta kuin konfliktitilanteiden matemaattista teoriaa. Teorian tavoitteena on suositusten kehittäminen kunkin vastustajan järkevästä toiminnasta konfliktien tilanteessa. Kukin konfliktien tilanteen käytännöstä suoraan otettu on hyvin monimutkainen, ja sen analyysi haittaa lukuisten asenteiden läsnäolo. Tilanne mahdollisen matemaattisen analyysin tekemiseksi on välttämätöntä häiritä toissijaisia \u200b\u200btekijöitä ja rakentaa yksinkertaistettua, virallista tilanne mallia. Soitamme tällaisen mallin "pelin".

Todellisesta konfliktitilanteesta, pelille on ominaista se, että se toteutetaan melkoisten sääntöjen mukaisesti. Ihmiskunta on pitkään käyttänyt tällaisia \u200b\u200bfordalisoituja konfliktitilanteita, jotka ovat pelit sanan kirjaimellisessa merkityksessä. Esimerkkejä voivat palvella shakkia, ruudusta, korttipelejä jne. Kaikki nämä pelit ovat kilpailun luonne, joka virtaa tietyn pelaajan tunnettujen sääntöjen ja loppujen "voiton" mukaan.

Tällaisia \u200b\u200bmuodollisesti säänneltyjä, keinotekoisesti järjestettyjä pelejä ovat eniten sopiva materiaali Voit havainnollistaa ja hallita peliteorian peruskäsitteitä. Tällaisten pelien käytännöstä lainattu terminologia koskee ja analysoidaan muita konfliktitilanteita: osapuolet kutsutaan ehdollisesti "pelaajiksi", ja törmäystulos on "voittaa" yksi osapuolista.

Peli voi kohdata kaksi tai useampia vastustajia; Ensimmäisessä tapauksessa peliä kutsutaan "pariksi" toisessa "useassa". Useat pelin osallistujat voivat muodostaa koalitiot kurssillaan - pysyvä tai tilapäinen. Jos on kaksi pysyvää koalitiota, moninkertainen peli kiinnittää pariin. Suurin käytännöllinen merkitys on pariksi yhdistettyjä pelejä; Täällä rajoitamme itsemme vain tällaisten pelien huomioon ottamiseen.

Aloitamme pelien perusteorian esittäminen joidenkin peruskonseptien sanamuodossa. Tarkastelemme pariliitosta peliä, jossa mukana on kaksi pelaajaa A ja B vastakkaisia \u200b\u200betuja. "Game" ymmärrämme tapahtuman, joka koostuu useista osapuolten toimista A ja V. Jotta peli, joutuu matemaattiseen analyysiin, pelin säännöt on muotoiltava tarkasti. "Pelin sääntöjen" mukaan on olemassa olosuhteita, jotka säätelevät molempien osapuolten mahdollisia toimintavaihtoehtoja, toisen käyttäytymisen kunkin puolen määrä, "liikkeitä" (yksittäiset päätökset " Peliprosessissa) sekä pelin tulos tai lopputulos, johon tämä joukko liikkuu. Tämä tulos (voitolla tai tappiolla) ei aina ole kvantitatiivista ilmaisua, mutta yleensä voit asettaa tiettyä mittausasteikkoa, ilmaista se tietyllä numerolla. Esimerkiksi shakkipelissä voitto voi olla ehdottomasti ilmoitettu +1, Loss -1, Draw 0.

Peliä kutsutaan peliksi, jossa on nolla, jos yksi pelaaja voittaa, mitä muut menettävät, ts. Molempien osapuolten voitot ovat nolla. Nolla-summalla pelaajien edut ovat suoraan vastakkaisia. Täällä harkitsemme vain tällaisia \u200b\u200bpelejä.

Koska pelissä, jossa on nolla summa yhden pelaajan voiton, on yhtä suuri kuin toinen vastapäätä tuttua, Ilmeisesti, kun analysoi tällaista peliä, voit harkita vain yhden pelaajista. Olkoon esimerkiksi pelaaja A. Tulevaisuudessa olemme vierekkäisyyden ja tavanomaisen ja kutsumme "me" ja vastustajan puolella.

Samanaikaisesti sivua ("me") pidetään aina "voittajana" ja sivussa ("vastustaja") "menettää". Tämä muodollinen tila, ilmeisesti ei tarkoita mitään todellista etua ensimmäiselle pelaajalle; On helppo nähdä, että se korvataan vastakkaisella, jos voitto-merkki muuttuu päinvastoin.

Pelin kehittäminen ajoissa meitä toimitetaan useista peräkkäisistä vaiheista tai "liikkeistä". Pelien teorian siirtoa kutsutaan yksi vaihtoehtojen sääntöjen valinnasta. Liikkuvat jaetaan henkilökohtaiseen ja satunnaiseen. Henkilökohtainen siirto kutsutaan tietoiseksi valinnaksi, joka on yksi tämän tilanteen ja sen täytäntöönpanon käytöstä. Esimerkki henkilökohtaisesta liikkeestä - mikä tahansa liikkeestä shakkipelissä. Toisen liikkeen suorittaminen, pelaaja tekee tietoisen valinnan yhdestä vaihtoehdoista, jotka ovat mahdollisia tämän luvut. Jokaisen henkilökohtaisen edistyksen mahdollisia vaihtoehtoja säännellään pelin säännöillä ja riippuu molempien osapuolten aikaisempien siirtojen kokonaismäärästä.

Satunnaista edistymistä kutsutaan valikoima useista mahdollisuuksista, joita ei ole pelaajan päätöksellä, vaan millä tahansa satunnaisvalintamekanismilla (heittää kolikot, luut, Tasttovat ja karttojen toimitukset jne.). Esimerkiksi ensimmäinen kortti, jolla on jossakin mieluummin pelaajista, on satunnainen kurssi 32 vastaavuusvaihtoehdolla. Pelin matemaattisesti määritelty, pelin sääntöjen on oltava jokaiselle tahattomalle aivohalvaukselle, mikä osoittaa todennäköisyyksien jakelu mahdollisista tuloksista.

Jotkut pelit voivat koostua vain satunnaisista liikkeistä (niin sanottu puhdasta uhkapeliä) tai vain henkilökohtaisista liikkeistä (shakki, ruudut). Suurin osa korttipelit Kuuluu peleihin sekalainen tyyppi. Sisältää sekä satunnaisia \u200b\u200bettä henkilökohtaisia \u200b\u200bliikkeitä.

Pelit luokitellaan paitsi sellaisten liikkeiden luonteesta (henkilökohtainen, satunnainen) vaan myös luonteeltaan ja kunkin toiminnan käytettävissä olevan tiedon määrä toisen toiminnasta. Erityinen luokka on niin sanottu "pelejä täydelliset tiedot" Peliä, jossa on täydelliset tiedot, kutsutaan peliksi, jossa jokainen pelaaja jokainen henkilö tuntee kaikkien aikaisempien liikkeiden tulokset sekä henkilökohtaiset että satunnaiset. Esimerkkejä täydellisistä tietopeleistä voivat palvella shakkia, ruudusta ja kuuluisaa peliä "Cross ja Noliki".

Suurin osa käytännöllisistä pelistä ei kuulu täydellisten tietojen luokkiin, koska tuntemattomuus vihollisen toiminnasta on yleensä merkittävä konfliktitilanne.

Yksi pelin teorian peruskäsitteistä on käsite "strategia". Pelaajan strategiaa kutsutaan joukko sääntöjä, jotka määrittävät yksiselitteisesti valinnan jokaisen tämän pelaajan henkilökohtaisen edistyksen kanssa riippuen tilanteesta pelin prosessissa. Yleensä ratkaisu (valinta) jokaiselle henkilökohtaisella edistymiselle tekee soitin pelin aikana riippuen nykyisestä erityisestä tilanteesta. Teoriassa ei kuitenkaan muutu, jos kuvittelemme, että kaikki nämä päätökset hyväksytään etukäteen. Tätä varten pelaajan olisi tehtävä luettelo kaikista mahdollisista tilanteista pelin aikana ja tarjoavat jokaisesta niistä. Periaatteessa (jos ei käytännössä) on mahdollista mihin tahansa peliin. Jos tällainen ratkaisujärjestelmä hyväksytään, se tarkoittaa, että pelaaja on valinnut erityisen strategian.

Strategia, joka on valinnut strategian, voi nyt osallistua peliin henkilökohtaisesti, vaan korvata osallistumisensa sääntöjen luetteloon, joka soveltaa hänelle kiinnostuneita henkilöitä (tuomari). Strategiaa voidaan myös pyytää koneen konea tietyn ohjelman muodossa. Sitä tällä hetkellä pelataan EMM Shakissa. Että "strategian" käsite on järkevä, on tarpeen olla henkilökohtaisten liikkeiden pelissä; Pelissä, jotka koostuvat yhdestä satunnaisista liikkeistä, ei ole strategioita.

Riippuen mahdollisten strategioiden määrästä, peli on jaettu "lopulliseen" ja "loputon". Ultimate kutsutaan peliksi, jossa jokaisella pelaajalla on vain rajallinen määrä strategioita. Ultimate peli, jossa pelaaja A on m. strategiat ja pelaaja n. MXN-pelin strategiat.

Harkitse kahden pelaajan A ja B mxn-peliä ("me" ja "vastustaja"). Ilmoitamme strategiamme A 1, ja 2, ... ja M vihollisen strategian B 1, 2, ..., N. Anna kummankin puolen valitsi erityinen strategia; Meille se on minä, vihollisen B j. Jos peli koostuu vain henkilökohtaisista liikkeistä, strategioiden valinta i, b j Määrittää ainutlaatuisesti pelin tulokset - meidän voitoamme. Merkitse hänet ja IJ. Jos peli sisältää henkilökohtaisten, satunnaisten liikkeiden lisäksi, sitten voittoparia A I, B J on satunnainen arvo riippuen kaikkien satunnaisten liikkeiden tuloksista. Tässä tapauksessa odotettujen voittojen luonnollinen arvio on keskimääräinen arvo ( odotettu arvo). Me merkitsemme saman merkin kuin voitot itse (pelissä ilman satunnaisia \u200b\u200bliikkeitä) ja sen keskiarvo (pelin satunnaisilla liikkeillä).

Kerro meille Voittajan (tai keskimääräisen voiton) arvot kullekin strategioihin. Arvot voidaan kirjoittaa suorakulmaisena taulukkona (matriisi), joiden merkkijonot vastaavat strategioita (a) ja sarakkeet - vihollisen strategiat (B J). Tällaista taulukkoa kutsutaan maksumatriisi tai vain pelimatriisi. MXN-pelimatriisi esitetään kuviossa. yksi.

Kuva. 1. Matric MXN.

Lyhennettynä merkitsemme pelin matriisin ‖a ij ‖. Harkitse useita alkeita esimerkkejä peleistä.

Esimerkki 1. Kaksi pelaajaa A ja sisään, katsomatta toisiaan, laita pöydälle kolikon ylös tunnus tai laaja heidän harkintansa mukaan. Jos pelaajat ovat valinneet samat sivut (molemmissa kädet tai molemmat kiireet), niin pelaaja ja ottaa molemmat kolikot; Muussa tapauksessa heidän pelaaja ottaa heidät analysoimaan peliä ja tekevät siitä matriisin. Päätös. Peli koostuu vain kahdesta liikkeestä: Siirrä ja vihollisen liikkuminen sekä henkilökohtainen. Peli ei kuulu peleihin, joissa on täydelliset tiedot, koska hänen pelaajansa suorittaman kurssin aikana ei tiedä, mitä hän teki toisen. Koska jokaisella pelaajalla on vain yksi henkilökohtainen liike, pelaajan strategia on valinta samanaikaisesti.

Meillä on kaksi strategiaa: ja 1 - valitse kädet ja 2 - päättää päätöksen; Vastustajalla on samat kaksi strategiaa: 1 - vaakuna ja 2 - kiire. Näin peli on 2 × 2 peliä. Tarkastelemme voittokolikoita +1. Matrix-pelit:

Esimerkissä tämän pelin, kuten se ei ole alkeellinen, voit ymmärtää joitain olennaisia \u200b\u200bideoita pelien teoriasta. Oletetaan ensin, että tämä peli suoritetaan vain kerran. Sitten tietenkin on turhaa puhua pelaajien "strategioista", järkevämpi kuin toiset. Jokainen saman pohjan pelaajista voi olla ratkaisu. Kuitenkin, kun pelin toistuminen, sijainti muuttuu.

Itse asiassa oletamme, että me (pelaaja a) valitsi jonkinlaisen strategian (sanotaan ja 1) ja noudata sitä. Sitten ensimmäisten siirtojen tulosten mukaan vastustaja arvaa strategiamme ja vastata siihen vähiten suotuisaan meille, ts. Valitse ote. Olemme selvästi kannattamattomia, jotta voimme aina soveltaa yhtä strategiaa; Jotta olematta tappiota, meidän pitäisi joskus valita kädet, joskus - tilalla. Kuitenkin, jos vaihdamme kädet ja repes joitakin tiettyyn sekvenssiin (esimerkiksi yhden jälkeen), vihollinen voi myös arvata tämän ja vastata tähän pahimpaan strategiaan meille. On selvää, että turvallinen tapa takaa, että vihollinen ei tiedä strategiamme, siellä on tällainen valinnanvaraa joka kerta, kun emme tiedä sitä itse (tämä voidaan varmistaa esimerkiksi kolikon heitto). Näin ollen intuitiivisella päättelyssä lähestymme yhden pelioteorian olennaisista käsitteistä - "sekastrategian" käsitteeseen, toisin sanoen Tällainen silloin, kun "puhtaat" strategiat - tässä tapauksessa A 1 ja 2 - vaihtoehtoisesti tietyillä taajuuksilla. Tässä esimerkissä symmetria-näkökohdat ovat selvästi selvää, että strategiat A 1 ja A 2 olisi vaihdettava samalla taajuudella; Monimutkaisemmissa peleissä päätös voi olla kaukana triviaalisesta.

Esimerkki 2. Pelaajat a ja molemmissa kolmessa numerossa riippumatta toisistaan: 1, 2 tai 3. Jos kirjallisten numeroiden summa on edes, maksaa tämän määrän ruplissa; Jos se on outoa, päinvastoin ja maksaa tämän määrän. Sinun on analysoitava peli ja tehdä siitä matriisi.

Päätös. Peli koostuu kahdesta liikkeestä; Molemmat ovat henkilökohtaisia. Me (a) kolme strategiaa: A 1 - Kirjoita 1; Ja 2 - kirjoita 2; Ja 3 - Kirjoita 3. Vastustaja (B) on samat kolme strategiaa. Peli on 3 × 3 peli:

Ilmeisesti, kuten edellisessä tapauksessa vastustajan vihollinen, voit vastata pahimpiin meille. Itse asiassa, jos valitsemme esimerkiksi strategiaa 1, vihollinen vastaa aina strategiaan 2; strategialla A 2 - strategia 3; 3 strategiastrategiassa 2; Näin ollen tietyn strategian valinta johtaa väistämättä meitä tappioon (ei välttämätöntä, unohda, että vastustaja sijaitsee myös samassa tontissa). Tämän pelin ratkaiseminen (toisin sanoen molempien pelaajien korkeimpien strategioiden joukko) annetaan 5 §: ssä.

Esimerkki 3.Meillä on käytettävissänne kolme aseita: A 1, A 2, A 3; Vastustajalla on kolme ilma-alusta: B 1, 2, 3. Meidän tehtävämme on lyödä ilma-alus; Vastustajan tehtävänä on säilyttää se ei vaikuta. Assamenttien a 1, lentokoneiden B1, B2, 3 ° C: ssa vaikuttavat todennäköisyydet 0,9, 0,4 ja 0,2; käytössä 2 - todennäköisyydellä 0,3, 0,6 ja 0,8; Armmentissa ja 3 - todennäköisyydellä 0,5, 0,7 ja 0,2. Sen on laadittava tilanne pelien teorian kannalta.

Päätös. Tilannetta voidaan pitää 3 × 3: n pelina kahdella henkilökohtaisella liikkeellä ja yksi satunnainen. Henkilökohtainen siirto on aseiden tyyppi; Henkilökohtainen siirto vastustajan - lentokoneen valinta osallistua taisteluun. Satunnainen siirto - aseiden käyttö; Tämä liike voi lopettaa ilma-aluksen tappion tai erimielisyyden. Voitamme on yhtä suuri kuin ilma-alus hämmästynyt, ja se on yhtä suuri kuin nolla. Strategiamme ovat kolme asetta; Viholliset strategiat ovat kolme vaihtoehtoa ilma-alukselle. Jokaisen määritetyn strategian voiton keskimääräinen arvo on vain tämän ilma-aluksen vahingoittumisen todennäköisyys tämän aseen kanssa. Matrix-pelit:

Pelien teorian tarkoituksena on kehittää suosituksia kohtuullinen käyttäytyminen Pelaajat B. konfliktitilanteet. Jokaisen "optimaalisen strategian" määritelmä. Optimaalisen pelaajan strategiaa pelien teoriassa kutsutaan sellaiseksi strategiaksi, joka toistuvasti pelin toistuminen tarjoaa tämän pelaajan mahdollisimman korkeisiin keskimääräisiin voitoihin (tai mahdollisimman pienen keskimääräisen tappion). Kun valitset tämän strategian, perustelun perustana on oletus, että vihollinen on ainakin yhtä järkevä kuin me itse, ja tekee kaiken, jotta estämme meitä saavuttamasta tavoitteitaan.

Pelien teoriassa kaikki suositukset syntyvät näiden periaatteiden perusteella; Siksi se ei ota huomioon riskialuetta, jotka ovat väistämättä läsnä kussakin todellisessa strategiassa sekä mahdolliset virheelliset virheet ja kunkin pelaajan virheet. Pelin teoria kuten kaikki matemaattinen malli Monimutkainen ilmiö on rajoituksia. Tärkein niistä on se, että voitot vähenevät keinotekoisesti yhteen yksittäinen numero. Useimmissa käytännöllisissä konfliktitilanteissa kohtuullisen strategian kehittämisessä on tarpeen ottaa huomioon yksi, mutta useat numeeriset parametrit - kriteerit tapahtuman onnistumiselle. Strategia, joka on optimaalinen kriteeri, ei välttämättä ole optimaalinen muille. Kuitenkin tietoinen näistä rajoituksista ja siksi noudattamatta pelin menetelmien saamat sokeita suosituksia, on edelleen kohtuudella käyttää peliteorian matemaattista laitetta kehittääkseen, ellei täsmälleen "optimaalinen", milloin tahansa " Hyväksyttävä "strategia.

§ 2. Alempi ja huippupeli. "Minimax" -periaate

Harkitse MXN-peliä matriisin kanssa, kuten kuviossa 1. 1. Merkitään kirjain I Strategian numero; Kirjain J on vihollisen strategian numero. Tehdämme tehtävän: määrittää optimaalinen strategia. Analysoimme johdonmukaisesti jokainen strategiamme alkaen 1.

Valitsemalla strategia i, meidän on aina luotettava siihen, että vihollinen vastaa siihen J J: n strategioiden, joiden voitot ja IJ ovat vähäisiä. Määritämme tämän voiton arvon, ts. Vähintään numeroita ja IJ i.Linja. Merkitsee sen α i:

Tässä min-merkki (minimi j) on merkitty tämän parametrin arvojen vähimmäismäärällä kaikissa mahdollisissa J. Torjua numerot α i; Matriisin vieressä oikea sarakkeen muodossa:

Valitsemalla kaikki strategiat i, meidän on odotettava, että vihollisen kohtuullisten toimien seurauksena emme voita enemmän kuin α i. Luonnollisesti, joka toimii kaikkein varovaisimmista ja laskettavimmista kohtuullisimmasta vihollisesta (eli riskin välttämiseksi), meidän on asuttava kyseisestä strategiasta, jonka numero α i on suurin. Merkitsee tätä enimmäisarvoa α:

tai ottaen huomioon kaava (2.1),

A-arvoa kutsutaan pelin pohjahinnasta, muuten - suurimmat voitot tai yksinkertaisesti maksimi. Numero α sijaitsee matriisin tiettyyn riviin; Tämä pelaaja strategia A, joka vastaa tätä linjaa, kutsutaan maksimaaliseksi strategiaksi. Ilmeisesti, jos noudatamme mahdollisimman suurta strategiaa, minkä tahansa vihollisen käyttäytymisen myötä voitot taataan joka tapauksessa, ei vähemmän α. Siksi α: n arvo ja kutsutaan pelin "pohjahinnasta". Tämä on yksi taattu vähimmäismäärä, jonka voimme tarjota itselleen huolellisen ("jälleenvakuutuksen) strategian.

On selvää, että samankaltainen päättely voidaan toteuttaa viholliselle V. Koska vihollinen on kiinnostunut maksamaan voitot mahdollisimman vähäisinä, hänen on tarkasteltava jokaista strategiaa suurin voitto Tällä strategialla. Siksi matriisin alareunassa vahvistimme kullekin sarakkeelle maksimiarvot:

ja etsi vähintään β j:

Β: n arvoa kutsutaan pelin ylemmiksi, muuten - "Minimax". Vastaava minimix-strategia vihollista kutsutaan sen "Minimax-strategiaksi". Vihollisen takaa itselleen seuraavat: kaikki mitä olemme ottaneet häntä vastaan, hän joka tapauksessa menettää määrän, joka ei ole suurempi kuin β. Varovaisuutta koskeva periaate, sanelee pelaajia asiaankuuluvien strategioiden valinnassa (enimmäis- ja minimax), pelien teoriassa ja sen hakemuksissaan kutsutaan usein "Minimax-periaatteeksi". Toimijoiden varovaisimmat maksimaaliset ja minimix-strategiat osoittavat joskus yleinen termi "Minimax Strategiat".

Esimerkkeinä määritämme pelin alemman ja ylemmän hinnan esimerkkien 1, 2 ja 3 § 1.

Esimerkki 1.Esimerkissä 1 § 1 Dana-peli seuraavalla matriisilla:

Koska α i: n ja β j: n arvot ovat vakio ja vastaavasti -1 ja +1, pelin alempi ja huippu hinta ovat myös -1 ja +1: α \u003d -1, β \u003d + 1. Jokainen pelaaja strategia on sen maksimointi ja kaikki pelaajan strategia on sen Minimax-strategia. Trivilenin vetäytyminen: noudattaa mihin tahansa strategioihinsa, pelaaja ja voi taata, että se menettää enintään 1; Sama voi taata pelaajan V.

Esimerkki 2. Esimerkissä 2 § 1 Dana-peli matriisi:

Pelin alhaisempi hinta α \u003d -3; Top hintapeli β \u003d 4. Maksimistrategiamme on 1; Sovelluksen soveltaminen järjestelmällisesti, voimme lujasti olla voittamatta vähintään -3 (menettää enintään 3). Vihollisen minimax-strategia on mikä tahansa 1 ja 2: n strategiasta; Systemaattisesti, hän voi missään tapauksessa taata, että hän menettää enintään 4. Jos vetäytyä maksimistrategiastasi (esimerkiksi valitsemalla strategia A 2), vihollinen voi "rangaista" tämän soveltamalla a strategia 3: een ja minimoi voittoamme -5; Samoin vihollisen sortuminen minimax-strategiasta voi lisätä tappiotaan 6: een.

Esimerkki 3.Esimerkissä 3 § 1 Dana-peli matriisi:

Pelin alhaisempi hinta α \u003d 0,3; Yläarvopelit β \u003d 0,7. Meidän huolellisin (maksimi) strategia on 2; ASEMMENT A 2: n avulla takaavat, että voimme vaikuttaa ilma-alukseen keskimäärin vähintään 0,3 kaikista tapauksista. Vihollisen varovainen (minimix) strategia on 2; Lentokoneen soveltaminen vihollinen voi olla varma, että se vaikuttaa enintään 0,7 kaikkiin tapauksiin.

Viimeisin esimerkissä on kätevästi osoittaa yksi tärkeä omaisuus Minimax-strategiat ovat heidän epävakaus. Letemme soveltamaan varovaisimmista (maksimi) strategiaa 2, ja vihollinen on sen varovainen (minimix) strategia 2. Niin kauan kuin molemmat viholliset noudattavat näitä strategioita, keskimääräinen voitto on 0,6; Se on pidempi, mutta vähemmän kuin huippupintapeli. Nyt sanotaan, että vihollinen on tunnettu, että käytämme strategiaa 2; Hän vastaa välittömästi hänen strategiaan 1 ja antaa voiton 0,3. Samoin strategiassa B 1 Meillä on hyvä vastaus: strategia A 1, joka antaa meille voittaa 0,9 jne.

Näin ollen kanta, jossa molemmat pelaajat nauttivat minimax-strategioistaan, on epävakaa, ja sitä voi rikkoa tiedot vastustajan vastustajan strategiasta. On kuitenkin joitain pelejä, joille minimix strategiat ovat kestäviä. Nämä ovat ne pelit, joille alempi hinta on yhtä suuri kuin alkuun: α \u003d β. Jos pelin pohja on yhtä suuri, niin heidän yhteisen arvon kutsutaan puhtaana pelin (joskus vain pelin hinta), emme merkitä sen kirjaimella ν.

Harkitse esimerkkiä. Anna pelin 4 × 4 asettaa matriisi:

Etsi pelin alhaisempi hinta: α \u003d 0,6. Etsi pelin huippu hinta: β \u003d 0,6. Ne olivat samat, joten peli on puhdas hinta, joka on yhtä suuri kuin α \u003d β \u003d ν \u003d 0,6. Elementti 0,6, joka on korostettu maksamatriisissa, on samanaikaisesti minimaalinen rivissä ja suurin sarakkeessa. Geometryssä pinnalla oleva piste, jolla on samanlainen ominaisuus (samanaikainen vähimmäismäärä yhdellä koordinaatiolla ja enintään toisella) kutsutaan satulapisteeksi analogisesti, tämä termi koskee pelien teoriaa. Elementti matriisista, jolla on tätä ominaisuutta, kutsutaan matriisin satulapisteeksi ja pelistä, jonka he sanovat, että sillä on satulapiste.

Satulapiste vastaa minimax-strategioita (tässä esimerkissä ja 3 ja 2). Näitä strategioita kutsutaan optimaaliseksi, ja niiden kokonaisuuden on ratkaista peli. Pelin päätöksessä on seuraava upea omaisuus. Jos jokin pelaajista (esimerkiksi a) noudattaa optimaalista strategiaansa, ja toinen pelaaja (C) poiketa millään tavalla poikkeamaan optimaalisesta strategiastaan, sitten pelaajalle, joka teki poikkeaman, se ei voi koskaan olla edullista, Tällainen pelaaja hylkääminen voi parhaiten jättää voitot ennallaan, ja pahimmassa tapauksessa - lisätä sitä. Päinvastoin, jos hänen optimaalisessa strategiassaan, mutta poikkeaa itsestään, tämä ei voi olla hyödyllistä A.

Tämä lausunto on helppo tarkistaa pelin esimerkki, joka on käsiteltävä satulapisteen kanssa. Näemme, että pelin satulasta, minimix strategiat ovat erikoinen "stabiilius": Jos toinen puoli tarttuu minimax-strategiaan, niin toista voidaan vain poiketa toiselle. Huomaa, että tässä tapauksessa minkä tahansa pelaajan tiedot, joita vihollinen valitsi optimaalisen strategiansa, ei voi muuttaa pelaajan omaa käyttäytymistä: jos hän ei halua toimia omia etujaan, hänen on noudatettava optimaalista strategiaansa. Optimaaliset strategiat pelissä satulapisteessä on sellaisenaan, kuten "tasapainon sijainti": kaikki poikkeamat optimaalisesta strategiasta johtaa poikkeavan pelaajan epäedullisiin seurauksiin, jotka pakottavat sen alkuperäiseen asentoon .

Joten jokaiselle pelipeleille on ratkaisu, joka määrittelee parin optimaalisen strategian molempien osapuolten, jolle on ominaista seuraavat ominaisuudet.

1) Jos molemmat osapuolet noudattavat optimaalisia strategioita, keskimääräinen voitto on yhtä suuri kuin pelin nettohinta, joka on sen alempi ja ylempi hinta.

2) Jos jokin osapuolista on optimaalinen strategia ja toinen poikkeaa itsestään, poikkeava puoli voi vain menettää eikä missään tapauksessa voi lisätä sen vahvistusta.

Satulapisteen luokka on erittäin kiinnostunut sekä teoreettisesta että käytännöllisestä näkökulmasta. Pelien teoriassa on osoitettu, että erityisesti jokaisella täydellä tiedolla on satulapiste, ja siksi jokaisella tällaisella pelillä on ratkaisu, ts. Toisaalta optimaaliset strategiat, joiden keskimääräinen voitto on yhtä suuri kuin peli. Jos peli, jossa on täydelliset tiedot, koostuu vain henkilökohtaisista liikkeistä, niin kun käytät optimaalisen strategiansa kummallakin puolella, se on aina otettava yhteyttä melkoiseen tulokseen, nimittäin voitot, täsmälleen yhtä suuri hinta.

Esimerkkinä pelistä täydelliset tiedot täältä kuuluisa peli sijoittamalla kolikoita pyöreä pöytä. Kaksi pelaajaa vaihdetaan vuorotellen samat kolikot pyöreän pöydän pöydälle, valitsemalla joka kerta kolikon keskuksen mielivaltainen asema; Kolikoiden keskinäinen peittäminen ei ole sallittua. Voittaa yhden pelaajista, jotka laittavat viimeisen kolikon (kun ei ole paikkoja muille). On selvää, että tämän pelin lopputulos on aina ennalta määrätty, ja on täysin selvä strategia, joka tarjoaa luotettavan voiton pelaajilta, jotka laittavat kolikon ensin. Nimittäin hänen täytyy ensin laittaa kolikko pöydän keskustaan \u200b\u200bja sitten jokaiselle vihollisen liikkeelle vastaamaan symmetrisen liikkeen kanssa. Samaan aikaan toinen pelaaja voi käyttäytyä kaikesta, muuttamatta pelin ennalta määrättyä tulosta. Siksi tämä peli on järkevä vain pelaajille, jotka eivät tiedä optimaalista strategiaa. Tilanne on samanlainen kuin shakki ja muut pelit, joissa on täydelliset tiedot; Tällaisella pelillä on satulapiste ja ratkaisu, joka osoittaa jokaisen pelaajan optimaalisen strategiansa; Chess-pelin päättämistä ei löydy vain siksi, että mahdollisten liikkeiden yhdistelmät shakki on liian suuri, jotta voit rakentaa maksutapahtuman ja löytää satulapisteen.

§ 3. Puhdas ja sekalaiset strategiat. Pelin ratkaisu sekalaisissa strategioissa

Lopullisista peleistä, jotka ovat käytännöllisiä, on suhteellisen harvinaisia \u200b\u200bpelejä, joissa on satulapiste; Tyypillisempi on tapaus, kun pelin pohja ja huippu hinta ovat erilaisia. Tällaisten pelien matriisin analysointi päätimme, että jos jokaiselle toimijoille annettiin yhden strategian valinta, tämä valinta on määritettävä mininakesin periaatteella kussakin pelaajalla. Noudattamalla sen maksimistrategiaa, minkä tahansa vihollisen käyttäytymisestä tietoisesti taata voitot, jotka ovat yhtä suuria kuin pelin a. On luonnollista kysymystä: onko itseään mahdotonta taata keskimääräiset voitot, suurempi α, jos käytät yhtä "puhdasta" strategiaa, ja vaihdat satunnaisesti useita strategioita? Tällaiset yhdistelmät, jotka koostuvat useiden puhtaiden strategioiden soveltamisesta, jotka vuorottelevat satunnaislain mukaan tietyn taajuussuhteen kanssa pelien teoriassa kutsutaan sekalaisiksi strategioiksi.

On selvää, että jokainen nettostrategia on erityinen sekaisin, jossa kaikki strategiat, paitsi yksi, käytetään nolla-taajuuksilla, ja tämä - taajuudella 1. osoittautuu, että soveltamalla paitsi puhtaita vaan myös sekalaisia \u200b\u200bstrategioita voi saada jokaisen päätypelin päätöksen, ts. Pari tällaista (yleensä sekoitettu) strategiat, jotka soveltavat niitä molempien pelaajien kanssa, voitot ovat yhtä suuret kuin pelin hinta ja mikä tahansa yksipuolinen poikkeama optimaalisesta strategiasta voitot voidaan muuttaa vain Sivu, kannattamaton poikkeama.

Hyväksyntä on ns. Pelien teorian ns. Theoremin sisältö. Tämä teorema osoittautui ensin Neumananin taustalla vuonna 1928, tunnetuista teoremista on suhteellisen monimutkainen; Siksi annamme vain sanamuodon.

Jokaisella lopullisella pelillä on vähintään yksi ratkaisu (mahdollisesti sekalaisten strategioiden alalla).

Ratkaisun tuloksena saadut voitot kutsutaan pelin hintaan. Tärkein teoremista seuraa, että jokaisella lopullisella pelillä on hinta. Ilmeisesti pelin ν hinta on aina pelin α alemman hinnan ja pelin ylähinnan välillä β:

(3.1) α ≤ ν ≤ β

Itse asiassa α on suurin takuuvahvistus, jota voimme tarjota itsellesi, vain puhtaita strategioita. Koska sekalaiset strategiat sisältävät yksityisenä kotelona ja kaikki puhtaat, antavat siis puhtaita, myös sekalaisia \u200b\u200bstrategioita, meitä ei missään tapauksessa pahentanut kykyjä; Näin ollen ν ≥ α. Samoin ottaen huomioon vihollisen mahdollisuudet, näytämme, että ν ≤ β, josta eriarvoisuus olisi todiste (3.1).

Esittelemme erityisen merkityksen seka strategioille. Jos esimerkiksi seka strategiamme koostuu strategioiden A 1, 2 ja 3 levittämisestä taajuuksilla P 1, P2, P3, P1 + P 2 + P 3 \u003d 1, emme merkitä tämän strategian

Samoin sekaveden vihollisen strategia merkitään:

missä Q 1, Q 2, Q 3 - taajuudet, joissa strategiat B 1, 2, 3, sekoitetaan; Q 1 + Q 2 + Q 3 \u003d 1.

Oletetaan, että löysimme ratkaisun peliin, joka koostuu kahdesta optimaalisesta strategiasta s a *, s b *. Yleensä kaikki tämän pelaajan käytettävissä olevat puhtaat strategiat sisältyvät optimaaliseen sekaisin strategiaan ja vain osa. Soitamme strategioihin, jotka sisältyvät optimaaliseen sekaryhmän strategiaan, sen "hyödyllisiä" strategioita. On osoittautunut, että pelin päätöksellä on toinen ihana omaisuus: jos jokin pelaajista on optimaalinen sekoitettu SA * -strategia (SB *), voitto pysyy ennallaan ja yhtä suuri kuin peli ν, riippumatta siitä, mitä Muu pelaaja tekee, ellei vain se ylittää sen "hyödylliset" strategiat. Hän voi esimerkiksi käyttää mitä tahansa "hyödyllisiä" strategioita puhtaassa muodossaan ja voi myös sekoittaa ne millä tahansa mittasuhteessa.

§ 4. Pelien ratkaiseminen. Pelit 2.x.2 ja 2.x.n.

Jos MXN-pelillä ei ole satulapistettä, ratkaisu on yleensä melko vaikeaa tehtävä, erityisesti suurilla m ja n. Joskus tämä tehtävä on mahdollista yksinkertaistaa, jos ensin vähentää strategioiden määrää ylittämällä tarpeettoman. Tarpeettomat strategiat ovat a) kaksoiskappale ja b) ilmeisesti kannattamaton. Harkitse esimerkiksi peli matriisin kanssa:

On helppoa varmistaa, että strategia on 3 toistaa tarkasti ("kaksoiskappaleet") Strategia A 1, joten jokin näistä kahdesta strategiasta voidaan poistaa. Edelleen, verrataan linjaa A 1 ja A 2, huomaamme, että jokainen osa merkkijono A2 on pienempi (tai yhtä suuri) vastaavan elementin merkkijonon A1. Ilmeisesti meidän ei pitäisi koskaan käyttää A2-strategiaa, se on ilmeisesti epäedullinen. Piirustus 3 ja 2, tuo matriisi enemmän yksinkertaisuus. Seuraavaksi huomaamme, että viholliselle strategia on 3 tietoisesti kannattamatonta; Kun olet piirtänyt sen, tuomat matriisi lopulliseen muotoon:

Näin peli 4 × 4 ylittämällä kaksoiskappale ja tietoisesti kannattamattomia strategioita pelataan peliin 2 × 3.

Menettely päällekkäisyyksien ja tietoisesti epäsuotuisten strategioiden olisi aina edeltävä pelipäätökseen. Yksinkertaisimmat tapaukset loppupeleissä, jotka voivat aina ratkaista peruskoidetta 2 × 2 ja 2xn pelejä.

Harkitse peli 2 × 2 matriisin kanssa:

Kaksi tapausta voi tavata täällä: 1) Pelillä on satulapiste; 2) Pelillä ei ole satulapistettä. Ensimmäisessä tapauksessa ratkaisu on ilmeinen: tämä on strategioita, jotka leikkaavat satulapistettä. Huomaa, että pelin 2 × 2, satulapisteen läsnäolo vastaa aina ilmeisesti epäedullisten strategioiden olemassaoloa, joka on poistettava alustavassa analyysissä.

Anna satulapisteen ja siksi pelin alhaisempi hinta ei ole yhtä suuri kuin ylempi: α ≠ β. Sen on löydettävä optimaalinen sekoitettu soittimen strategia A:

Se on ominaista omaisuus, joka olisi vihollisen toimet (jos vain se ei ylitä sen "hyödyllisiä" strategioita), voitto on yhtä suuri kuin peli ν. Pelissä 2 × 2, molemmat vihollisen strategiat ovat "hyödyllisiä", - muuten peli olisi ratkaisu puhtaiden strategioiden (satulapiste) alalla. Se tarkoittaa, että jos noudatamme optimaalista strategiaamme (4.1), vihollinen voi käyttää mitä tahansa puhdasta strategiaa B 1, 2, muuttamatta keskimääräistä Win ν. Täältä meillä on kaksi yhtälöä:

josta ottaen huomioon, että P 1 + P 2 \u003d 1 saamme:

Game ν: n hinta löytyy korvaamalla P 1, P2: n arvot mille tahansa yhtälöstä (4.2).

Jos peli on tiedossa, sitten määrittää optimaalinen vihollisen strategia

esimerkiksi on tarpeeksi yhtälöä:

mistä, kun otetaan huomioon Q 1 + Q 2 \u003d 1, meillä on:

Esimerkki 1. Löydämme pelin liuoksen 2 × 2, jota pidetään esimerkissä 1 1 §, Matriisi:

Pelillä ei ole satulapistettä (α \u003d -1, β \u003d +1), ja siksi liuoksen pitäisi olla seka strategioiden alalla:

P 1, P 2, Q 1 ja Q 2 on tarpeen löytää. P 1 meillä on yhtälö

1 * P 1 + (-1) (1 - P 1) \u003d (-1) P 1 + 1 (1 - P 1)

mistä P 1 \u003d 1/2, P 2 \u003d 1/2.

Samoin löydämme: q 1 \u003d 1/2, q 2 \u003d 1/2, ν \u003d 0.

Näin ollen jokaisen pelaajan optimaalinen strategia on satunnaisesti vuorotellen sekä nettostrategiat käyttäen samalla tavalla kuin kukin niistä; Tällöin keskimääräiset voitot ovat nolla.

Tuloksena oleva tulos oli melko selvä etukäteen. Seuraavassa esimerkissä tarkastellaan enemmän monimutkainen peli, jonka ratkaisu ei ole niin ilmeinen. Esimerkki on esimerkki pelejä, jotka tunnetaan peleiksi, "petos" tai "harhaanjohtava". Käytännössä konfliktien tilanteita sovelletaan usein eri menetelmät Vihollisen käyttöönotto on harhaanjohtava (desinformaatio, väärien tarkoitusten yhdenmukaistaminen jne.). Esimerkki yksinkertaisuudesta huolimatta melko opettavasta.

Esimerkki 2. Peli koostuu seuraavaksi. On kaksi korttia: ässä ja kahdesti. Pelaaja ja satunnaisesti vie yhden niistä; Ei näe, mitä karttaa hän otti. Jos otin ässä, hän julistaa: "Minulla on ässä" ja vaatii vastustajan 1 rupla. Jos otin two, niin se voi joko 1) sanoa "Minulla on ässä" ja kysyntä vihollisen 1 ruplaa tai 2) myöntää, että hänellä on kaksi kertaa ja maksaa vihollisen 1 rupla.

Vihollinen, jos hän vapaaehtoisesti maksaa 1 ruplaa, voi vain ottaa sen. Jos hän tarvitsee 1 ruplaa, hän voi joko olla joko 1) uskoa pelaajalle, mutta hänellä on TUZ ja anna hänelle 1 ruplaa tai 2) vaatia tarkastuksia varmistaakseen, onko A. A. On totta, jos seurauksena tarkastukset osoittautuvat, että u todella ässä, on maksettava 2 ruplaa. Jos se osoittautuu, että hän pettää ja hänellä on kaksi kertaa pelaaja ja maksaa pelaajan 2 ruplaa. Sinun on analysoitava peli ja löytää kunkin pelaajan optimaalinen strategia.

Päätös. Pelillä on suhteellisen monimutkainen rakenne; Se koostuu yhdestä pakollisesta satunnaisesta siirtymisestä - valitsemalla pelaaja ja yksi kahdesta kortista - ja kaksi henkilökohtaista liikkeitä, joita ei kuitenkaan välttämättä toteuteta. Itse asiassa, jos otin ässä, hän ei tee mitään henkilökohtaista liikettä: hänelle annettiin vain yksi mahdollisuus - vaatia 1 ruplaa, jota hän tekee. Tässä tapauksessa henkilökohtainen siirto - uskoa tai uskoa (eli maksaa tai olla maksamaan 1 ruplaa,) - lähetetään pelaaja V. jos ensimmäisen satunnaisen liikkeen seurauksena hän sai kaksi kertaa Hänellä on henkilökohtainen liike: maksaa 1 rupla tai yrittää pettää vihollinen ja kysyntä 1 rupla (lyhyellä: "Älä pettää" tai "pettää"). Jos ja valitsee ensimmäisen, niin on vain 1 rupla; Jos valitsin toisen, niin pelaaja on varustettu henkilökohtaisella liikkeellä: uskoa sitä tai uskoa (eli maksaa 1 ruplaa tai vaatia todentamista).

Jokaisen pelaajan strategiat ovat säännöt, jotka osoittavat, miten pääset pelaajalle, kun hänelle annetaan henkilökohtainen liike. On selvää, että vain kaksi strategiaa: ja 1 - petollinen ja 2 - ei pettää. B - myös kaksi strategiaa: B 1 - uskoa 2 - ei usko. Rakenna pelimatriisi. Tätä varten laskemme keskimääräiset voitot kussakin strategioiden yhdistelmällä.

1. 1 in 1 (ja pettää, uskoo). Jos sain ässä (tämän ½ todennäköisyys, niin sitä ei anneta henkilökohtaiseen liikkeen; se vaatii 1 ruplaa, ja pelaaja uskoo hänet; voitot ja ruplat ovat yhtä suuria kuin 1. jos hän sai kaksi (todennäköisyys Liian ½), hän pettää strategiansa mukaan ja vaatii 1 ruplaa; se uskoo häneen ja maksaa; voitot ja myös yhtä kuin 1. Keskimääräiset voitot: 11 \u003d ½ * 1 + ½ * 1 \u003d 1.

2. 1: ssä 2 (ja pettää, ei usko). Jos sain ässä, hänellä ei ole henkilökohtaista liikkua; Se vaatii 1 ruplaa; Strategiansa mukaisesti se ei usko ja tarkastuksen seurauksena 2 ruplaa (voitot A on +2). Jos sain kaksi, se vaatii 1 ruplaa hänen strategiansa mukaan; Oman mukaan se ei usko; Tämän seurauksena se maksaa 2 ruplaa (voitot yhtä suuri kuin -2). Keskimääräinen voitto on yhtä suuri kuin 12 \u003d ½ * (+ 2) + ½ * (- 2) \u003d 0.

3. 2 in 1: ssä (eikä pettää, usko). Jos otin ässä, se vaatii 1 ruplaa; Strategiansa mukaan maksaa; Voittaminen on +1. Jos otin kaksi kertaa, hän maksaa 1 ruplaa hänen strategiansa mukaan; Se on vain hyväksyä (voittaa A on -1). Keskimääräiset voitot ovat: A 21 \u003d ½ * (+ 1) + ½ * (- 1) \u003d 0.

4. ja 2 2: ssä (eikä pettää, B ei usko). Jos otin ässä, se vaatii 1 ruplaa; Tarkastuksissa ja tarkastuksen seurauksena 2 ruplaa maksaa (voito on +2). Jos otin kaksi kertaa, se maksaa 1 rupla; Se on vain hyväksyä (voito on 1). Keskimääräinen voitto on yhtä suuri kuin 22 \u003d ½ * (+ 2) + ½ * (- 1) \u003d ½.

Rakenna pelimatriisi:

Matriisilla ei ole satulapistettä. Pelin hinta α \u003d 0, pelin huippu hinta β \u003d ½. Löydä ratkaisu peliin sekaisin strategioiden alalla. Kaavan (4.3) avulla saat:

nuo. Pelaajan on kolmasosa kaikista tapauksista käyttää ensimmäistä strategiaansa (pettää) ja kahdessa kolmasosassa - toinen (ei pettää). Samaan aikaan se voittaa keskimäärin pelin hinta ν \u003d 1/3.

V ν \u003d 1/3 osoittaa, että näissä olosuhteissa peli hyödyttää B. käyttämällä optimaalista strategiaa ja voi aina antaa positiivisen keskimääräisen vahvistuksen. Huomaa, että jos käytin huolellisinta (maksimaalista) strategiaani (tässä tapauksessa sekä strategiat A 1 että A 2 ovat maksimaalisia), sillä olisi keskimääräinen nousu nolla. Siten sekoitettu strategian käyttö ja kyky toteuttaa sen etu B: n, joka tapahtuu pelin datasääntöjen aikana.

Määritämme optimaalisen strategian V. Me: q 1 * 1 + q 2 * 0 \u003d 1/3, q 1 \u003d 1/3, q 2 \u003d 2/3. Peräkkäin

tE. Pelaajan on uskottava kolmannekseen kaikista tapauksista A ja maksaa se 1 rupla ilman tarkastamista ja kahdessa kolmasosassa - tarkista. Sitten hän on keskimäärin jokaiselle pelille menettää 1/3. Jos hän käytti minimax puhdasta strategiaa 2: een (ei uskoa), hän menettää jokaisen pelin keskimäärin 1/2.

Pelin ratkaisu 2 × 2 voidaan antaa yksinkertainen geometrinen tulkinta. Olkoon 2 × 2 matriisin kanssa

Ota Abscissan akselin osa 1 (kuva 4.1). Osion vasemmanpuoleinen pää (kohta abscissa x \u003d 0: n kanssa) kuvaa strategiaa A 1; Sivuston oikea pää (x \u003d 1) on strategia A 2. Leikkaa pisteiden A 1 ja 2 kaksi kohtisuorassa abscissan akseliin nähden: akseli I.-I. ja akseli II-II.. Akselilla I.-I. Me lykkäämme voitot, kun strategia A 1; akselilla II-II. - Tapoja strategialla A 2. Harkitse vihollisen strategiaa B 1; Se antaa kaksi pistettä akseleilla I.-I. ja II-II. Ordinesin vastaavasti ja 11 ja 21. Vietämme suoraan suoraan B 1 B 1 näiden pisteiden kautta. Ilmeisesti, jos me, vihollisen strategiassa B 1, käytämme seka strategiaa

sitten keskimääräiset voitot, jotka ovat tässä tapauksessa, 11 p1 + a 21 p2, kuvataan piste M: llä 1 b 1; Tämän pisteen abskissa on yhtä suuri kuin P2. Suora 1: ssä 1: ssä, joka kuvaa voitot strategialla 1, pyhitetään "strategiasta 1".

On selvää, että 2 voidaan rakentaa täsmälleen samalla tavalla (kuva 4.2).

Meidän on löydettävä optimaalinen strategia S A *, toisin sanoen, joista vähintään voitot (b): n käyttäytymisellä maksettaisiin. Tehdä tämä, me rakentamme voiton alemman rajan strategioissa 1, 2, toisin sanoen Rikki b 1 nb 2 merkitty kuviossa 2 4.2 Rasvan linja. Tämä alaraja ilmaisee vähimmäispelaaja voittaa A: n seka strategiat; Piste N, jossa tämä vähimmäisvoitot saavuttavat enimmäismäärän ja määrittää pelin ratkaisun ja hinnan. On helppoa varmistaa, että pisteen n koordinaatti on pelin ν, ja sen Abskissa on yhtä suuri kuin P2 - strategian soveltamisen tiheys A 2 optimaalisessa sekaryhmässä S a *.

Meidän tapauksessamme pelin ratkaisu määritettiin strategioiden risteyksessä. Se ei kuitenkaan aina ole niin; Kuviossa 1 4.3 Näyttää tapauksen, kun strategioiden risteyksestä huolimatta ratkaisu antaa puhtaita strategioita molemmille pelaajille (A 2 ja 2) ja pelin hinta ν \u003d A 22. Tällöin matriisilla on satulapiste ja strategia A 1 on ilmeisesti kannattamaton, koska Puhtaalla vihollisen strategialla se antaa pienemmän voittojen kuin ja 2.

Siinä tapauksessa, kun ilmeisesti epäsuotuisa strategia on vastustaja, geometrinen tulkinta on esitetty kuviossa 2 esitetyn ulkonäön. 4.4.

Tällöin voitot pienempi raja on samansuuntainen strategiassa 1, strategia 2 viholliselle on ilmeisesti epäedullinen.

Geometrinen tulkinta mahdollistaa pelin pohjan ja huippuluokan hinnan visuaalisesti (kuva 4.5).

Esimerkeissä 1 ja 2 käsitellyt geometriset tulkinnat rakentavat geometriset tulkinnat (kuva 4.6 ja 4.7).

Olemme varmistaneet, että kaikki 2 × 2-peli voidaan ratkaista perustekniikoilla. Kaikki 2xn-peli voidaan ratkaista täysin samalla tavoin. Jos meillä on vain kaksi strategiaa, ja vastustajalla on mielivaltainen numero.

Anna meillä kaksi strategiaa: A 1, 2 ja vastustaja - N-strategiat: 1, 2, ..., n. Matrix ‖a ij ‖ on asetettu; Se koostuu kahdesta rivistä ja n sarakkeesta. Samanlainen kuin kaksi strategiaa, tarjoamme geometrisen tulkkausongelman; N Enemy Strategiat näyttävät N: n suora (kuva 4.8). Rakentamme voitoiden alaraja (rikki B 1 MNB 2) ja löydämme pisteen n, jolla on suurin asuinpaikka. Tämä kohta antaa pelin pelin (strategia ) Ordinate kohta n on yhtä suuri kuin pelin ν, ja Abskissa on yhtä suuri kuin strategian P 2 taajuus A 2.

Tässä tapauksessa optimaalinen vihollisstrategia saadaan käyttämällä kahden "käyttökelpoisen" strategian seosta: 2 ja 4 risteyksessä N: ssä. Strategia 3 on ilmeisesti kannattamaton, ja strategia B 1 on optimaalinen strategia SA *. Jos se noudattaa optimaalista strategiaansa, voitot eivät muutu, riippumatta siitä, kuinka paljon "hyödyllisiä" strategioita joko muutetaan, se muuttuu, jos se menee strategioihin B 1 tai 3. Teorian teoriassa on osoitettu, että kaikilla lopullisella MXN-pelillä on ratkaisu, jossa toisen puolen "hyödyllisten" strategioiden määrä ei ylitä pienintä kahden numeron M ja N. Erityisesti tästä seuraa, että 2xm-pelillä on aina ratkaisu, jossa toiselta puolelta ei ole vielä kaksi "hyödyllistä" strategiaa.

Geometrisen tulkinnan avulla voit helposti ratkaista 2xm-peli. Suoraan piirustusten mukaan löydämme parin "hyödyllisistä" strategioista vihollisen B j ja k, leikkauspisteessä n (jos pisteessä n on yli kaksi strategiaa, ota kaksi niistä). Tiedämme, että jos pelaaja ja noudattaa optimaalista strategiaa, voitto ei riipu siitä, mikä osuus koskee "hyödyllisiä" strategioita,

Näistä yhtälöistä ja olosuhteista P 2 \u003d 1 - P 1 löydämme P1, P2 ja pelin hinta ν. Tietäen pelin hinta, voit välittömästi määrittää optimaalisen strategian Pelaaja V. Tätä varten on ratkaistu esimerkiksi yhtälö: qja 1 j + qka 1 k \u003d ν, missä QJ + qk \u003d 1. Jos meillä on M-strategioita, ja vihollinen on vain kaksi, ilmeisesti , tehtävä ratkaistaan \u200b\u200btäysin samalla tavalla. Riittää, että huomaat, että muuttamalla voittaneen merkkiä päinvastoin, voit kääntää soittimen ja "voittaa" "menettää". Voit ratkaista pelin ja muuttamatta viisautta merkki; Sitten tehtävä ratkaistaan \u200b\u200bsuoraan B: lle, mutta ei pienemmäksi, vaan voitot (kuva 4.9). Rajalla etsii pistettä n minimaalisella tavaroilla, mikä on peli ν.

Harkitse ja ratkaise useita esimerkkejä 2 × 2: sta ja 2xm-pelistä, jotka ovat yksinkertaistettuja pelien yksilöitä, jotka ovat käytännöllisiä.

Esimerkki 3.Puolue ja lähettää vihollisen kahdelle pommikoneelle I. ja II.; I. lentää edessä II. - Takaosa. Yksi pommikoneista - Ei tiedetä etukäteen, mitä - pommi on oltava pommi, toinen suorittaa säestystoiminnon. Vastustajan alueella Bomber hyökkää V. Bombardersin taistelija aseilla aseilla eri nopeus. Jos taistelija hyökkää takapuhallus II., sitten tuli vain tämä pommitus johtaa siihen; Jos hän hyökkää etupuhallus, niin molempien pommikoneiden aseet johtavat siihen. Fighter-leesion todennäköisyys ensimmäisessä tapauksessa on 0,3, toisessa 0,7.

Jos taistelija ei ammu alas pommittajien puolustavalla palolla, niin hän on silmiinpistävä tavoite, joka on valittu heille todennäköisyydellä 0,6. Bomberin tehtävä - välittää pommi tavoitteeseen; Taistelun tehtävänä on estää tämä, toisin sanoen Lataa kantokahva. Sen on valittava osapuolten optimaaliset strategiat:

a) Party A: Mikä on pommikone tehdä harjoittaja?

b) Party Q: Mitä pommikone hyökkää?

Päätös. Meillä on yksinkertainen tapa pelata 2 × 2; voittanut todennäköisyys Kertakäyttöiset tiedotusvälineet. Strategiamme: 1 - Carrier - Bomber I.; Ja 2 - Carrier - Bomber II.. Sivustostrategia: 1 - hyökkää pommikoneen I.; 2 opetti pommikone II.. Tehdään pelin matriisi, ts. Löydämme keskimääräisen vahvistuksen jokaisella strategioiden yhdistelmällä.

1. 1 in 1 (kantaja I.Hyökkäys I.). Lentoliikenteen harjoittaja ei hämmästynyt, jos pommikoneet kokoontuvat taistelijan tai eivät pääse vastuulle, mutta se ei osu tavoitteeseensa: A 11 \u003d 0,7 + 0,3 * 0,4 \u003d 0,82.

2. 2 in 1 (kantaja II.Hyökkäys I.). A 21 \u003d 1

3. 1 IN 2 (kantaja I.Hyökkäys II.). 12 \u003d 1

4. 2 IN 2 (kantaja II.Hyökkäys II.). A 22 \u003d 0,3 + 0,7 * 0,4 \u003d 0,58

Pelin matriisi on lomake:

Pelin alhaisempi hinta 0,82; Top Hinta 1. Matriisilla ei ole satulapistettä; Ratkaisu Etsimme sekalaisten strategioiden alalla. Meillä on:

p 1 * 0,82 + P 2 * 1 \u003d ν

p 1 * 1 + P 2 * 0,58 \u003d ν

p 1 \u003d 0,7; P 2 \u003d 0,3

Optimaalinen strategiamme Siellä on eli kuljettajana, sinun on valittava lisää I.kuin II.. Pelin hinta on yhtä suuri kuin ν \u003d 0,874. Tietäen ν, määritämme Q 1 ja Q 2 - strategioiden taajuudet 1 ja 2 optimaalisessa vihollisen strategiassa S B *. Meillä on: q 1 * 0,82 + q 2 * 1 \u003d 0,874 ja q 2 \u003d 1 - Q 1, mistä Q 1 \u003d 0,7; Q 2 \u003d 0,3, ts. Optimaalinen vihollisstrategia on .

Esimerkki 4.Puolue hyökkää esineeseen, puolue puolustaa häntä. Sivulta a - kaksi ilma-alusta; B-kolmen zenith-aseiden puolella. Jokainen ilma-alus on voimakas hellävaras; Jotta esine on hämmästynyt, riittää rikkomaan vähintään yhden ilma-aluksen. Lentokoneiden puolue ja voi valita minkä tahansa kolmesta suunnasta lähestyä kohdetta: I., II., III (Kuva 4.10). Vihollinen (puoli c) mahtuu mihin tahansa aseeseen mihin tahansa suuntaan; Tällöin kukin instrumentti ammuttiin vain tilan avaruudessa tämä suunta, ja ei ammu lähellä olevia ohjeita. Jokainen ase voi palata vain yhden ilma-aluksen; Ammuttu lentokone on hämmästynyt todennäköisyydellä 1. Osapuoli ja ei tiedä, missä aseet asetetaan; Osapuoli ei tiedä, missä lentokoneet tulevat. A: n osan tehtävä on osua esineeseen; Osapuolten tavoitteena - estää sen tappion. Etsi ratkaisu peliin.

Päätös. Peli on 2 × 3 peliä. Voittaminen on todennäköisyys esine vahinkoa. Mahdolliset strategiat: A 1 - Lähetä yksi ilma kahteen eri suuntiin. A 2 - Lähetä molemmat ilma-alukset yhteen suuntaan. Sivustostrategia: 1 - laittaa yksi yhdelle työkalulle kullekin suuntaan; 2 - laittaa kaksi asetta yhteen suuntaan ja yksi - toiseen; 3 - Laita kaikki kolme asetta yhteen suuntaan. Tee pelin matriisi.

1. ja 1 in 1: ssä (lentokone lentävät eri alueet; Aseet on järjestetty yksi). Ilmeisesti mikään taso ei hajota kohteeseen: A 11 \u003d 0.

2. 2 in 1 (lentokone lentää yhteen suuntaan, aseet sijoitetaan yksi kerrallaan). Ilmeisesti yhdellä ilma-aluksella siirretään objektille, jonka on kiinnitetty: A 21 \u003d 1.

3. ja 1-2 (lentokone lentävät yksi kerrallaan, vastustaja suojaa kaksi suuntaa ja jättää suojaamattoman kolmannen). Todennäköisyys, että ainakin yksi lentokone hajoaa esineeseen, on yhtä suuri kuin todennäköisyys, että yksi niistä valitsee suojaamattoman suunnan: 12 \u003d 2/3.

4. ja 2: ssä 2 (ilma-alukset lentävät yhteen suuntaan, vihollinen suojaa yhtä suuntaa kahdella työkalulla ja yksi - yksi, toisin sanoen suojelee yhtä suuntausta ja jättää suojaamattomat kaksi). Todennäköisyys siitä, että ainakin yksi taso hajoaa esineeseen, on yhtä suuri kuin ilma-aluksen parin todennäköisyys, joka on tosiasiallisesti suojaamaton suunta: A 22 \u003d 2/3.

5. ja 1-3 (ilma-alus lentävät yksi kerrallaan, vastustaja suojaa kolme aseita vain yhteen suuntaan): A 13 \u003d 1.

6. ja 2 3: ssa (ilma-alus lentävät molemmat yhdessä, vastustaja suojaa kolme aseita vain yhteen suuntaan). Jotta esine on hämmästynyt, ilma-alusten on valittava suojaamaton suunta: A 23 \u003d 2/3.

Matrix-pelit:

Matriisista on selvää, että 3: n strategia on ilmeisesti epäedullinen verrattuna B 2: een (tämä voitaisiin ratkaista etukäteen). Strategian ilmaiseminen 3 peli tulee alas peliin 2 × 2:

Matriisilla on satulapiste: pelin alhaisempi hinta 2/3 vastaa ylhäällä. Samanaikaisesti huomaamme, että meille (a) strategia A 1 on selvästi epäedullinen. Päätelmä: Molemmat osapuolet A ja B on aina käytettävä puhtaita strategioitaan A 2 ja B 2, ts. Meidän on lähetettävä ilma-alusta 2, valita satunnainen suunta, jolla höyry lähetetään; Vihollisen pitäisi asettaa aseet näin: kaksi - yhteen suuntaan, yksi - toisaalta, ja näiden alueiden valinta olisi myös toteutettava sattumalta (tässä, kuten näemme, jo "puhtaat strategiat" ovat elementti mahdollisuus). Näiden optimaalisten strategioiden soveltaminen saat aina pysyviksi keskimääräiset voitot 2/3 (eli objektin todennäköisyydellä 2/3). Huomaa, että löydetty ratkaisu ei ole ainoa; Ratkaisujen lisäksi B. puhtaat strategiat, On koko käyrä sekoitettu pelaaja strategioita A, jotka ovat optimaalisia, p 1 \u003d 0 p 1 \u003d 1/3 (Fig. 4.11).

Varmista esimerkiksi, että samat keskimääräiset voitot 2/3 onnistuvat, jos käytämme 1 ja 2 strategiaa suhteessa 1/3 ja 2/3.

Esimerkki 5. Sama olosuhteet, jotka edellisessä esimerkissä, mutta meille on neljä vaikutuksen suuntaa, ja vihollisella on neljä asetta.

Päätös.Meillä on vielä kaksi mahdollista strategiaa: 1 - Lähetä ilma-alus yksi kerrallaan ja 2 - Lähetä kaksi ilma-alusta yhdessä. Vastustajalla on viisi mahdollista strategiaa: 1 - laittaa yksi työkaluun kullekin suuntaan; 2 - laittaa kaksi asetta kahteen eri suuntiin; 3 - laittaa kaksi asetta yhteen suuntaan ja yksi kerrallaan - kaksi muuta; Vuonna 4 laittaa kolme asetta yhteen suuntaan ja yksi - toiseen; 5 - Laita kaikki neljä asetta yhteen suuntaan. Strategiat 4: ssä, 5 heitto etukäteen yhtä selvästi epäedullinen. Väittää samalla tavalla kuin edelliseen esimerkkiin, rakentamme pelin matriisi:

Alhaisempi hinta 1/2 peli, ylempi 3/4. Matriisilla ei ole satulapistettä; Päätös on sekalaisten strategioiden alalla. Geometrisen tulkinnan käyttäminen (Kuva 4.12) Korostamme "hyödyllisiä" vihollisen strategioita: 1 ja 2: ssä.

Taajuudet P 1 ja P 2 Määritämme yhtälöistä: P 1 * 0 + (1 - P 1) * 1 \u003d ν ja P 1 * 5/6 + (1 - P 1) * 1/2 \u003d ν; Jossa p 1 \u003d 3/8; P 2 \u003d 5/8; ν \u003d 5/8, ts. Optimaalinen strategiamme on . Käyttämällä sitä takaavat itsellesi keskimääräiset voitot 5/8. Tietäen pelin hinta ν \u003d 5/8, löydämme taajuuden Q 1 ja Q 2 "hyödylliset" vihollisen strategiat: Q 1 * 0 + (1 - Q 1) * 5/6 \u003d 5/8, q 1 \u003d ¼, q 2 \u003d ¾. Optimaalinen vihollisen strategia on: .

Esimerkki 6. Party A: lla on kaksi strategiaa A 1 ja A 2, sivu B - neljä B 1, 2, 3 ja 4: ssä. Pelin matriisi on lomake:

Etsi ratkaisu peliin.

Päätös. Pelin alhaisempi hinta 3; TOP 4. Geometrinen tulkinta (kuva 4.13) osoittaa, että pelaajan hyödylliset strategiat ovat 1 ja 2 tai 2 ja 4:

Pelaajalla A on äärettömän monia optimaalisia strategioita: Optimaalisessa strategiassa P 1 voi vaihdella 1/5 - 4/5. Pelin hinta ν \u003d 4. Pelaajalla on puhdas optimaalinen strategia 2.

§ 5. Yleiset menetelmät loppupelejen ratkaisemiseksi

Meillä on toistaiseksi vain useimmat tyypin 2xn-pelit, jotka voidaan yksinkertaisesti ratkaista ja mahdollistaa kätevän ja visuaalisen geometrisen tulkinnan. Yleisessä tapauksessa MXN-peliratkaisu edustaa melko vaikeaa tehtävää ongelman monimutkaisuuden ja laskennan ratkaistamiseen tarvittavan laskennan määrän kasvaessa M ja N. Näillä vaikeuksilla ei kuitenkaan ole perustavanlaatuista ja niillä on vain erittäin suuri määrä siirtokuntia, jotka joissakin tapauksissa voi olla käytännössä mahdotonta. Päätöksen päätöksen pääpuoli pysyy minkä tahansa M: n kanssa ja sama.

Kuvaamme tätä pelin esimerkissä 3xn. Antakaamme hänen geometrisen tulkinnan - jo spatiaalinen. Kolme strategiamme ja 1, 2 ja 3 ovat kolme pistettä koneella hous; Ensimmäinen on koordinaattien alussa (kuva 5.1), toinen ja kolmas - akseleilla vai niin ja Ou Etäisyydellä 1 alusta alkaen.

Pisteiden A 1 ja 2 ja 3 kautta suoritetaan akseli I. – I., II. – II. ja III – IIIkohtisuoraan tasoon hous. Akselilla I. – I. Voitot siirretään, kun strategia A 1 akseleilla II. – II. ja III – III - Voitot strategiat A 2 ja 3. Jokainen vihollisen strategia B J esittää koneen, joka katkaisee akseleilla I. – I., II. – II. ja III – III Segmentit ovat yhtä suuria voitot, joilla on asianmukaiset strategiat A 1, A 2 ja 3 ja strategia j. Näin ollen kaikki vihollisen strategioiden rakentaminen, saamme kolmioon A 1, A 2 ja 3 (kuva 5.2). Tälle perheelle voit myös rakentaa pienemmän rajan voitot, kuten 2xn: n tapauksessa ja etsimme pisteen n tällä rajalla, jonka korkein korkeus on koneen yläpuolella hous. Tämä korkeus on peli ν.

Taajuudet P1, P2, P3 Strategiat A 1, 2 ja 3 optimaalisessa SA * -strategiassa määritetään pisteen n koordinaattien (X, y) avulla, nimittäin: p 2 \u003d x, p3 \u003d Y, P 1 \u003d 1 - P 2 - P3. Tällainen geometrinen rakentaminen jopa 3xn: n tapauksessa ei ole helppo toteuttaa ja vaatii mielikuvitusta. Pelin yleisen tapauksen mukaan se siirretään M-ulotteiseen tilaan ja menettää kaikki näkyvyyden, vaikka geometrisen terminologian käyttö joissakin tapauksissa voi olla hyödyllinen. Kun ratkaista MXN-pelejä käytännössä, on helpompaa käyttää geometrisiä analogeja, vaan lasketuilla analyyttisellä menetelmällä varsinkin sijoitetun ongelman ratkaisemiseksi laskentakoneiden ongelman ratkaisemiseksi nämä menetelmät ovat yksinomaan sopivia.

Kaikki nämä menetelmät vähenevät olennaisesti ongelman ratkaisemiseksi peräkkäisillä näytteillä, mutta näytesekvenssin tilaaminen mahdollistaa algoritmin rakentamisen, joka johtaa taloudellisin tavoin ratkaista. Täällä keskitymme lyhyesti samaan laskettuun menetelmään MXN-pelien ratkaisemiseksi - ns. "Lineaarinen ohjelmointi" -menetelmällä. Tehdä tämä, annamme ensin ongelman yleisen asetuksen MXN-pelin päätöksen löytämisestä. Anna MXN-pelin M-strategioilla A 1, 2, ... ja M-soitin A ja N Strategiat B 1, B 2, ..., B n soitin ja asetetaan Maksutapa Matrix ‖A I J ‖. Minun on löydettävä päätös pelin, ts. Kaksi optimaalista sekastrategiaa pelaajien A ja

jossa P 1 + P 2 + ... + P m \u003d 1; Q 1 + Q 2 + ... + q n \u003d 1 (jotkut numerot p I ja q j voivat olla nolla).

Optimaalinen strategia S A *: n pitäisi antaa meille voitot, ei vähemmän ν, minkä tahansa vihollisen käyttäytymistä ja voiton yhtä suuri kuin ν, sen optimaalinen käyttäytyminen (strategia s b *). Samoin strategia S B *: n pitäisi antaa vastustaja, jolla on tappio, ei suurempi kuin ν, jolla tahansa käyttäytymisestämme ja yhtä suuri kuin ν optimaalinen käyttäytyminen (strategia s a *).

Game ν: n hinnan suuruus tässä tapauksessa ei ole meille tuntematon; Oletamme, että se on yhtä suuri kuin jotkut positiivinen numero. Uskoo, että emme rikkoa perustelun yleisyyttä; Jotta voisit olla ν\u003e 0, on selvää, että kaikki matriisin elementit ‖ a j ‖ olivat ei-negatiivisia. Tämä voidaan aina saavuttaa lisäämällä elementtejä ‖A i j ‖ melko myönteisen arvon L.; Samaan aikaan pelin hinta kasvaa L.ja päätös ei muutu.

Olkoon valitsi optimaalinen strategia s *. Sitten keskimääräiset voitot strategiat B J Enemy on yhtä suuri: J \u003d P 1 A 1J + P 2 A 2J + ... + P m A MJ. Optimaalisen strategian S A * on omaisuus, jonka avulla vihollisen käyttäytyminen takaa voitot vähintään ν; Näin ollen mikä tahansa numero J J ei voi olla vähemmän ν. Saamme useita ehtoja:

Me jakaamme epätasa-arvot (5.1) ν ja merkitsevät

Sitten olosuhteet (5.1) tallennetaan lomakkeeseen

missä ξ 1, ξ 2, ..., ξ m eivät ole negatiivisia numeroita. Koska P 1 + P 2 + ... + p m \u003d 1, arvot ξ 1, ξ 2, ..., ξ m täyttävät tilan

(5.3) ξ 1 + ξ 2 + ... + ξ m \u003d 1 / ν.

Haluamme tehdä taatut voitot mahdolliseksi; Ilmeisesti, samanaikaisesti oikea osa Tasa-arvo (5.3) ottaa vähimmäisarvo. Näin ollen tehtävän löytämisestä pelin ratkaisu vähenee seuraavaan matemaattiseen ongelmaan: määrittää ei-negatiiviset arvot ξ 1, ξ 2, ξ m, tyydyttävät olosuhteet (5.2), niin että niiden summa φ \u003d ξ 1 + ξ 2 + ... + ξ m Se oli minimaalinen.

Yleensä, kun ratkaisee äärimmäisiä arvoja (maxima ja minima) löytämiseen liittyvät ongelmat, toiminto eroaa ja tasaantuu nollajohdannaisilla. Tämä tekniikka on kuitenkin hyödytön tässä tapauksessa, koska funktio φ, joka on käänteinen, lineaarinen ja sen johdannaiset kaikissa väitteissä ovat yhtä suuria kuin yksi eli eli. Älä käänny nollaksi. Siksi enimmäisfunktio saavutetaan jonnekin väitteiden muutoksen alueen rajalla, joka määräytyy väitteiden ja ehtojen muista kuin negatiivisuudesta (5.2). Äärimmäisten arvojen hyväksyminen erilaistumisen avulla ei ole sopiva ja tapauksissa, joissa voitot pienempi (tai ainakin ylhäältä) rajat määritetään ratkaista pelin, kuten esimerkiksi määritettiin 2xn-pelien ratkaisemisessa. Itse asiassa alaraja koostuu suorista linjoista ja enimmäismäärästä ei saavuteta pisteessä, jossa johdannainen on nolla (ei ole sellaista pistettä ollenkaan) ja aikavälillä tai suoraviivaisen risteyksessä sivustot.

Tällaisten tehtävien ratkaiseminen melko usein esiintyy käytännössä, erityinen lineaarinen ohjelmointilaite on kehitetty matematiikassa. Lineaarisen ohjelmointin tehtävä on seuraava. Dana Lineaaristen yhtälöiden järjestelmä:

Sinun on löydettävä muut kuin negatiiviset arvot ξ 1, ξ 2, ξ, ξ m, tyydyttävät olosuhteet (5.4) ja samalla maksamalla vähintään tietyn homogeenisen lineaarisen funktion arvot ξ 1, ξ 2, ξ, ξ m (lineaarinen muoto): φ \u003d c 1 ξ 1 + c 2 ξ 2 + ... + cm ξ m

On helppo varmistaa, että peliteorian edellä mainittu tehtävä on erityinen tapaus lineaarisen ohjelmointiongelman C1 \u003d C 2 \u003d ... \u003d cm \u003d 1. yhdellä silmäyksellä, voi näyttää siltä, \u200b\u200bettä olosuhteet (5.2) eivät vastaa olosuhteita (5.4), koska sen sijaan tasa-arvomerkit sisältävät epätasa-arvot. Kuitenkin epätasa-arvoisista merkkeistä on helppo päästä eroon, esittelee uusia fiktiivisiä ei-negatiivisia muuttujia Z1, Z 2, ..., Z N ja tallennusolosuhteet (5.2) muodossa:

Lomake φ, joka on käännettävä minimiin, on φ \u003d ξ 1 + ξ 2 + ... + ξ m. Lineaarinen ohjelmointilaite mahdollistaa suhteellisen pienen määrän peräkkäisiä näytteitä valitaksesi arvon ξ 1, ξ 2, ..., ξ m vaatimusten täyttämiseksi. Selvyyden lisäämiseksi näemme täältä soveltaa tätä laitetta suoraan tiettyjen pelien ratkaisemisessa.

Esimerkki 1. Sen on löydettävä esimerkissä 2 annettu peli 3 × 3 liuos, jossa on matriisi:

Voit tehdä kaiken ja IJ: n ei-negatiivisen, lisätä kaikki matriisi L \u003d 5. Saat matriisin:

Samaan aikaan pelin hinta kasvaa 5, ja päätös ei muutu.

Määritämme optimaalisen strategian S a *. Edellytykset (5.2) ovat muodossa:

jossa ξ 1 \u003d p 1 / ν, ξ 2 \u003d p 2 / ν, ξ 3 \u003d p3 / ν. Päästä eroon epätasa-arvoista, esitämme fiktiiviset muuttujat z 1, z 2, z 3; Edellytykset (5.6) kirjataan lomakkeeseen:

Lineaarinen muoto φ on: φ \u003d ξ 1 + ξ 2 + ξ 3 ja se on tehtävä niin vähän kuin mahdollista. Jos kaikki kolme strategiaa ovat "hyödyllisiä", kaikki kolme fiktiivistä muuttujaa Z 1, Z2, Z3 kääntyvät nollaan (eli pelin ν hinnan vastaavat voitot saavutetaan jokaisen B J-strategian kanssa). Mutta emme ole vielä syytä väittää, että kaikki kolme strategiaa ovat "hyödyllisiä". Testaa se, yritämme ilmaista muotoa φ kuvitteellisten muuttujien Z 1, z 2, z 3 kautta ja katso, jos uskomme, että ne ovat nolla, vähimmäismuoto. Tehdä tämä, ratkaise yhtälöt (5.7) suhteessa muuttujiin ξ 1, ξ 2, ξ 3 (eli express ξ 1, ξ 2, ξ 3 fiktiivisten muuttujien Z 1, z 2, z 3) kautta:

Taitettava ξ 1, ξ 2, ξ 3 saamme: φ \u003d 1/5 + Z 1/20 + Z 2/10 + Z 3/2 20. Täällä kaikki Z: n kertoimet ovat positiivisia; Se tarkoittaa, että Z 1: n, Z 2: n, Z 3: n lisääntyminen nolla voi johtaa vain lomakkeen φ kasvuun ja haluamme sen olevan minimaalinen. Näin ollen Z 1, Z2, Z3, muodon φ arvot z 1 \u003d z 2 \u003d z 3 \u003d 0. Siksi muodon φ: 1 / ν \u003d 1 vähimmäisarvo / 5, mistä pelin hinta ν \u003d 5. Nolla-arvojen korvaaminen Z 1, Z 2, Z 3 Kaavassa (5.8), löydämme: ξ 1 \u003d 1/20, ξ 2 \u003d 1/10, ξ 3 \u003d 1/20, tai, kertoo ne ν, p 1 \u003d 1/4, p 2 \u003d 1/2, p3 \u003d 1/4. Näin ollen optimaalinen strategia ja havaittu: . Meidän on kirjoitettava neljäsosaa kaikista tapauksista kuvioon 1, puolet tapauksissa 2 ja loput tapauksista 3.

Tietäen pelin hinta ν \u003d 5, voit jo tietää, miten löytää optimaalinen vihollisen strategia . Tätä varten käytämme mitä tahansa kaksi "hyödyllistä" strategiaa (esimerkiksi ja 2 ja A 3) ja kirjoittaa yhtälöt:

9q 1 + 11 (1-Q 2 -Q 1) \u003d 5,

mistä Q 1 \u003d Q3 \u003d 1/4; Q 2 \u003d 1/2. Optimaalinen vihollisen strategia on sama kuin meidän: . Nyt takaisin alkuperäiseen (ei muunnettu) peli. Tehdä tämä, on välttämätöntä vain pelin ν \u003d 5 hinnasta, kun otetaan määrä L \u003d 5, lisätään matriisin elementteihin. Saavutamme alkuperäisen pelin hinnan V 0 \u003d 0. Näin ollen molempien osapuolten optimaaliset strategiat tarjoavat keskimääräisen nousun nolla; Peli on yhtä hyödyllinen tai kannattamaton molemmille osapuolille.

Esimerkki 2. Urheiluklubissa A on kolme varianttia ryhmän kokoonpanosta A 1, ja 2 ja 3. Club B on myös kolme suoritusmuotoa B 1, 2 ja 3. Hakemuksen soveltaminen kilpailuun, mikään klubista ei tiedä, mitä koostumusta valitsee vastustajan. Todennäköisyys voittaa klubin A erilaisten tiimiformulaatioiden varianttien kanssa, jotka ovat suunnilleen tunnettuja aiempien kokousten kokemuksesta, asettavat matriisi:

Etsi joitakin taajuusklubeja, joista jokainen kokouskokous olisi tehtävä saavuttamaan suurimman määrän voittoja.

Päätös. Pelin alhaisempi hinta 0,4; Top 0.6; Ratkaisu Etsimme sekalaisten strategioiden alalla. Jotta fraktioita ei käsitellä, kerro kaikki matriisin elementit 10: llä; Samaan aikaan pelin hinta kasvaa 10 kertaa, ja päätös ei muutu. Saamme matriisin:

Edellytykset (5.5) ovat muodossa:

ja minimitila φ \u003d ξ 1 + ξ 2 + ξ 3 \u003d min.

Tarkistamme, onko kaikki kolme vihollisen strategiaa "hyödyllisiä". Kuten hypoteesia, oletetaan ensin, että fiktiiviset muuttujat z 1, z 2, z 3 ovat nolla ja testata yhtälö (5.10) suhteessa ξ 1, ξ 2, ξ 3:

(5,12) 136φ \u003d 30 + 13Z 1 + 18Z 2 - 51Z 3

Kaava (5,12) osoittaa, että muuttujien Z 1 ja Z2 lisääntyminen verrattuna niiden arvioitu arvo nolla voi lisätä vain φ, kun taas Z 3: n kasvu voi vähentää φ. Z 3: n kasvu on kuitenkin suoritettava huolellisesti, että arvot ξ 1, ξ 2, ξ 3 riippuu Z3: stä, ei tullut negatiiviseksi. Siksi asetamme oikeat osat (5.11) Z 1: n ja Z 2: n arvot ovat nolla, ja arvo Z3 nousee sallittuihin rajoihin (toistaiseksi arvoista ξ 1, ξ 2, ξ 3 ei muutu nollaan). Toisesta tasa-arvosta (5.11) Voidaan nähdä, että Z 3 "turvallisesti" lisäys ξ 2 - se kasvaa vain siitä. Kuten arvot ξ 1 ja ξ 3, täältä Z 3: n kasvu on mahdollista vain tiettyyn rajaan. Arvo ξ 1 vetoaa nollaan Z 3 \u003d 10/23; Arvo ξ 3 vetoaa nollaan aikaisemmin, jo Z 3 \u003d 1/4. Siksi z 3: n suurimman sallitun arvon Z 3 \u003d 1/4, kun käännymme nolla-arvoksi ξ 3.

Tarkista, onko lomake φ näkyy vähintään Z 1 \u003d 0, z 2 \u003d 0, ξ 3 \u003d 0, ilmamme jäljellä olevat (ei yhtä suuret nolla) muuttujat väitetysti yhtä suurella nolla z 1, z 2, ξ 3. Yhtälöiden ratkaiseminen (5.10) Suurenna ξ 1, ξ 2 ja z 3, saamme:

(5.13) 32φ \u003d 7 + zz 1 + 4Z 2 + ξ 3

Kaapasta (5.13) Voidaan nähdä, että Z1, Z2, ξ 3 kasvaa niiden aiottujen nolla-arvojen yli voi lisätä vain muotoa φ. Näin ollen pelin päätös löytyy; Se määräytyy arvot Z 1 \u003d z 2 \u003d ξ 3 \u003d 0, mistä ξ 1 \u003d 1/32, ξ 2 \u003d 3/16, z 3 \u003d 1/4. Korvaavan kaavan (5.13), löydämme pelin hinnan ν: 32φ \u003d 7 \u003d 32 / ν; ν \u003d 32/7. Optimaalinen strategiamme: . "Hyödyllisiä" strategioita (koostumuksia A 1 ja A 2) olisi sovellettava taajuuksilla 1/7 ja 6/7; Koostumus A 3 - ei koskaan sovelleta.

Jos haluat löytää optimaalisen vihollisen strategian yleensä, voit tehdä tämän: Muuta merkki voittamisesta taaksepäin, lisää Matriisi vakion arvon elementteihin, jotta ne eivät ole negatiivisia ja ratkaista tehtävänsä vihollisen tehtäväksi Ratkaisimme sen itselleen. Kuitenkin se, että pelin ν hinta on jo tiedossa meille, jonkin verran yksinkertaistaa tehtävää. Lisäksi tämä konkreettinen tapaus Tehtävää yksinkertaistetaan lisäksi sillä, että vain kaksi "hyödyllistä" vihollisen strategiaa 1 ja 2 osallistuvat päätökseen, koska Z 3 -arvo ei ole nolla, ja se tarkoittaa, että peliä ei saavuteta 3. Valitsemalla "hyödyllinen" pelaajan strategia A, esimerkiksi 1, löydät taajuuksia Q 1 ja Q 2. Tee tämä, kirjoita yhtälö 8Q 1 + 2 (1 - Q 1) \u003d 32/7, mistä Q 1 \u003d 3/7, Q 2 \u003d 4/7; Optimaalinen vihollisen strategia on: . Vihollisen ei pitäisi käyttää 3 koostumusta, ja 1 ja 2: n koostumukset on käytettävä taajuuksilla 3/7 ja 4/7.

Paluu alkuperäiseen matriisiin, määritämme pelin todellisen hinnan ν 0 \u003d 32/7: 10 \u003d 0,457. Se tarkoittaa, että iso numero Kokoukset Klubin A-voiton määrä on 0,457 kaikista kokouksista.

§ 6. Likimääräiset menetelmät pelien ratkaisemiseksi

Usein käytännön tehtävissä ei ole tarvetta löytää tarkkaa päätöstä pelistä; Riittää likimääräisen ratkaisun löytäminen, jolloin keskimääräinen voitto, lähellä pelin hintaa. Game ν: n hinnan arvioitu tuntemus voi jo antaa yksinkertaisen analyysin matriisista ja alemman (α) ja pelin ylemmän (β). Jos α ja β ovat lähellä, on käytännössä tarvetta etsiä tarkkaa ratkaisua, mutta se riittää valitsemaan nettimaksiset strategiat. Tapauksissa, joissa α ja β eivät ole lähelle, on mahdollista saada hyväksyttävä ratkaisu käytäntöön numeeristen menetelmien avulla, joista lyhentää iterointimenetelmän lyhyesti.

Ajatus iterointimenetelmästä vähennetään seuraavaan. "Henkinen kokeilu" pelataan, jossa vastustajat A ja B soveltavat strategioitaan toisiaan vastaan. Koe koostuu peruspeleistä peräisin olevasta sekvenssistä, joista jokaisella on tietyn pelin matriisi. Se alkaa siitä, että me (pelaaja A) valitse mielivaltaisesti yksi sen strategioista, esimerkiksi ja i. Vihollinen on vastuussa tästä strategiasta B J, joka on vähiten hyödyllinen meille, ts. Kääntää voitot, kun strategiat ja minä minimi. Tällä liikkeellä vastaamme samaan strategiaan A K, joka antaa keskimääräisen voiton vastustajan strategian B j. Seuraava - jälleen vastustajan kääntyminen. Hän vastaa pari liikkua I ja K sen strategian B j, mikä antaa meille pienimmät keskimääräiset voitot näillä kahdella strategialla (i ja k) ja niin edelleen. Jokaisessa iteratiivisen prosessin vaiheessa jokainen pelaaja vastaa minkä tahansa toisen pelaajan kanssa strategiansa kanssa, mikä on optimaalinen kaikista aikaisemmista liikkeistään, jota pidetään sekavana strategiana, jossa puhtaita strategioita esitellään suhteessa niiden soveltamisen taajuutta .

Tämä menetelmä on kuin pelaajien todellinen käytännöllinen "oppiminen" malli, kun jokainen niistä kokee vastustajan käyttäytymistä ja yrittää vastata siihen suotuisaan itselleen. Jos tällainen oppimisprosessin simulointi jatkuu riittävän kauan, sitten keskimääräiset voitot liikkuu (alkeellinen peli) pyrkivät pelin hintaan ja taajuuksiin p 1 ... p m; Q 1 ... Q N, jonka kanssa pelaajat strategiat löytyvät tästä vedystä, lähestyvät taajuuksia, jotka määrittävät optimaaliset strategiat. Laskelmat osoittavat, että menetelmän lähentyminen on kuitenkin hyvin hidasta suurten nopeuksien laskentakoneille, tämä ei ole este.

I havainnollistamme iteratiivisen menetelmän soveltamista pelin esimerkissä 3 × 3, joka on ratkaistu edellisen kohdan esimerkissä 2. Peli asettaa matriisi:

Taulukossa 6.1 esitetään iteratiivisen prosessin ensimmäiset 18 vaiheet. Ensimmäisessä sarakkeessa annetaan alkupelien lukumäärä (liikkeen parit) n.; Toisessa numerossa I. Valittu soittimen strategia A; Seuraavat kolme - "kertynyt voitot" ensimmäiselle n. Pelit, joissa vihollisen strategiat B 1, 2, 3. Näiden arvojen vähimmäisarvo korostetaan. Seuraavaksi tulee numero j. Vihollisen valitsema strategia ja kertynyt voitto n. Pelit strategiassa A 1, ja 2 ja 3 näistä arvoista korostetaan suurimmasta suurimmasta arvosta. Alleviivatut arvot määrittävät toisen pelaajan vastausstrategian valinnan. Seuraavat sarakkeet annetaan peräkkäin: vähimmäisimmät keskimääräiset voitot ν, joka on yhtä suuri kuin vähintään kertynyt voitto jaettuna pelien määrä n.; Suurin keskimääräinen voitto, joka on yhtä suuri kuin suurin kertynyt voitto jaettu n.ja niiden aritmeettinen keskiarvo ν * \u003d (ν +) / 2. Kasvava n. Kaikki kolme arvoa vastaan \u200b\u200bja ν * lähestyvät pelin ν: n hintaa, mutta ν * arvo lähestyy luonnollisesti suhteellisen nopeammin.

Taulukko 6.1.

Kuten esimerkistä voidaan havaita, iteraatioiden lähentyminen on hyvin hidasta, mutta jopa tällainen pieni laskelma mahdollistaa pelin hinnan likimääräisen arvon ja paljastaa "hyödyllisiä" strategioita. Kun käytät laskettavia koneita, menetelmän arvo kasvaa merkittävästi. Pelin ratkaisemisen iteratiivisen menetelmän etu on se, että laskelmien määrä ja monimutkaisuus suhteellisen heikosti kasvavat, kun strategioiden määrä kasvaa m. ja n..

§ 7. Menetelmät loputtomien pelien ratkaisemiseksi

Loputon peli kutsutaan peliksi, jossa ainakin yksi osapuolista on ääretön joukko strategioita. Yleiset menetelmät tällaisten pelien ratkaisemiseksi ovat edelleen hieman suunniteltuja. Jotkut erityiset tapaukset, jotka mahdollistavat suhteellisen yksinkertaisen ratkaisun, voivat olla kiinnostavia käytäntöjä. Harkitse kahden vastustajan A ja B pelin, joista jokaisella on ääretön (lukematon) strategiat; Nämä pelaajan strategiat vastaavat erilaisia \u200b\u200barvoja jatkuvasti muuttuva parametri h.ja sisään - parametri w.. Tällöin matriisin ‖a ij ‖ sijasta peli määrittää jonkin verran kahden jatkuvasti muuttuvan argumentin a (x, y)jonka kutsumme voitot-toiminnoksi (huomaat, että toiminto itse a (x, y) Sen ei pitäisi olla jatkuva). Voita toiminto a (x, y) voidaan esittää geometrisesti jotkut pinnat a (x, y) Argumenttien muutosalueen yläpuolella (x, y) (Kuva 7.1)

Voitot-toiminnon analyysi A (x, y) Se suoritetaan samanlainen kuin maksumatriisin analyysi. Ensin pelin hinta on alhaisempi hinta; Sillä tämä on määritetty kaikille h. Vähimmäisfunktio a (x, y) kaikkiaan w.: Sitten etsitään enimmäismäärät kaikkiin H. (Maximine):

Pelin huippu hinta (minimix) määritellään samalla tavalla:

Harkitse tapausta, kun α \u003d β. Koska pelin ν hinta päättyy aina α ja β, niin niiden merkitys on ν. Tasa-arvo α \u003d β tarkoittaa pintaa a (x, y) on satulapiste, eli tällainen kohta, jossa koordinaatit X 0, 0, jossa a (x, y) on samanaikaisesti vähäinen W. ja enimmäismäärä h. (Kuva 7.2).

Arvo a (x, y) Tässä vaiheessa on hinta ν: ν \u003d a (x 0, y 0). Satulapisteen läsnäolo tarkoittaa, että tämä loputon peli on ratkaisu puhtaiden strategioiden alalla; x 0, Y 0 Optimaalisia puhtaita strategioita A ja V. Yleensä, kun α β, peli voi olla ratkaisu vain seka strategioiden alalla (ehkä ei ainoa). Seka Strategia loputtomiin peleihin on olemassa todennäköisyysjakelu strategioihin h. ja w.pidetään satunnaisina muuttujina. Tämä jakelu voi olla jatkuva ja määrittää tiheydet. f. 1 x) ja f. 2 (y); Se voi olla erillinen ja optimaaliset strategiat koostuvat erillisistä nettostrategioista, jotka on valittu joidenkin ei-nolla-todennäköisyyksien kanssa.

Siinä tapauksessa, kun loputon peli ei ole satulapistettä, voit antaa visuaalisen geometrisen tulkinnan pelin alemmasta ja huipputasosta. Harkitse loputtomia peliä, jossa on voitot. a (x, y)ja strategiat x, W.Täytä jatkuvasti segmentit akseleita (x 1, x 2) ja (1, u 2). Voit määrittää pelin alemman hinnan α: n, sinun täytyy "nähdä" pinnalla a (x, y) Akselin puolelta w.. Muunna se koneeseen hoa (Kuva 7.3). Saavutamme jonkinlaista muotoa, rajoitettu sivuilta suoralla x \u003d x 1 ja x \u003d x 2 ja ylhäältä ja alapuolelta - käyrät B: lle ja N: lle käyrän järjestys N.

Samoin löytää pelin β huippuluokan hinta, sinun täytyy "nähdä" pinnalla a (x, y) Akselin puolelta h. (Suunnittele pinta koneeseen vetelehtiä) ja löydä ylärajan vähimmäisordinaatti ulokkeeseen (kuva 7.4).

Harkitse kaksi perusteellista esimerkkiä loputtomasta peleistä.

Esimerkki 1. Pelaajat A ja B on kaikki lukemattomia monia mahdollisia strategioita. h.ja w.Lisäksi 0 ≤ x ≤ 1; 0 ≤ Y ≤ 1. A: n voiton toiminto annetaan ilmaisulla A (X, Y) - (X - Y) 2. Etsi ratkaisu peliin.

Ratkaisu, pinta A (X, Y) on parabolinen sylinteri (kuva 7.5) ja sillä ei ole satulaatua pistettä. Määritämme pelin alemman hinnan; Ilmeisesti kaikille h.; Siksi \u003d 0. Määritä pelin ylempi hinta. Tehdä tämä, löydämme kiinteän w.

Tällöin enimmäismäärä saavutetaan aina aikavälillä (x \u003d 0 tai x \u003d 1), ts. Se on yhtä suuri kuin 2; (1 - Y) 2, mikä on enemmän. Kuvittelen näiden toimintojen kaavioita (kuva 7.6), ts. Pinnan ulkonema a (x, y) Lentokoneessa vetelehtiä. KUVA. 7.6 Ominaisuus näytetään. On selvää, että sen vähimmäisarvo saavutetaan Y \u003d 1/2: ssa ja yhtä suuri kuin 1/4. Näin ollen pelin huippu hinta β \u003d 1/4. Tällöin pelin huippu hinta vastaa pelin hinta ν. Itse asiassa pelaaja A voi soveltaa sekoitettua strategiaa a \u003d johon äärimmäiset arvot X \u003d 0 ja X \u003d 1 sisältyvät samoilla taajuuksilla; Sitten millä tahansa strategialla, pelaaja keskimäärin pelaajan voittaminen A on yhtä suuri kuin ½u 2 + ½ (1 - Y) 2. On helppo varmistaa, että tämä arvo arvoille w. 0 - 1, se ei ole pienempi kuin ¼: ½u 2 + ½ (1 - y) 2 ≥ ¼.

Näin ollen pelaaja ja tämän sekoitetun strategian käyttö voi taata pelin huipputason voitot; Koska pelin hinta ei voi olla suurempi kuin huippu hinta, sitten tämä strategia S Optimaalinen: s a \u003d s a *.

Pelaaja V: n optimaalinen strategia on edelleen olemassa pelistä. Tällöin tällainen strategia on 0 \u003d ½. Itse asiassa tämän strategian kanssa, mitä pelaaja a, voitot eivät ole enemmän ¼. Tämä seuraa ilmeistä epätasa-arvoa (x - ½) 2 \u003d x (x -1) + ¼ ≤ ¼

Esimerkki 2. Side A ("Me") johtaa lentokoneen vastustajalle. Jotta voitte valettua kuoresta, vihollinen voi ohjata ylikuormitusta w.jonka hänen harkintansa mukaan voi kiinnittää merkityksen w. \u003d 0 (suora liike) - w. = w. Max (Lentää suurimman kaarevuuden ympärysmitta). Oletamme w. Max Mittayksikkö, ts. Laittaa w. Max \u003d 1. Vihollisen torjunnassa voimme käyttää näyttölaitteita, jotka perustuvat yhteen tai toiseen hypoteesiin palveluliikkeen palveluksessa. Ylikuormitus h. Tällöin hypoteettinen liikkumavaraa voi luottaa arvoon 0 - 1. Tehtävämme on lyödä vihollista; Vihollisen tehtävä on pysyttävä ennallaan. Tietojen vaurioitumisen todennäköisyys h. ja w. Suunnilleen ilmaistuna kaava: a (x, y) \u003d , Missä w. - vihollisen ylikuormitus; X - ylikuormitus, otettu huomioon silmissä. Sen on määritettävä molempien osapuolten optimaaliset strategiat.

Päätös. On selvää, että peliratkaisu ei muutu, jos laitamme P \u003d 1. WIN -toiminto a (x, y) Kuvataan kuviossa 2 esitetyssä pinnalla. 7.7.

Tämä on sylinterimäinen pintamuodostus, joka yhdensuuntainen koordinaattikulman bisectin kanssa housJa koneen poikkileikkaus, joka on kohtisuorassa muodostumiseen, on käyrä normaalin jakelukäyrän tyypin. Käyttämällä pelin alemman ja huipputason ehdotettua geometrista tulkintaa, löydämme β \u003d 1 (kuva 7.8) ja (kuva 7.9). Pelillä ei ole satulapistettä; Päätös, jota sinun on etsittävä sekastrategioiden alalla. Tehtävä on jossain määrin samanlainen kuin edellisen esimerkin tehtävä. Itse asiassa pienillä arvoilla k. Toiminto käyttäytyy suunnilleen toiminnona - (X - Y) 2, ja peliratkaisu toimii, jos ratkaisemalla edellinen esimerkki, muuta pelaajien A ja B rooleja; nuo. Optimaalinen strategiamme on puhdas strategia X \u003d 1/2, ja vihollisen SB: n optimaalinen strategia on äärimmäisten strategioita Y \u003d 0 ja Y \u003d 1. Tämä tarkoittaa sitä, että meidän on käytettävä näkymää kaikissa tapauksissa, lasketaan Ylikuormitukseen x \u003d 1/2, ja vihollisen ei pitäisi käyttää liikkumavaraa puolessa kaikista tapauksista ja puolet mahdollisimman suuresta liikkumisesta.

Kuva. 7,8 Kuva. 7.9.

On helppoa todistaa, että tämä päätös on oikeudenmukainen arvoille k ≤ 2. Itse asiassa keskimääräiset voitot vihollisen strategian kanssa s b \u003d ja strategiamme kanssa h. Se ilmaistaan \u200b\u200btoiminnolla , mitkä arvot k ≤ 2: lla on yksi enimmäismäärä x \u003d 1/2, joka on yhtä alhaisempi hinta α. Näin ollen strategian S b soveltaminen takaa menetyksen vihollisen, ei enemmän kuin α, mikä on selvää, että α on pelin alhaisempi hinta - ja peli ν.

K\u003e 2: ssä toiminnossa A (X) on kaksi maksimia (kuvio 7.10), joka sijaitsee symmetrisesti suhteessa x \u003d 1/2 pisteeseen X 0 ja 1 - X 0 ja X 0: n arvo riippuu k.

Ilmeisesti, sillä k. \u003d 2 x 0 \u003d 1 - x 0 \u003d ½; Kasvava k. Pisteitä X 0 ja 1 - X0 siirretään, lähestyvät lähempänä äärimmäisiä kohtia (0 ja 1). Näin ollen pelin ratkaisu riippuu k. Asetamme K: n spesifinen arvo, esimerkiksi K \u003d 3 ja löytää ratkaisu peliin; Tehdä tämä, määritämme suurimman käyrän ABSCISSA X 0: n (x). Nollaajohdannainen toiminto A (X), kirjoita yhtälö X 0: n määrittämiseksi:

Tämä yhtälö on kolme juuria: x \u003d 1/2 (missä se saavutetaan vähintään) ja x 0, 1 - x 0, jossa maksimit saavutetaan. Yhtälöiden ratkaistaminen numeerisesti löydämme noin x 0 ≈ 0,07; 1 - X 0 ≈ 0,93.

Todistamme, että pelin päätös tässä tapauksessa on seuraava strategioita:

Strategiamme ja vihollisen strategiamme kanssa w. Keskimääräinen voitto on yhtä suuri

Etsi vähintään 1 (Y) 0: ssa< у < 1. Функция a 1 (y) симметрична относительно y = 1/2 и может иметь только один или два максимума; ее минимум, во всяком случае, достигается либо в середине отрезка (0, 1), либо на его концах. Полагая у = 0 (или у = 1), найдем

Uskoa y \u003d 1/2, saamme

joka on suurempi kuin 1 (0); Näin ollen pelin hinta on vähintään 1 (0):

Nyt sanotaan, että vihollinen soveltaa strategiaa S B *, ja olemme strategia X. Sitten keskimääräinen voitto

Mutta valitsimme x 0 tällä tavalla, jotta x \u003d x 0 saavutti maksimaalisen lausekkeen (7.2); siten,

nuo. Vastustaja strategian S B * avulla ei saa sallia tappiota, yli 0,530; Siksi ν \u003d 0,530 on pelin hinta, ja strategia s a * ja s b * antaa ratkaisun. Tämä tarkoittaa sitä, että meidän on käytettävä silmistä x \u003d 0,07 ja x \u003d 0,93 samalla taajuudella ja vastustaja, jolla on sama taajuus, ei ole liikkumavaraa ja liikkumavaraa.

Huomaa, että voitot ν \u003d 0,530 on huomattavasti suurempi kuin pelin alhaisempi hinta Jotta voisimme turvata itsemme maksimaalisen strategian X 0 \u003d 1/2 avulla.

Yksi käytännölliset tavat Loputon pelien ratkaiseminen on niiden likimääräinen vähennys lopulliseen. Tällöin kunkin pelaajan mahdolliset strategiat yhdistetään tavanomaisesti yhteen strategiaan. Tällä tavalla tietenkin on mahdollista saada vain likimääräinen pelipäätös, mutta useimmissa tapauksissa ei tarvita tarkkaa ratkaisua.

On kuitenkin pidettävä mielessä, että tämän vastaanottoa käytettäessä ratkaisuja voi esiintyä sekalaisten strategioiden alalla myös tapauksissa, joissa alkuperäisen äärettömän pelin ratkaisu on mahdollista nettostrategiassa, ts. Kun loputon peli on satulapiste. Jos loputtoman pelin tiedot saatiin sekoitettu ratkaisu, joka sisältää vain kaksi naapurimaiden "käyttökelpoisia" strategioita, on järkevää yrittää soveltaa alkuperäisen loputtoman pelin väliverkkostrategiaa niiden välillä.

Lopuksi toteamme, että loputtomat pelit kontrastissa lopullisella ei ehkä ole ratkaisuja. Anna meille esimerkki äärettömästä pelistä, jolla ei ole ratkaisua. Kaksi pelaajaa kutsuvat kaikkiin kaikkiin kokonaislukuun. Nimetty lisää Saa toisesta 1 rupla. Jos molemmat kutsutaan samaksi numeroksi, peli päättyy vetoon. Pelillä ei tietenkään voi olla ratkaisuja. On kuitenkin olemassa loput loputtomia pelejä, joille ratkaisu on ilmeisesti olemassa.

SA-pelaajan A sekaisin strategiaa kutsutaan puhtaiden strategioiden A1, A2, ..., olen todennäköisyys P1, P2, ..., PI, ..., PM ja todennäköisyys summa on 1: sekoitettu Pelaajien strategiat A tallennetaan matriisin muodossa tai merkkijono SA \u003d (P1, P2, ..., PI, ..., PM), samoin sekoitetut soittimen strategiat nimeämisessä :, tai, sb \u003d (Q1, Q2, ..., Qi, ..., Qn), jossa strategioiden ulkonäön todennäköisyyksien summa on 1: Puhtaat strategiat voidaan pitää erityisenä sekoitettuna ja asettaa merkkijono, jossa 1 vastaa puhtaaseen strategiaan. Pelin optimaalinen ratkaisu (tai päätös) perustuu: se on parin optimaaliset strategiat s * a, s * b sekoitettuna, hallussaan seuraava omaisuus: Jos jokin pelaajista noudattaa optimaalista strategiaansa, toinen ei voi olla suotuisasti vetäytyä omasta. Optimaalista ratkaisua vastaavia voitot kutsutaan pelin V. Pelin hinta täyttää epätasa-arvo :? ? v? ? (3.5) Missä? ja? - Alempi I. ylä hinnat Pelit. Fair Seuraavat pelin teorian peruslause on Neuman Theorem. Jokaisella lopullisella pelillä on ainakin yksi optimaalinen ratkaisu, ehkä sekoitetuista strategioista. Anna s * a \u003d (p * 1, p * 2, ..., p * i, ..., p * m) ja s * b \u003d (q * 1, q * 2, ..., q * I, ..., q * n) - optimaaliset strategiat. Jos nettostrategia siirtyy optimaaliseen sekaisinstrategiaan ei-nolla-todennäköisyydellä, sitä kutsutaan aktiiviseksi. Aktiivinen strategia Theorem on pätevä: jos jokin pelaajista noudattaa optimaalista seka strategiaansa, voitot pysyvät muuttumattomina ja yhtä suurina kuin pelin V, jos toinen pelaaja ei ylitä aktiivisia strategioita. Tällä teoreella on suuri käytännöllinen merkitys - se antaa erityisiä malleja etsimään optimaalisia strategioita satulapisteen puuttuessa. Harkitse 2 × 2: n pelikokoa, joka on lopullisen pelin yksinkertaisin tapa. Jos tällaisella pelillä on satulapiste, optimaalinen ratkaisu on pari puhtaita strategioita, jotka vastaavat tätä pistettä. Peli, jossa ei ole satulapistettä, pelit teorian tärkeimmän teorian mukaan optimaalinen ratkaisu on olemassa ja määräytyy seka strategioiden s * a \u003d (p * 1, p *) ja s * B \u003d (q * 1, q * 2). Jotta voit löytää ne, käytämme todellista strategiaa teoremia. Jos pelaaja ja pitää optimaalisen strategiansa S "A, hänen keskimääräiset voitot ovat yhtä suuria kuin pelin V, riippumatta aktiivinen strategia pelaajan V. pelaamiseen 2 × 2 puhdasta vihollisen strategiaa on aktiivinen, jos ei ole Satulapiste. Voita pelaaja A (pelaajan menetys) - satunnaisarvo, jonka matemaattinen odotus (keskimääräinen arvo) on pelin hinta. Siksi keskimääräinen pelaaja voittaa A (Optimaalinen strategia) on yhtä suuri kuin ensimmäinen ja ensimmäinen, ja 2. vihollisen strategia. Anna pelin asettamalla keskimääräinen pelaajan voitot A maksamatriisi, jos se käyttää optimaalista sekoitettua strategiaa ja Pure Strategian B1 soitin (tämä vastaa maksumatriisin P) ensimmäistä saraketta, on hinta Peli V: A11 P * 1 + A21 P * 2 \u003d V. Sama keskimääräinen vahvistus vastaanottaa pelaajan A, jos toinen pelaaja soveltaa B2-strategiaa, ts. A12 P * 1 + A22 P * 2 \u003d V. Ottaen huomioon, että P * + P * 2 \u003d 1 saamme yhtälöjärjestelmän optimaalisen strategian S "A ja pelin h: (3.6) ratkaisemiseksi tämän järjestelmän ratkaisemiseksi, saamme optimaalisen strategian (3.7) ja pelin hinta (3.8) Teelekkeiden soveltaminen aktiivisista strategioista, kun löydät SV * - Optimaalisen pelaajan strategia, saamme sen, että pelaajan (A1 tai A2) puhtaalla strategialla keskimääräinen pelaajan menetys on yhtä suuri kuin hinta Pelin V eli (3.9) optimaalinen strategia määräytyy kaavojen mukaan: (3.10)

"Puhdas" strategiat

Olemme jo perehtyneitä JAMBS. Kuitenkin, mitä tapahtuu, jos poistat shoaleja minkä tahansa strategian ketjusta? Saat "puhtaan strategian". Puhtaat strategiat ovat ketjussa sellaisten toimien ketjussa, jotka vaihtelevat itseään ja tehokkaaseen osaan, ei ole tehottomia aliverkkoja (shoaleja), ja tämä voi usein todistaa vain kaikkien tietoisuuksien yksiköiden läsnäoloa.

Tietenkin kaikkien strategian soveltamisen mahdollisista tuloksista on vaikea puhua kaikkein tehokkaimmasta, koska emme yksinkertaisesti ole tiettyjä kokemuksia, ja siksi tietyt välitastrategiat ovat kuitenkin meidän Kokemus, strategian olisi oltava mahdollisimman tehokas.

Puhtaiden strategioiden käsite on myös yksi näiden materiaalien keskeisistä materiaaleista, joten annan esimerkin:

Ilta. Kiirehdi kotiin kotisivullasi. Maito kulkee pois. Lentäminen "epäilyttävän jonkinlainen" kuulet osoitteeseesi "Hei, sinä, [veistetty sensuuri]. Et mene tänne, lumi on osuma! ".

Mitä aiot tehdä? Vaihtoehdot voivat olla paljon. Joku tietää suhdetta, joku pelkää ja nopeuttaa askelta, joku siirtää jotain vastauksena. Ajattelemme kuitenkin, mikä tässä tapauksessa on puhdas käyttäytymisstrategia?

Henkilö tuntematon sinulle, jotain huutaa sinulle kadulla. Sinulla on oma liiketoiminta, josta todella menet. Tekstin tuomitseminen, positiiviset hyödyt, jotka välittävät tämän henkilön kanssa, ovat epätodennäköisiä. Looginen johtopäätös: Mene rauhallisesti asioillesi. Kiinnittän huomiota siihen, että se on "rauhallinen" ilman varjoa negatiiviset tunteetja terveellinen välinpitämättömyys siihen, mitä tapahtuu. Kuinka monta ihmistä tulee niin? Oletan, että ylivoimainen vähemmistö. Miksi?

Koska useimmilla ihmisillä on koko alitajunta-strategioita, jotka on sidottu alempiin kerroksiin itsestään säilytykseen, erityisesti ne voivat olla: "Vastaa aina epämiellyttävyyteen rudiness", "Jos joku sanoo Nastyness, sinun täytyy ajaa", " Joku Grubit - Sinun täytyy täyttää kasvonsa ", jos joku on töykeä, se tarkoittaa, että on olemassa vaara" ja vastaavat eri muunnelmissa. Tietenkään kaikki eivät ottavat aktiivisia toimia, mutta emotionaalisesti se osallistuu lähes kaikkiin. Ja tämä on jamb.

Puhdas strategiat ovat aina emotionaalisesti neutraaleja tai positiivisia, ja se asetetaan aivoihin, se on vain käyttää sitä.

Voit lukea vähän puhtaista strategioista muistiinpanoissa "Miksi tarkalleen puhtaat strategiat?" ja "talo, hopkins ja niin edelleen".

Strategiat 1. Termin "strategia": a) Määritelmä Kreikan sana "Strategia", eli "sotilaallinen johtaja", "tiede, sotatarvike", "julkisen, poliittisen taistelun" taidetta ".b ) yksityiskohtainen suunnitelma tavoitteen saavuttamiseksi tai kannattavan

Tutkimusstrategiat menevät täysin erilaiseen laadun tasoon, jos ajattelet ja valitset toimintastrategian. Spriikki on yleinen suunnitelma. Tämä on yhteinen linja todelliset olosuhteet. Nämä ovat tavoitteita, määräajat, arvaamattomuus ja monikannallinen kirjanpito ... Tämä on pulssin tunne