Intel·ligència artificial del joc de taula: l'algorisme Minimax: 8 passos

2024 Autora: John Day | [email protected]. Última modificació: 2024-01-30 08:13

Us heu preguntat mai com es fabriquen els equips contra els quals jugueu als escacs o a les dames? No busqueu més enllà d’aquest Manual d’instruccions, ja que us mostrarà com fer una intel·ligència artificial (IA) senzilla però eficaç mitjançant l’algorisme Minimax. En utilitzar l’algorisme Minimax, la IA realitza moviments ben planificats i pensats (o almenys imita un procés de pensament). Ara, només podria donar-vos el codi de la IA que he creat, però això no seria divertit. Explicaré la lògica que hi ha darrere de les decisions de l’ordinador.

En aquest instructiu, us guiaré pels passos sobre com fer una IA per a Othello (AKA Reversi) en python. Hauríeu de tenir una comprensió intermèdia de com codificar en python abans d’abordar aquest projecte. A continuació, es mostren alguns bons llocs web per preparar-vos per a aquest instructiu: w3schools o learnpython. Al final d’aquest instructiu, hauríeu de tenir una IA que faci moviments calculats i hauria de ser capaç de derrotar a la majoria dels humans.

Com que aquest Instructable s’ocuparà principalment de com fer una IA, no explicaré com dissenyar un joc en python. En lloc d'això, donaré el codi del joc on un ésser humà pot jugar contra un altre ésser humà i el modificaré perquè pugui jugar a un joc en què un ésser humà jugui contra la IA.

Vaig aprendre a crear aquesta IA mitjançant un programa d’estiu a Columbia SHAPE. M'ho vaig passar bé, així que mireu el seu lloc web per veure si us interessa.

Ara que ja hem deixat la logística, comencem a codificar!

(Vaig posar un parell de notes a les imatges, així que assegureu-vos de mirar-les)

Subministraments

Això és fàcil:

1) Ordinador amb un entorn python com Spyder o IDLE

2) Descarregueu els fitxers del joc Othello del meu GitHub

3) El vostre cervell amb paciència instal·lada

Pas 1: baixeu els fitxers necessaris

Quan accediu al meu GitHub, hauríeu de veure 5 fitxers. Baixeu-ne les 5 i col·loqueu-les a la mateixa carpeta. Abans d’executar el joc, obriu tots els fitxers de l’entorn spyder.

Això és el que fan els fitxers:

1) othello_gui.py aquest fitxer crea el tauler de joc perquè els jugadors puguin jugar (ja sigui humà o ordinador)

2) othello_game.py aquest fitxer reprodueix dos ordinadors l'un contra l'altre sense el tauler de joc i només mostra la puntuació i les posicions de moviment

3) ai_template.py aquí és on posareu tot el vostre codi per crear la vostra IA

4) randy_ai.py es tracta d'una IA prefabricada que tria els seus moviments a l'atzar

5) othello_shared.py un munt de funcions prefabricades que podeu utilitzar per fer la vostra IA, com ara comprovar si hi ha moviments disponibles, la puntuació o l'estat del tauler.

6) Els altres tres fitxers: Puma.py, erika_5.py i nathan.py, fets per mi, Erika i Nathan respectivament del programa SHAPE, són tres IA diferents amb codis únics

Pas 2: Com obrir i reproduir Python Othello

Quan tingueu tots els fitxers oberts, a l'extrem inferior dret de la pantalla, escriviu "executa othello_gui.py" i premeu Intro a la consola IPython. O bé al terminal Mac, escriviu "python othello_gui.py" (per descomptat, després d'haver estat a la carpeta correcta). A continuació, apareixerà un tauler a la pantalla. Aquest mode és el mode humà vs humà. La llum passa en segon lloc i la foscor primer. Mireu el meu vídeo si esteu confós. iA la part superior, hi ha la puntuació de cada mosaic de color. Per jugar, feu clic a un espai de moviment vàlid per col·locar-hi una fitxa i, a continuació, doneu l'ordinador al vostre oponent que farà el mateix i repetirà.

Si no sabeu com jugar a Othello, llegiu aquestes regles del lloc web ultra boards:

El negre sempre es mou primer. Es fa un moviment col·locant un disc del color del jugador al tauler en una posició que "flanci" un o més dels discs de l'oponent. Un disc o una fila de discos es desborda quan està envoltat pels extrems per discos de color oposat. Un disc pot superar qualsevol nombre de discos en una o més files en qualsevol direcció (horitzontal, vertical, diagonal) … (acabar de llegir al seu lloc web)

La diferència entre el joc original i aquest joc de pitó és que quan no queden moviments vàlids per a un jugador, el joc acaba

Ara que podeu jugar amb un amic, fem una IA amb la qual pugueu jugar.

Pas 3: Algorisme Minimax: generació d'escenaris

