Samm-sammuline juhend lihtsa male AI loomiseks

Uurime mõningaid põhimõisteid, mis aitavad meil luua lihtsa male AI:

  • käigupõlv
  • juhatuse hindamine
  • minimax
  • ja alfa-beeta pügamine.

Igal sammul täiustame oma algoritmi ühe neist ajaproovitud maleprogrammeerimise tehnikatest. Näitan, kuidas kumbki mõjutab algoritmi mängustiili.

Tehisintellekti algoritmi saate vaadata siin GitHubis.

1. samm: liigutage põlvkonna ja tahvli visualiseerimist

Me kasutame liigutuste genereerimiseks teeki chess.js ja tahvli visualiseerimiseks chessboard.js. Liikumise põlvkonna raamatukogu rakendab põhimõtteliselt kõiki malereegleid. Selle põhjal saame arvutada kõik antud juhatuse oleku kõik juriidilised käigud.

Nende raamatukogude kasutamine aitab meil keskenduda ainult kõige huvitavamale ülesandele: parima käigu leidva algoritmi loomisele.

Alustame funktsiooni loomisega, mis tagastab juhusliku käigu kõigist võimalikest käikudest:

Kuigi see algoritm ei ole eriti kindel maletaja, on see siiski hea lähtepunkt, kuna saame selle vastu tegelikult mängida:

2. samm: positsiooni hindamine

Proovime nüüd mõista, kumb pool on kindlas asendis tugevam. Lihtsaim viis selle saavutamiseks on tahvlil olevate tükkide suhtelise tugevuse lugemine järgmise tabeli abil:

Hindamisfunktsiooniga saame luua algoritmi, mis valib kõrgeima hinnangu andva käigu:

Ainus käegakatsutav täiustus on see, et meie algoritm haarab nüüd tüki, kui see on võimalik.

3. samm: otsige puud Minimaxi abil

Järgmisena loome otsingupuu, kust algoritm saab valida parima käigu. Selleks kasutatakse Minimaxi algoritmi.

Selles algoritmis uuritakse kõigi võimalike käikude rekursiivset puud etteantud sügavusele ja hinnatakse asukohta puu lõpp-lehtedel.

Pärast seda tagastame vanema sõlme kas lapse väikseima või suurima väärtuse, sõltuvalt sellest, kas liikumiseks on see valge või must. (See tähendab, et me püüame igal tasandil tulemust kas minimeerida või maksimeerida.)

Kui minimax on paigas, hakkab meie algoritm mõistma mõnda male põhitaktikat:

Minimax-algoritmi efektiivsus põhineb suuresti otsingusügavusel, mille suudame saavutada. Seda parandame järgmises etapis.

4. samm: alfa-beeta pügamine

Alfa-beeta pügamine on minimax-algoritmi optimeerimismeetod, mis võimaldab meil otsingupuus mõnda haru eirata. See aitab meil minimaxi otsingupuud palju sügavamalt hinnata, kasutades samas ressursse.

Alfa-beeta pügamine põhineb olukorral, kus saame otsingupuu osa hindamise lõpetada, kui leiame käigu, mis viib halvema olukorrani kui varem avastatud käik.

Alfa-beeta pügamine ei mõjuta minimax-algoritmi tulemusi - see muudab selle ainult kiiremaks.

Alfa-beeta algoritm on tõhusam, kui me juhtumisi külastada kõigepealt need teed, mis viivad hea liigub.

Alfa-beeta abil saame minimax-algoritmile märkimisväärse tõuke, nagu on näidatud järgmises näites:

Järgige seda linki, et proovida male AI AI-beeta täiustatud versiooni.

5. samm: täiustatud hindamisfunktsioon

Esmane hindamisfunktsioon on üsna naiivne, kuna loendame ainult tahvlil leiduvat materjali. Selle parandamiseks lisame hindamisele teguri, mis võtab arvesse tükkide positsiooni. Näiteks laua keskel asuv rüütel on parem (kuna sellel on rohkem võimalusi ja on seega aktiivsem) kui laua serval asuv rüütel.

Kasutame veidi kohandatud versiooni tükk-ruudu tabelitest, mida on algselt kirjeldatud male-programmeerimise-wikis.

Järgmise täiustuse abil hakkame hankima algoritmi, mis mängib mõnda tavalist malet, vähemalt tavalise mängija seisukohast:

Järeldused

Isegi lihtsa malemängu algoritmi tugevus on see, et see ei tee rumalaid vigu. Sellest hoolimata puudub sellel endiselt strateegiline arusaam.

Siin kasutusele võetud meetodite abil oleme suutnud programmeerida malet mängiva algoritmi, mis suudab mängida malet. Lõpliku algoritmi „tehisintellekti osa” (välja arvatud liigutuste genereerimine) on vaid 200 koodirida, mis tähendab, et põhimõisteid on üsna lihtne rakendada. Saate vaadata, et lõplik versioon on GitHubis.

Mõned täiendavad parandused, mida saaksime algoritmis teha, oleksid näiteks:

  • käigukorraldus
  • kiirem liigutuste genereerimine
  • ja lõpumänguspetsiifiline hindamine.

Kui soovite rohkem teada saada, vaadake maleprogrammide wiki. See on kasulik ressurss nende siin esitatud põhimõistete kõrvalt uurimiseks.

Täname lugemast!