<jupyter_start><jupyter_text>Intelligenza artificialeI computer non sono macchine intelligenti: sono macchine in grado di eseguire in modo pedissequo istruzioni dettate da un programmatore. Tuttavia, nella nostra società sono sempre più presenti computer in grado di eseguire istruzioni proprie dell'intelligenza umana, come il parlare o il risolvere problemi di matematica.Storicamente, i matematici e gli informatici si sono posti da sempre il problema di come ricreare l'intelligenza in modo artificiale. Il modo ideale per iniziare ad affrontare questo problema è quello dei giochi: infatti, un gioco è un ambiente piccolo e circoscritto, spesso governato da semplici regole facilmente codificabili in un programma.Nella cultura popolare, il gioco per eccellenza che richiede intelligenza è il gioco degli **scacchi**: gli informatici iniziarono a tentare di sviluppare programmi in grado di giocare a scacchi fin dagli anni 50, agli albori dell'informatica. Il problema delle otto regineUn problema classico che riguarda gli scacchi è **il problema delle otto regine**: trovare tutti i modi possibili in cui si possono disporre otto regine su una scacchiera 8x8 senza che esse possano mangarsi a vicenda.La regina è il pezzo più potente del gioco degli scacchi e può muoversi arbitrariamente lungo le colonne, le righe e le diagonali della scacchiera.Il problema non è banale: è stato posto per la prima volta nel 1848 e ha interessato alcuni tra i piu grandi matematici del mondo, tra cui Gauss. Esercizio 1Prova a risolvere il problema delle otto regine su una scacchiera:* 2x2* 3x3* 4x4* 5x5ovviamente, prova a posizionare un numero di regine pari al lato della scacchiera. Il metodo di "backtracking"Il seguente codice risolve il problema delle otto regine usando la mera forza bruta: infatti, se consideriamo che possiamo mettere un'unica regina per colonna, abbiamo:* 8 possibilità per posizionare la regina nella colonna 0;* 7 possibilità per posizionare la regina nella colonna 1;* 6 possibilità per posizionare la regina nella colonna 2;* ...* 1 possibilità per posizionare la regina nella colonna 7 (l'ultima colonna).In totale, abbiamo $8! = 40320$ configurazioni da verificare. Ovviamente, gran parte di queste configurazioni sono non accettabili, perché le regine occupano una stessa diagonale. Tuttavia, il computer è sufficientemente potente per verificare tutte queste 40320 configurazioni e quindi discriminare quelle accettabili da quelle non accetabili.Questo è un esempio di algoritmo che risolve un problema che richiede intelligenza umana semplicemente sfruttando la brutale potenza di calcolo del computer.<jupyter_code># n è la dimensione della scacchiera
# c_cor è la colonna considerata in questo momento (da 0 a n-1)
#       le colonne precedenti sono già occupate da regine
# r_occ è la lista delle righe attualmente occupate da altre regine
# d_occ_1 è la lista delle diagonali da Nord-Ovest a Sud-Est
# d_occ_2 è la lista delle diagonali da Sud-Ovest a Nord-Est
def otto_regine(n, c_cor, r_occ, d_occ_1, d_occ_2):
    n_sol = 0 # numero di soluzioni trovate
    if c_cor == n:
        # TROVATA UNA SOLUZIONE
        print(r_occ) # scrivi in output le righe occupate dalle regine
        return 1
    elif c_cor < n: # PROVO A PIAZZARE UNA REGINA NELLA COLONNA c_cor
        for j in range(n): # PROVO TUTTE LE RIGHE POSSIBILI
            if not( (j in r_occ) or (c_cor+j in d_occ_1) or (c_cor-j in d_occ_2) ):
                # PIAZZO UNA REGINA NELLA COLONNA c_cor e NELLA RIGA j
                # E VADO AVANTI CON LA COLONNA c_cor+1
                n_r_occ = r_occ + [j] # nuove righe occupate
                n_d_occ_1 = d_occ_1+[c_cor+j] # nuove diagonali occupate
                n_d_occ_2 = d_occ_2+[c_cor-j]
                # chiamata ricorsiva
                n_sol += otto_regine(n, c_cor+1, n_r_occ, n_d_occ_1, n_d_occ_2)
    return n_sol


n_scacchiera = 3
ns = otto_regine(n_scacchiera, 0, [], [], [])
print(f"Il problema delle otto regine su una scacchiera di lato {n_scacchiera} ha {ns} soluzioni")<jupyter_output><empty_output><jupyter_text>Esercizio 2Modifica la variabile `n_scacchiera` nel codice precedente precedente per trovare le soluzioni al problema delle otto regine in una scacchiera:* 4x4* 5x5* 8x8  Un esempio di gioco a somma zeroConsidera il seguente gioco:* ci sono due giocatori, g1 e g2;* g1 e g2 fissano un numero $N$;* g1 e g2 giocano moltiplicando un numero $p$ per 2 oppure per 9 e alternano i turni;* l'obiettivo del gioco è raggiungere o superare il numero N;* inizia g1 partendo da $p=1$.Un esempio di gioco:* $N = 50$* g1 parte da $p=1$ e moltiplica per 9 (-> $p = 9$)* g2 moltiplica per 2 (-> $p = 18$)* g1 moltiplica per 9, raggiunge $p = 162 > N$, e vince. Esercizio 3Prova a giocare con un tuo compagno utilizzando i seguenti numeri: * $N = 18$* $N = 19$* $N = 100$* $N = 200$* $N = 1000$* $N = 2000$* $N = 1000000$Eventualmente, prova a giocare la stessa strategia più volte, cercando un modo ottimale per scegliere il gioco. Esercizio 4Fissato un certo $N$, sapresti elaborare uno schema o una procedura per giocare una strategia ottimale?  La strategia MinimaxIl seguente codice implementa la strategia minimax: una tecnica di intelligenza artificiale che sfrutta la potenza di calcolo del computer. Essa consiste nell'esplorare tutte le configurazioni di gioco possibili alternando due giocatori:* il giocatore MAX, implementato dalla funzione `g1_max`. Il giocatore MAX prova tutte le mosse possibili e, assumendo che l'avversario g2 giochi sempre in modo ottimale, sceglie l'opzione migliore per g1.* il giocatore MIN, implementato dalla funzione `g2_min`. Il giocatore MIN prova tutte le mosse possibili e, assumendo che l'avversario g1 giochi sempre in modo ottimale, sceglio l'opzione peggiore per g1.La strategia Minimax è alla base dei programmi per computer che giocano a scacchi: in particolare è alla base del software che sul supercomputer Deep Blue nel 1997 sconfisse il campione del mondo di scacchi <NAME>. Attualmente la strategia Minimax è stata talmente raffinata che non è più necessario avere un supercomputer per battere il campione del mondo di scacchi: anche il semplice processore del cellulare è sufficiente.<jupyter_code># Restituisce il massimo punteggio
# che il giocatore 1 fa se riceve il gioco
# con il valore p
def g1_max(N, p):
    if p >= N:
        vincitore = 2
        mossa = -1
        return vincitore, mossa
    for i in [2,9]:
        vincitore, mossa = g2_min(N, p *i)
        if vincitore == 1:
            return 1, i
    # Se non c'è una mossa vincente
    # vince g2
    vincitore = 2
    mossa = 2
    return vincitore, mossa

# Resituisce il minimo punteggio
# che il giocatore 1 fa se l'avversario
# riceve il gioco con il valore p
def g2_min(N, p):
    if p >= N:
        vincitore = 1
        mossa = -1
        return vincitore, mossa
    
    for i in [2,9]:
        vincitore, mossa = g1_max(N, p *i)
        if vincitore == 2:
            return 2, i
    # Se non c'è una mossa vincente
    # vince g1
    vincitore = 1
    mossa = 2
    return vincitore, mossa<jupyter_output><empty_output><jupyter_text>Il seguente codice ti permette di giocare contro il computer. Inoltre, il codice ti suggerirà la mossa ottimale, in accordo alla strategia minimax.<jupyter_code>import colorama
from colorama import Fore


n_gioco = int(input("Inserire numero da raggiungere: ") )

p = 1

while p < n_gioco:
    print(Fore.MAGENTA + f"\n\n\n -------> Stato del gioco: p = {p} e N = {n_gioco} <-------\n\n" + Fore.BLACK)
    
    vincitore, mossa_sug = g1_max(n_gioco, p)

    print(Fore.BLUE)
    if vincitore == 1:
        
        print("Il giocatore 1 vince se gioca in modo ottimale")
    else:
        print("Il giocatore 1 perde se il giocatore 2 gioca in modo ottimale")
    
    print(f"Mossa suggerita: {mossa_sug}")
    print(Fore.BLACK)
    
    mossa = int(input("Inserire fattore moltiplicativo: "))
    
    p = p * mossa
    
    if p >= n_gioco:
        print(Fore.GREEN + "Hai vinto!")
        break
    
    vincitore, mossa = g2_min(n_gioco, p)
    
    print(Fore.RED + f"\nIl giocatore 2 usa il fattore moltiplicativo: {mossa}")
    
    p = p*mossa
    
    if p >= n_gioco:
        print("Hai perso!")
        break<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.062319189971070395, 'fraction_numerical': 0.018924783027965283, 'mean_word_length': 3.612006670372429, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '130524', 'license': 'CC0-1.0', 'n_tokens_mistral': 3041, 'n_tokens_neox': 2948, 'n_words': 1131, 'path': 'Intelligenza artificiale, scacchi e brute force.ipynb', 'repo_name': 'comaschipaolo/corso_coding_2022', 'size': '8304'}