La cerca adversària és una recerca, on examinem el problema que sorgeix quan intentem planificar per davant del món i altres agents estan planejant contra nosaltres.

• En temes anteriors, hem estudiat les estratègies de cerca que només s'associen a un sol agent que pretén trobar la solució que sovint s'expressa en forma d'una seqüència d'accions.
• Però, pot haver-hi algunes situacions en què més d'un agent estigui cercant la solució al mateix espai de cerca, i aquesta situació sol passar durant el joc.
• L'entorn amb més d'un agent s'anomena com entorn multiagent , en què cada agent és un oponent d'un altre agent i juga un contra l'altre. Cada agent ha de considerar l'acció d'un altre agent i l'efecte d'aquesta acció en el seu rendiment.
• Tan, Les cerques en què dos o més jugadors amb objectius en conflicte intenten explorar el mateix espai de cerca per trobar la solució, s'anomenen cerques adversàries, sovint conegudes com a Jocs. .
• Els jocs es modelen com un problema de cerca i una funció d'avaluació heurística, i aquests són els dos factors principals que ajuden a modelar i resoldre jocs en IA.

Tipus de jocs en IA:

Informació perfecta:Un joc amb la informació perfecta és aquell en què els agents poden mirar el tauler complet. Els agents tenen tota la informació sobre el joc i també es poden veure els moviments. Alguns exemples són els escacs, les dames, el Go, etc.Informació imperfecta:Si en un joc els agents no tenen tota la informació sobre el joc i no són conscients del que està passant, aquest tipus de jocs s'anomenen el joc amb informació imperfecta, com ara tic-tac-toe, Battleship, blind, Bridge, etc.Jocs deterministes:Els jocs deterministes són aquells jocs que segueixen un patró estricte i un conjunt de regles per als jocs, i no hi ha aleatorietat associada amb ells. Alguns exemples són els escacs, les dames, Go, tic-tac-toe, etc.Jocs no deterministes:No deterministes són aquells jocs que tenen diversos esdeveniments impredictibles i tenen un factor d'atzar o sort. Aquest factor d'atzar o sort s'introdueix mitjançant daus o cartes. Són aleatoris i cada resposta d'acció no està fixada. Aquests jocs també s'anomenen jocs estocàstics.
Exemple: Backgammon, Monopoly, Poker, etc.

Nota: En aquest tema, parlarem de jocs deterministes, entorn totalment observable, suma zero i on cada agent actua alternativament.

Joc de suma zero

• Els jocs de suma zero són una recerca adversa que implica pura competència.
• En el joc de suma zero, el guany o la pèrdua d'utilitat de cada agent s'equilibra exactament amb les pèrdues o guanys d'utilitat d'un altre agent.
• Un jugador del joc intenta maximitzar un únic valor, mentre que un altre jugador intenta minimitzar-lo.
• Cada moviment d'un jugador en el joc s'anomena capa.
• Els escacs i el tic-tac-toe són exemples d'un joc de suma zero.

Joc de suma zero: pensament incrustat

El joc de suma zero implicava un pensament integrat en el qual un agent o jugador intenta esbrinar:

• Què fer.
• Com decidir el moviment
• També ha de pensar en el seu oponent
• El rival també pensa què ha de fer

Cadascun dels jugadors està intentant esbrinar la resposta del seu oponent a les seves accions. Això requereix un pensament integrat o un raonament cap enrere per resoldre els problemes del joc en IA.

Formalització del problema:

Un joc es pot definir com un tipus de cerca en IA que es pot formalitzar dels següents elements:

Estat inicial:Especifica com es configura el joc al començament.Jugador(s):Especifica quin jugador s'ha mogut a l'espai d'estat.Accions:Retorna el conjunt de moviments legals a l'espai estatal.Resultat(s, a):És el model de transició, que especifica el resultat dels moviments a l'espai d'estats.Prova(s) del terminal:La prova del terminal és certa si el joc s'ha acabat, sinó és falsa en qualsevol cas. L'estat on acaba el joc s'anomena estats terminals.Utilitat(s, p):Una funció d'utilitat dóna el valor numèric final d'un joc que acaba en estats terminals s per al jugador p. També s'anomena funció de pagament. Per als escacs, els resultats són una victòria, una pèrdua o un empat i els seus valors de benefici són +1, 0, ½. I per a tic-tac-toe, els valors d'utilitat són +1, -1 i 0.

Arbre del joc:

Un arbre de joc és un arbre on els nodes de l'arbre són els estats del joc i les vores de l'arbre són els moviments dels jugadors. L'arbre del joc implica l'estat inicial, la funció d'accions i la funció de resultat.

Exemple: arbre del joc Tic-Tac-Toe:

connexions en java

La figura següent mostra part de l'arbre de joc per al joc de tic-tac-toe. A continuació es mostren alguns punts clau del joc:

• Hi ha dos jugadors MAX i MIN.
• Els jugadors tenen un torn alternatiu i comencen amb MAX.
• MAX maximitza el resultat de l'arbre del joc
• MIN minimitza el resultat.

Exemple d'explicació:

• Des de l'estat inicial, MAX té 9 moviments possibles ja que comença primer. MAX col·loca x i MIN col·loca o, i ambdós jugadors juguen alternativament fins que arribem a un node fulla on un jugador té tres seguides o totes les caselles s'omplen.
• Els dos jugadors calcularan cada node, minimax, el valor minimax que és la millor utilitat possible contra un adversari òptim.
• Suposem que els dos jugadors són ben conscients del tic-tac-toe i juguen la millor jugada. Cada jugador està fent tot el possible per evitar que un altre guanyi. MIN està actuant contra Max al joc.
• Així, a l'arbre del joc, tenim una capa de Max, una capa de MIN, i cada capa s'anomena com Ply . Max col·loca x, després MIN posa o per evitar que Max guanyi, i aquest joc continua fins al node terminal.
• En això, MIN guanya, MAX guanya o és un empat. Aquest arbre-joc és tot l'espai de cerca de possibilitats que MIN i MAX estan jugant al tic-tac-toe i fent torns alternativament.

Per tant, la cerca contradictòria del procediment minimax funciona de la següent manera:

• Pretén trobar l'estratègia òptima perquè MAX guanyi el joc.
• Segueix l'enfocament de la cerca en profunditat.
• A l'arbre del joc, el node de fulla òptim podria aparèixer a qualsevol profunditat de l'arbre.
• Propaga els valors minimax fins a l'arbre fins que es descobreixi el node terminal.

En un arbre de joc determinat, l'estratègia òptima es pot determinar a partir del valor mínimmax de cada node, que es pot escriure com MINIMAX(n). MAX prefereix passar a un estat de valor màxim i MIN prefereix passar a un estat de valor mínim llavors: