opi fyrir 16 árum, 9 mánuðum Fjöldi lestra: 994

MiniMax?

Ég er búinn að vera að reyna að gera AI vél fyrir TicTacToe með MiniMax, en ég er einfaldlega ekki að átta mig á því hvernig maður gerir þetta, er búinn að lesa allt sem ég finn um þetta á netinu og skil hvernig þetta virkar, en átta mig ekki á því hvernig skal gera þetta í c++.

Einhver sem er vel að sér í þessu og getur hjálpað?
Einhver sem hefur gert TicTacToe með MiniMax algrími?

VeryMuch fyrir 16 árum, 9 mánuðum

Ertu í H.Í.? ;)

Það er mjög langt síðan ég gerði þetta forrit, þú þarft að passa að minmax standist rétt á, og að hafa ólík gildi fyrir mismunandi stöður. Mjög stóran bónus fyrir raunverulega góðar stöður, en smotterí fyrir annað sem er hvorki né.

En líkast til hjálpar þetta ekki mikið. Mesta villu hættan er í að klúðra hlutum eins og min og max standast ekki á, að þú sért með max þegar þú ættir að vera með min, og svona dót. Þetta er svona debugging sem er eiginlega ekki hægt að hjálpa með í gegn um svona texta.

Hinsvegar ef þú skilur ekki út á hvað minmax gengur þá þarftu að lesa betur um algríminn. En ég veit að þú ert líklega undir tímapressu, en besta ráðið við því er að reyna að slaka á og halda haus, og skoða þetta í rólegheitunum ( og farðu varlega í kaffið! ;) ).

Fyrra álit

opi fyrir 16 árum, 9 mánuðum

Nei, reyndar er ég bara framhaldskóla áhugamaður um forritun, sem er ný búinn að uppgötva undrið C++, en ég stefni á að læra stærðfræði/forritun í H.Í eftir menntó.

Vandamálið er eiginlega bara að ég átta mig ekki á því hvernig ég á að gera þennan kóða, er þetta ekki rétt hugmynd af algríminu?

minmax(staða leiksins) {
   n = mögulegir_leikir(staða);
   if(n!=0) {
     for(i=0;i<n;i++) {
        skoða mögulegann leik nr "i"
        minmax(nýja staða leiksins);
        kannastöðu(staða leiksins)
        if(staða leiksins er betri en besta staða)
           besta staða = nýja staða;
        fara til baka um einn leik og endurtaka
     }
   }
}

Bara vandamálið er að ég skil ekki hvernig hún á að ákvarða hvort einhver leikur sé betri en hinn og hvernig á að gefa hverri stöðu gildi til að reikna það út.

Fyrra álit

VeryMuch fyrir 16 árum, 9 mánuðum

Frábært að þú skulir vera að pæla í þessu. Þetta er rauninni nokkuð kúl verkefnið þegar það er farið að virka. Svona þegar maður er farinn að geta spilað við forritið sitt, og það er janvel að valta yfir mann. ;)

Eins og ég man þetta þá bjó maður til stöðuna sem object eða bara borðið sjálft og gerði það að klasa. Svo voru hinar og þessar að gerðir sem hægt var að gera við það, skv leikreglunum.

Fyrst er bara byrjunarstaða og hvítur á að gera, hann skoðar alla mögulega leiki, og út kemur nýtt ‘Borð’ í hvert skipti, og matsfallið gefur Borðinu gildi eftir því hvor á leik. Og þannig byggir leikmaðurinn leikja tré, sem er eins djúpt og þú stillir leitina á að vera. Verður fljótt þungt að skoða alla mögulega leiki þegar þú kemur niður á dýpi. Og þá er oft gripið til Alpha beta pruning, þar sem hætt er við leit ef góður leikur ef fundinn ( eða eitthvað á þá leið ). Þú getur stillt leitina á að leita X djúpt, og skipta svo yfir í alpha-beta leit, og fara Y dýpra. Getur hraðað leitinni mikið, þó hún verði ekki óskeikul og tölvunni gæti sést yfir mjög góða leiki í alpha-beta… en ámóti kemur að þú ert þegar kominn á töluvert dýpi með minmax.