Abans de parlar de com escriure això en codi, repassem la lògica que hi ha al darrere. L’algoritme minimax és un algorisme de presa de decisions i de seguiment posterior i s’utilitza normalment en jocs basats en torns de dos jugadors. L'objectiu d'aquesta IA és trobar el següent millor moviment i els següents millors moviments fins que guanyi el joc.

Ara bé, com determinaria l'algorisme quin moviment és el millor? Atureu-vos i penseu com escolliríeu el següent moviment. La majoria de la gent escolliria la jugada que li donaria més punts, oi? O si estiguessin pensant endavant, escollirien el moviment que permetria establir una situació en què podrien guanyar encara més punts. Aquesta última forma de pensar és la forma en què pensa l’algorisme Minimax. Preveu totes les configuracions futures del tauler i fa el pas que portaria a la majoria de punts.

Vaig anomenar-ho algorisme de retrocés, perquè comença creant i avaluant tots els futurs estats de la placa amb els seus valors associats. Això significa que l'algoritme jugarà el joc tants com sigui necessari (fent els moviments per a ell mateix i per a l'adversari) fins que hagi jugat tots els escenaris del joc. Per fer un seguiment de tots els estats de la placa (escenaris), podem dibuixar un arbre (mireu a les imatges). L’arbre de la imatge superior és un exemple senzill d’un joc de Connect 4. Totes les configuracions de taulers s’anomenen estat de tauler i el seu lloc a l’arbre es diu node. Tots els nodes de la part inferior de l’arbre són els estats finals del tauler després de fer tots els moviments. Evidentment, alguns estats del tauler són millors per a un jugador que per a l’altre. Per tant, ara hem de fer que la IA triï a quin estat de la junta vol arribar.

Pas 4: Minimax: avaluació de les configuracions de la placa

Per donar valors als estats del tauler, hem d'aprendre les estratègies del joc que estem jugant: en aquest cas, les estratègies d'Otelo. Com que aquest joc és una batalla per capgirar l'oponent i els vostres discos, les millors posicions del disc són les que són estables i no es poden capgirar. La cantonada, per exemple, és el lloc on es col·loca un disc no es pot canviar a l’altre color. Per tant, aquest lloc seria extremadament valuós. Altres bones posicions inclouen els laterals del tauler que us permetrien agafar moltes pedres. Hi ha més estratègies en aquest lloc web.

Ara podem assignar valors a les posicions de cada junta estatal de la junta. Quan una posició està ocupada per la peça de la IA, donareu un nombre determinat de punts en funció de la posició. Per exemple, si es tracta d'un tauler on la peça de la IA es troba a la cantonada, podeu donar un bo de 50 punts, però si es trobés en un lloc desfavorable, la peça pot tenir un valor de 0. Després de tenir en compte tots els valors de a les posicions, assigneu un valor a l’estat de la junta. Per exemple, si la IA té una peça a la cantonada, l'estat del tauler pot tenir una puntuació de 50, mentre que un altre estat de tauler amb la peça de la IA al centre té una puntuació de 10.

Hi ha moltes maneres de fer-ho, i tinc tres heurístiques diferents per avaluar les peces del tauler. Us animo a fer el vostre propi tipus d’heurística. Vaig penjar tres IA diferents al meu github de tres fabricants diferents, amb tres heurístiques diferents: Puma.py, erika5.py, nathanh.py.

Pas 5: Algorisme Minimax: triar el millor moviment

Ara seria bo que l’IA només pogués triar tots els moviments per arribar a l’estat del tauler amb la puntuació més alta. Però recordeu que la IA també escollia els moviments de l’oponent quan generava tots els estats del tauler i, si l’oponent és intel·ligent, no permetrà que la IA aconsegueixi la puntuació més alta del tauler. En canvi, un oponent intel·ligent faria el moviment per fer que la IA passés a l’estat més baix del tauler. A l'algorisme, anomenem als dos jugadors un jugador que maximitza i un minimitza. L’IA seria el màxim jugador, ja que vol obtenir el màxim de punts per si mateix. L’oponent seria el jugador que minimitzaria, ja que l’oponent intenta fer el moviment on la IA obté menys punts.

Un cop es generen tots els estats de la placa i s’han assignat valors a les taules, l’algorisme comença a comparar els estats de la placa. A les imatges, vaig crear un arbre per representar com l’algorisme escolliria els seus moviments. Cada divisió a les branques és un moviment diferent que pot jugar l'AI o l'adversari. A l'esquerra de les files de nodes, vaig escriure si el reproductor de maximització o minimització està en marxa. La fila inferior inclou tots els estats del tauler amb els seus valors. Dins de cadascun d’aquests nodes hi ha un número i aquestes són les puntuacions que assignem a cadascun dels taulers: com més altes siguin, millor tindrà la IA.

Definicions: node pare: un node que resulta o crea nodes a sota seu; l'origen dels nodes fills: els nodes que provenen del mateix node pare

