La ricerca contraddittoria è una ricerca in cui esaminiamo il problema che sorge quando proviamo a pianificare in anticipo rispetto al mondo e altri agenti stanno pianificando contro di noi.
- Negli argomenti precedenti abbiamo studiato le strategie di ricerca associate solo a un singolo agente che mira a trovare la soluzione che spesso si esprime sotto forma di una sequenza di azioni.
- Tuttavia, potrebbero esserci alcune situazioni in cui più di un agente sta cercando la soluzione nello stesso spazio di ricerca e questa situazione di solito si verifica durante il gioco.
- L'ambiente con più di un agente è definito come ambiente multi-agente , in cui ogni agente è avversario di un altro agente e gioca l'uno contro l'altro. Ciascun agente deve considerare l'azione di un altro agente e l'effetto di tale azione sulle proprie prestazioni.
- COSÌ, Le ricerche in cui due o più giocatori con obiettivi contrastanti cercano di esplorare lo stesso spazio di ricerca per trovare la soluzione sono chiamate ricerche contraddittorie, spesso note come Giochi .
- I giochi sono modellati come un problema di ricerca e una funzione di valutazione euristica, e questi sono i due fattori principali che aiutano a modellare e risolvere i giochi nell'intelligenza artificiale.
Tipi di giochi nell'intelligenza artificiale:
| Deterministico | Mosse casuali | |
|---|---|---|
| Informazioni perfette | Scacchi, Dama, vai, Otello | Backgammon, monopolio |
| Informazioni imperfette | Corazzate, cieche, tris | Bridge, poker, scarabeo, guerra nucleare |
Esempio: Backgammon, Monopoli, Poker, ecc.
Nota: in questo argomento discuteremo dei giochi deterministici, dell'ambiente completamente osservabile, della somma zero e del luogo in cui ciascun agente agisce in modo alternativo.
Gioco a somma zero
- I giochi a somma zero sono ricerche contraddittorie che implicano pura competizione.
- Nel gioco a somma zero il guadagno o la perdita di utilità di ciascun agente è esattamente bilanciato dalle perdite o dai guadagni di utilità di un altro agente.
- Un giocatore del gioco cerca di massimizzare un singolo valore, mentre l'altro giocatore cerca di minimizzarlo.
- Ogni mossa di un giocatore nel gioco è chiamata ply.
- Gli scacchi e il tris sono esempi di giochi a somma zero.
Gioco a somma zero: pensiero incorporato
Il gioco a somma zero implica un pensiero incorporato in cui un agente o giocatore cerca di capire:
livecricket.is
- Cosa fare.
- Come decidere il trasloco
- Deve pensare anche al suo avversario
- Anche l'avversario pensa a cosa fare
Ciascuno dei giocatori sta cercando di scoprire la risposta del suo avversario alle proprie azioni. Ciò richiede un pensiero incorporato o un ragionamento all'indietro per risolvere i problemi di gioco nell'intelligenza artificiale.
Formalizzazione del problema:
Un gioco può essere definito come un tipo di ricerca nell'intelligenza artificiale che può essere formalizzato nei seguenti elementi:
Albero del gioco:
Un albero di gioco è un albero in cui i nodi dell'albero sono gli stati del gioco e i bordi dell'albero sono le mosse dei giocatori. L'albero del gioco coinvolge lo stato iniziale, la funzione delle azioni e la funzione del risultato.
Esempio: albero del gioco Tic-Tac-Toe:
prepararsi per il test mockito
La figura seguente mostra parte dell'albero del gioco del tris. Di seguito sono riportati alcuni punti chiave del gioco:
- Ci sono due giocatori MAX e MIN.
- I giocatori hanno un turno alternativo e iniziano con MAX.
- MAX massimizza il risultato dell'albero di gioco
- MIN minimizza il risultato.
Esempio Spiegazione:
- Dallo stato iniziale, MAX ha 9 mosse possibili poiché inizia per primo. MAX posto x e MIN posto o, ed entrambi i giocatori giocano alternativamente fino a raggiungere un nodo foglia in cui un giocatore ne ha tre di fila o tutti i quadrati sono pieni.
- Entrambi i giocatori calcoleranno ciascun nodo, minimax, il valore minimax che è la migliore utilità ottenibile contro un avversario ottimale.
- Supponiamo che entrambi i giocatori siano ben consapevoli del tris e giochino la giocata migliore. Ogni giocatore fa del suo meglio per impedire che un altro vinca. MIN agisce contro Max nel gioco.
- Quindi nell'albero del gioco abbiamo un livello Max, uno livello MIN e ogni livello è chiamato come Piega . Max piazza x, poi MIN mette o per impedire a Max di vincere, e il gioco continua fino al nodo terminale.
- In questo caso vince MIN, vince MAX o è un pareggio. Questo albero di gioco è l'intero spazio di ricerca delle possibilità in cui MIN e MAX giocano a tris e si alternano a turno.
Quindi la ricerca contraddittoria per la procedura minimax funziona come segue:
stringbuilder
- Lo scopo è trovare la strategia ottimale affinché MAX vinca la partita.
- Segue l'approccio della ricerca Depth-first.
- Nell'albero del gioco, il nodo foglia ottimale potrebbe apparire a qualsiasi profondità dell'albero.
- Propaga i valori minimax fino all'albero finché non viene scoperto il nodo terminale.
In un dato albero di gioco, la strategia ottimale può essere determinata dal valore minimax di ciascun nodo, che può essere scritto come MINIMAX(n). MAX preferisce passare ad uno stato di valore massimo e MIN preferisce spostarsi ad uno stato di valore minimo, quindi:
