Sukurti AI algoritmą iššūkiui „Tic-Tac-Toe“

Dalyvaudamas „freeCodeCamp“ programoje, aš buvau pakviestas kurti „Tic-Tac-Toe“ interneto programą. Tai buvo tikras malonumas.

Programoje yra pagrindinis kompiuterio grotuvas. Tai gali optimizuoti bet kokią situaciją ant „Tic-Tac-Toe“ lentos. Rezultatas mane nustebino.

Net ir tokiame paprastame žaidime kompiuterio grotuvas išmokė mane naujų žingsnių. Kalbant apie mano parašytą kodą, jis yra šiek tiek unikalus ir įdomus tyrinėti.

Pasižiūrėk

Spustelėkite šią nuorodą ir pasirinkite žaisti prieš kompiuterį. Aš jums iššūkį laimėti . Galite pastebėti ... kad negalite.

Vis dėlto, jei esate sunkus gynyboje, galite sužinoti, kad kompiuteris taip pat negali laimėti. Iš patirties sužinojau, kad „Tic-Tac-Toe“ turi paprastą strategiją „ neprarasti “.

Tai reiškia, kad jei pavyksta pasiekti lygų rezultatą, jūs pasirenkate teisingus gynybinius sprendimus. Kompiuteris vis tiek optimizuoja savo judesius. Taigi geriausias rezultatas, kurį jis gali pasiekti prieš tokį žaidėją kaip jūs, gali būti lygus.

Pagrindiniai sprendimo žingsniai

1. lentos duomenų struktūra

_gameBoard: [[“”, “”, “”],[“”, “”, “”],[“”, “”, “”]]

Lentos masyve yra 3 masyvai, kiekvienas iš jų reiškia eilutę.

Kiekvienoje eilutės masyve yra 3 simbolių arba eilutės elementai.

Šie elementai yra arba:

  • „“ Kaip tuščia eilutė, žyminti tuščią langelį
  • „X“ reiškia X grotuvą
  • „O“ reiškia O žaidėją

2. „getResult“ funkcija

Prasideda 59 linijoje

Bet kurioje valstybėje valdyba bus vienoje iš šių galimų valstybių:

  • Nebaigtas
  • laimėjo X žaidėjas
  • Nugalėjo žaidėjas O
  • ar kaklaraištis

getResultFunkcija gauna stalo masyvas, kartojasi per visas eilutes, per visus stulpelius ir abiejuose įstrižainių. Jis tikrina simbolių seką. Tada tai leidžia mums žinoti dabartinę šios valdybos būklę.

3. „getBestMove“ funkcija

Čia pasidaro sunkiau. Kai lenta tuščia, labai sunku nustatyti geriausią įmanomą žingsnį. Pažvelkite į šią lentą.

Kuris yra geriausias įmanomas žingsnis?

Kai lenta bus apgyvendinta, mūsų akyse pasirodys geriausias įmanomas žingsnis.

Panaudokime šią užpildytą lentą kaip atspirties tašką. Leidžiame nuspręsti, kad kitas žingsnis yra mūsų, o mūsų simbolis yra „X“.

Pabandykime nustatyti geriausią įmanomą žingsnį naudodami jau turimus įrankius. Yra 3 tušti langeliai, atitinkantys 3 galimus judesius. Leidžia patikrinti kiekvienos iš šių parinkčių rezultatą.

Tai galime padaryti kartodami galimus judesius ir kiekvienam iš jų:

  • Sukurkite naują lentą
  • Pridėkite mūsų simbolį į atitinkamą tuščią langelį
  • Siųskite šią lentą į getResultfunkciją

Iš 3 lentų, esančių aukščiau esančiame paveikslėlyje, kai mes siunčiame antrąją lentą į getResult funkciją, gausime savo trofėjų.

Susitelkite į kitus esminius veiksmus:

  1. Turime įvertinti galimus judesius, kad galėtume juos palyginti. Nuspręskime, kad jei ėjimas duos laimėtą lentą, mes ją įvertinsime 1. Jei praras pralaimėtą lentą, ji gaus -1 balą. Lygiosios gaus 0 balų.
  2. 2 perkėlimas gaus 1 balą. Kai rasime judesį, pažymėtą 1, galime nepaisyti visų kitų galimų ėjimų. Nėra kito geresnio galimo žingsnio, kaip tikra pergalė.
  3. Bet supratimo sumetimais, kaip mes įvertintume 1 ar 3 judesius ar bet kokį kitą judesį su nebaigtu rezultatu?

Susitelkime ties 3 judesiu. Sprendimas yra rekursiškai nusiųsti atitinkamą lentą į getBestMovefunkciją.

Galbūt galvoji: „Bet palauk! Mūsų varžovas žaidžia kitą žingsnį “. Teisingai. Sužinokime, kokį pažymį mūsų varžovas gauna už geriausią būsimą žingsnį.

Mūsų varžovas turi tik du galimus ėjimus:

3–1 žingsnis laimės žaidimą mūsų priešininko naudai. Kadangi mes naudojame tą pačią getBestMovefunkciją, „Perkelti 3–1“ įvertinimas bus 1.

Tai gali būti šiek tiek painu, nes tiek mūsų pergalė, tiek pralaimėjimas įvertins 1 balais. Turime prisiminti, kad šis skambutis priklauso mūsų oponentui, o jo pergalė yra mūsų pralaimėjimas ir atvirkščiai.

Turime paneigti bet kokį pažymį, kurį getBestMovefunkcija grąžino getBestMovefunkcijai.

3–1 perkėlimas gauna 1 balą. getBestMoveFunkcija grąžina 1 balą, o 3 perkėlimą galime įvertinti -1.

Tokiu būdu getBestMovefunkcija toliau tyrinėja judesius ir tolesnius judesius. Šis procesas tęsis iki:

  1. Jis randa judesį, pažymėtą 1, tokiu atveju jis nedelsdamas grąžins ėjimą
  2. Tai tęsis tol, kol kiekvienas galimas ėjimas turės pažymį. Galimi ėjimai (su 0 ir -1 laipsniais) saugomi masyve
  3. Tada masyvas bus:

    [a] atsitiktinių imčių

    [b] rūšiuojami nuo aukšto iki žemiausio

    [c] bus grąžintas pirmasis elementas

Šie veiksmai garantuoja, kad:

  1. Pralaimėjusio žingsnio bus išvengta, nebent tai bus vienintelė galimybė
  2. Kompiuterio grotuvas gali žaisti įvairiai

Pabaigos pastabos:

  1. Esama rimtų pagrįstų susirūpinimų dėl dirbtinio intelekto (AI) keliamos rizikos.

    Leidžia naudoti dirbtinį intelektą visų labui.

    Geriausia įmanoma dirbtinio intelekto programinė įranga yra ta, kuri gali užkirsti kelią neteisingam AI naudojimui.

  2. Rašydamas programą konsultavausi su Assafu Weinbergu

Žiūrėkite mano kodą „GitHub“.