S.s.
Obect Board ( með functions eins og að finna löglega leiki, og leika þeim og fá nýjá útgáfu af Board… og svona allskyns útfærslur eins og þér þykir sniðugt. )

Valuation gæti verið í Board, eða Board gæti verið sent í valuation function.

Value stöðunnar gæti líka verið breyta í Board hlutnum sem væri reiknaður um leið og hann er skapaður.

Og allskonar allskonar, allt svona sem þú ættir að finna smámsaman út.

En skoðaðu algorithman sjálfann, og farðu í gegn um hann skref af skrefi ef það er hann sem þú ert ekki að ná. Það er í raun eina leiðin til að skilja algórithma… bara að leggjast yfir þá og prufa jafnvel að reikna eitt dæmi út á blaði og svona, bara allar leiðir. ;)

Þú átt eftir að finna út úr þessu. Ég er viss um það. Og það er líka ekki síður partur af því að læra að forrita. ( Að finna út úr hlutum. ) ;)

Fyrra álit

davido fyrir 16 árum, 9 mánuðum

Hvað er það nákvæmlega sem þú skilur ekki varðandi útfærsluna?

Ef það er t.d. hvernig þú byggir upp ákvarðanatréð, þá er það c.a. svona:

class Node {
  Node *pChild1;   // Bendir á fyrsta barnið.
                                  // Það bendir síðan á barn 2 (systkyni), sem bendir svo á barn 3 o.s.frv.
  Node *pSibling; // Næsta systkyni
  int iScore; // Stig sem fást fyrir að leika þennan leik
  int iMove;    // Á hvaða reit var leikið (0-8)
  /* Frekari upplýsingar sem þú vilt geyma... */
  /* Aðgerðir sem þú vilt geta framkvæmt, svo sem að bæta við systkyni og bæta við barni... */
}
Node *Tree = new Node;

Þetta er sem sagt einfalt tré sem lítur ca. svona út:

Tree
     |
     Child 1 - Child 2 - Child 3 - ... - Child 9
                 |                 |
                 |                 Child 1 - Child 2 - ... - Child 8
                 Child 1 - Child 2 - Child 3 - ... - Child 8
                             |
                             ...

Þar sem borðið er ekki nema 3x3, þá eru bara 9 mögulegir leikir í fyrsta leik (ef tölvan byrjar). Í öðrum leik eru þá 8 mögulegir leikir (fyrir hvern af þessum 9), síðan 7 o.s.frv.

Ef þú síðan lætur hverja grein í trénu innihalda þann leik sem myndaði greinina, þá þarftu ekki að mynda tréð nema einu sinni og getur síðan prjónað við það eftir því sem líður á leikinn (nema þú myndir allt tréð strax, sem ég veit ekki hvort er raunhæft. Það má vel vera að það sé hægt með svona lítinn leik).

Skemmtileg viðbót við þetta er síðan að láta forritið smám saman læra þá leiki sem leiða til vinnings og geyma í e-s konar gagnagrunni. Smám saman verður þá forritið ósigrandi :)

Vona að ég hafi hitt á rétt atriði sem þú vissir ekki - annars var þetta allt víst til lítils.

Eitt er samt víst - nú fer ég heim að gera XogO leik :D

0100100100100000011000010110110100100000010001000110000101110110011010010110010000100001

Fyrra álit

Forritun

Forritun

Ofurhugar

Stjórnendur

Hverjir eru inni

Korkar - C++

MiniMax?

Dýr

Dægurmál

Fræði

Leikir

Lífið

Lífsstíll

Margmiðlun

Menning

Skjár

Sport

Tónlist

Tækni

Vélar

Hugi