Els nodes buits representen el moviment que farà la IA per arribar al millor estat del tauler. Comença comparant els fills del node més esquerre: 10, -3, 5. Com que el jugador maximitzador faria el moviment, escolliria el moviment que li donaria més punts: 10. Per tant, seleccionem i guardem aquest mou-te amb la partitura del tauler i escriu-la al node pare. Ara que 10 es troba al node pare, ara és el torn de minimització dels jugadors. Tanmateix, el node amb què compararíem 10 és buit, de manera que hem d’avaluar primer aquest node abans que el jugador que minimitzi pugui triar. De manera que tornem al torn del màxim jugador i comparem els fills del node adjacent: 8, -2. Maximitzant triarà 8 i ho escriurem al node pare buit. Ara que l'algorisme ha acabat d'emplenar els espais buits per als fills d'un node que hi ha a sobre, el jugador que minimitza pot comparar els nens (10 i 8) i triar 8. L'algoritme repeteix aquest procés fins que s'ompli tot l'arbre. Al final d'aquest exemple, tenim la puntuació 8. Aquest és l'estat de tauler més alt que pot jugar la IA suposant que l'adversari juga de manera òptima. Per tant, la IA triarà el primer moviment que condueix a l’estat del tauler 8 i, si l’oponent juga de manera òptima, la IA hauria de jugar tots els moviments per arribar a l’estat 8. del tauler (seguiu les notes de les meves imatges)

Sé que va ser molt. Si sou d'aquests tipus que necessiten que algú us parli per entendre alguna cosa, aquí teniu un parell de vídeos que he vist per ajudar-me a comprendre la idea que hi ha darrere d'això: 1, 2, 3.

Pas 6: Algorisme Minimax: pseudocodi

Després d’entendre la lògica que hi ha darrere de l’algoritme minimax, mireu aquest pseudocodi (les funcions que són universals per a tots els codis) a la wikipedia:

La funció minimax (node, profunditat, maximizingPlayer) és

si la profunditat = 0 o el node és un node terminal, llavors

retorna el valor heurístic del node

si maximizingPlayer llavors

valor: = −∞

per a cada fill del node do

valor: = màxim (valor, mínimax (fill, profunditat - 1, FALS))

valor de retorn

else (* reproductor minimitzant *)

valor: = + ∞

per a cada fill del node do

valor: = mínim (valor, mínimax (fill, profunditat - 1, TRUE))

valor de retorn

Es tracta d’una funció recursiva, és a dir, que s’anomena una vegada i una altra fins que arriba a un punt d’aturada. En primer lloc, la funció inclou tres valors, el node, la profunditat i el torn del qual és. El valor del node és el lloc on voleu que el programa comenci a cercar. La profunditat és fins a quin punt voleu cercar el programa. Per exemple, a l'exemple del meu arbre té una profunditat de 3, perquè ha cercat tots els estats del tauler després de 3 moviments. Per descomptat, ens agradaria que la IA comprovés tots els estats del tauler i triés una victòria guanyadora, però a la majoria de jocs on hi ha milers, si no milions, de configuracions de taulers, el portàtil de casa no podrà processar totes aquestes configuracions. Per tant, limitem la profunditat de cerca de la IA i la fem passar al millor estat del tauler.

Aquest pseudocodi reprodueix el procés que he explicat en els dos passos anteriors. Ara fem un pas més i encertem en el codi Python.

Pas 7: Feu la vostra IA amb Ai_template.py

Abans de fer una ullada al meu codi Minimax AI, intenteu fer la vostra pròpia IA amb el fitxer ai_template.py i el pseudo-codi del qual vam parlar al darrer pas. Hi ha dues funcions a la plantilla ai anomenades: def minimax_min_node (tauler, color) i def minimax_max_node (tauler, color). En lloc de fer que la funció minimax es cridi recursivament, tenim dues funcions diferents, que es diuen mútuament. Per crear la heurística per avaluar els estats del tauler, haureu de crear la vostra pròpia funció. Hi ha funcions premade al fitxer othello_shared.py que podeu utilitzar per crear la vostra IA.

Un cop tingueu la vostra IA, proveu d'executar-la contra, randy_ai.py. Per executar dos ais l'un contra l'altre, escriviu "python othello_gui.py (inseriu el nom del fitxer ai).py (inseriu el nom del fitxer).py" al terminal del mac o escriviu "run othello_gui.py (inseriu el nom del fitxer ai).py (inseriu el nom del fitxer).py "i assegureu-vos que esteu al directori correcte. A més, mireu el meu vídeo per veure els passos exactes.

Pas 8: és hora de lluitar contra la IA

Ara obtingueu un munt de amics del vostre ordinador i feu-los dissenyar la seva pròpia IA. Aleshores podeu fer una competició i fer que el vostre duc d’intel·ligència artificial pugui sortir. Amb sort, fins i tot si no podíeu construir la vostra pròpia IA, podríeu entendre com funciona l’algoritme minimax. Si teniu cap pregunta, no dubteu a publicar qualsevol pregunta als comentaris següents.