Grafica su C++

Pubblicità
rctimelines ha detto:
Rispetto al titolo mi pare che siate molto OT.

Comunque.. stiamo parlando di tic-tac-toe? È un gioco veramente stupido in cui chi inizia per primo vince sempre!

Quindi implementare una "logica" per questo gioco è un'espressione discutibile!

1) Le mosse da simulare sono un numero limitatissimo e sinceramente sempre le stesse (tra l'altro sono simmetriche per cui il numero di dimezza.
2) La conclusione è sempre di vittoria o pareggio a seconda di chi inizia.. quindi la scelta della mossa diventa sempre arbitraria...

ma avete mai visto il film "war games"?

Inviato dal mio Nexus 5 utilizzando Tapatalk
Clicca per espandere...
Nel mio caso fu appunto una scelta semplice solo per l'implementazione dell'algoritmo (MiniMax), senza complicare le cose con altro. Questo è il motivo per il quale suggerivo ad inizio topic di utilizzare qualcosa di "base", visto che lo scopo è implementare tic tac toe.
Le logiche si fanno interessanti con Connect 4 e minimax

Comunque si, siamo molto OT ormai.
@_Achille proseguiamo in pvt, scrivimi pure.

Inviato da ONEPLUS A5000 tramite App ufficiale di Tom\'s Hardware Italia Forum
 
Ok

Io farei 3 matrici, una per ogni giocatore (velocissime da verificare la vittoria con 8 sommatorie) più una che usa il computer per sviluppare ogni volta che tocca a lui tutte le rimanenti mosse possibili e decidere quale fare in caso di vittoria o, se non si riesce, di pareggio.. altrimenti succede come nel film: il CPU va in loop perché non vince!

Inviato dal mio Nexus 5 utilizzando Tapatalk
 
rctimelines ha detto:
Ok

Io farei 3 matrici, una per ogni giocatore (velocissime da verificare la vittoria con 8 sommatorie) più una che usa il computer per sviluppare ogni volta che tocca a lui tutte le rimanenti mosse possibili e decidere quale fare in caso di vittoria o, se non si riesce, di pareggio.. altrimenti succede come nel film: il CPU va in loop perché non vince!

Inviato dal mio Nexus 5 utilizzando Tapatalk
Clicca per espandere...
Non ho ben capito. Perché 3 matrici quando i giocatori sono due? Comunque il computer ha già una sua “matrice” di copia perché uso un oggetto vector passato non per reference.
DispatchCode ha detto:
Nel mio caso fu appunto una scelta semplice solo per l'implementazione dell'algoritmo (MiniMax), senza complicare le cose con altro. Questo è il motivo per il quale suggerivo ad inizio topic di utilizzare qualcosa di "base", visto che lo scopo è implementare tic tac toe.
Le logiche si fanno interessanti con Connect 4 e minimax

Comunque si, siamo molto OT ormai.
@_Achille proseguiamo in pvt, scrivimi pure.

Inviato da ONEPLUS A5000 tramite App ufficiale di Tom\'s Hardware Italia Forum
Clicca per espandere...
Ma non siamo affatto OT. Sempre di Tris stiamo parlando.

Quel che mi interessava era creare un algoritmo intelligente che portava sempre ad uno stato di vittoria o pareggio.
 
_Achille ha detto:
Non ho ben capito. Perché 3 matrici quando i giocatori sono due? Comunque il computer ha già una sua “matrice” di copia perché uso un oggetto vector passato non per reference.

Ma non siamo affatto OT. Sempre di Tris stiamo parlando.

Quel che mi interessava era creare un algoritmo intelligente che portava sempre ad uno stato di vittoria o pareggio.
Clicca per espandere...
Il titolo dice grafica c++.. cosa c'entra il tris?

Se per questo allora: anche se i giocatori sono due giocano su una matrice sola.. quindi perché te ne servirebbero due?..


Inviato dal mio Nexus 5 utilizzando Tapatalk
 
rctimelines ha detto:
Il titolo dice grafica c++.. cosa c'entra il tris?

Se per questo allora: anche se i giocatori sono due giocano su una matrice sola.. quindi perché te ne servirebbero due?..


Inviato dal mio Nexus 5 utilizzando Tapatalk
Clicca per espandere...
Il titolo era indicativo su che APi utilizzare su C++ per la parte grafica, poi specializzato nel progetto TicTacToe.
Ne servono due per evitare che l'algoritmo lasci qualche punto non desiderato. In ogni caso c'è il costruttore di copia che se ne occupa per le due classi

@DispatchCode ho il link al codice senza parte grafica: https://drive.google.com/open?id=1DsPerDDa-jriMx94HfztLX2sAOjfJmr9. Continua a non fungere completamente. Forse non ho ben capito il ragionamento....
 
rctimelines ha detto:
?!?


Inviato dal mio Nexus 5 utilizzando Tapatalk
Clicca per espandere...
La copia della matrice. Semplicemente non uso una variabile reference per evitare problemi.

@DispatchCode penso di averlo fatto funzionare. Non perde mai!
La modifica al codice precedente è questa:

Minimax.h
C++: 
#include "TicTacToe.h"
#include <vector>

struct _algorithm_search {

    int rating;
    int distance;
};

class Minimax
{
public:
    Minimax(std::vector<int>);
    int get_position();

private:
    _algorithm_search Minimax_algorithm_max(int);
    _algorithm_search Minimax_algorithm_min(int);
    int check_win();

    std::vector<int> grid;
    int position;
};

Minimax.cpp
C++: 
#include "Minimax.h"

#include <vector>

using namespace std;

Minimax::Minimax(vector<int> copy)
    : grid(copy)
{
    _algorithm_search max = { INT_MIN, INT_MAX };
    for(int i = 0; i < 9; i++)
        if (grid[i] == VOID_P)
        {
            grid[i] = COMPUTER_P;
            _algorithm_search temp = Minimax_algorithm_min(1);
            if (temp.rating > max.rating || (temp.rating == max.rating && temp.distance < max.distance))
            {
                max = temp;
                position = i;
            }
            grid[i] = VOID_P;
        }
}

int Minimax::get_position()
{
    return position;
}

_algorithm_search Minimax::Minimax_algorithm_max(int d)
{
    if (check_win() == COMPUTER_P)
        return { 10, d };
    if (check_win() == PLAYER_P)
        return { -10, d };
    if(check_win() == 3)
        return { 0, d };

    _algorithm_search max = { INT_MIN, INT_MAX };
    for (int i = 0; i < 9; i++)
        if (grid[i] == VOID_P)
        {
            grid[i] = COMPUTER_P;
            _algorithm_search temp = Minimax_algorithm_min(d + 1);
            if (temp.rating > max.rating || (temp.rating == max.rating && temp.distance < max.distance))
                max = temp;
           
            grid[i] = VOID_P;
        }

    return max;
}

_algorithm_search Minimax::Minimax_algorithm_min(int d)
{
    if (check_win() == COMPUTER_P)
        return { 10, d };
    if (check_win() == PLAYER_P)
        return { -10, d };
    if (check_win() == 3)
        return { 0, d };

    _algorithm_search min = { INT_MAX, INT_MIN };
    for (int i = 0; i < 9; i++)
        if (grid[i] == VOID_P)
        {
            grid[i] = PLAYER_P;
            _algorithm_search temp = Minimax_algorithm_max(d + 1);
            if (temp.rating < min.rating || (temp.rating == min.rating && temp.distance > min.distance)    )
                min = temp;

            grid[i] = VOID_P;
        }

    return min;
}

int Minimax::check_win()
{
    for (int i = 0; i <= 6; i += 3)
        if (grid[i] != VOID_P && grid[i] == grid[i + 1] && grid[i] == grid[i + 2])
            return grid[i];
    for (int i = 0; i < 3; i++)
        if (grid[i] != VOID_P && grid[i] == grid[i + 3] && grid[i] == grid[i + 6])
            return grid[i];

    if (grid[0] != VOID_P && grid[0] == grid[4] && grid[0] == grid[8])
        return grid[0];

    if (grid[6] != VOID_P && grid[6] == grid[4] && grid[6] == grid[2])
        return grid[6];

    for (int i = 0; i < 9; i++)
        if (grid[i] == VOID_P)
            return 0;

    return 3;
}

Ora proseguo con l'implementazione della grafica con una classe derivata
 
Provando a inserire la Potatura Alfa-Beta si ottiene un risultato sbagliato, ma comunque leggermente intelligente (potrebbe andare bene per una difficoltà bassa :asd:).
La potatura mica la ho capita. Come faccio a sapere se devo continuare se per sapere il risultato devo visitare tutto il ramo?
 
_Achille ha detto:
Provando a inserire la Potatura Alfa-Beta si ottiene un risultato sbagliato, ma comunque leggermente intelligente (potrebbe andare bene per una difficoltà bassa :asd:).
La potatura mica la ho capita. Come faccio a sapere se devo continuare se per sapere il risultato devo visitare tutto il ramo?
Clicca per espandere...

Alpha è il massimo valore minimo, e beta è il minimo valore massimo. Praticamente sono i limiti dei possibili valori.

Inizi con alpha = - inf, e beta = inf.
Quando arrivi ad una foglia, in questo caso uno stato terminale (vittoria, pareggio, sconfitta), ottieni un valore. Il valore diventa il nuovo massimo (beta). Torna quindi verso l'alto, e viene valutato il nodo precedente. In questo caso il valore sarà alpha.
Se non hai più alpha e beta sovrapposti (immaginati due linee, una che va verso destra ed una verso sinistra), in pratica, puoi ignorare quel valore. Di conseguenza tagli, ignorando tutti i digli (da pc, nel caso, se dovesse servire, sarò più chiaro).
 
DispatchCode ha detto:
Alpha è il massimo valore minimo, e beta è il minimo valore massimo. Praticamente sono i limiti dei possibili valori.

Inizi con alpha = - inf, e beta = inf.
Quando arrivi ad una foglia, in questo caso uno stato terminale (vittoria, pareggio, sconfitta), ottieni un valore. Il valore diventa il nuovo massimo (beta). Torna quindi verso l'alto, e viene valutato il nodo precedente. In questo caso il valore sarà alpha.
Se non hai più alpha e beta sovrapposti (immaginati due linee, una che va verso destra ed una verso sinistra), in pratica, puoi ignorare quel valore. Di conseguenza tagli, ignorando tutti i digli (da pc, nel caso, se dovesse servire, sarò più chiaro).
Clicca per espandere...
Il principio lo ho capito, ma poi non riesco a capirlo ne teoricamente ne in pratica.
O forse sì. Ad esempio
5 -> 5 -> 8
..........-> 5
...-> 4 -> 4
..........-> ecc

La prima mossa è un Max. In teoria non si vanno più a considerare i rami del 4 perché ormai si ha 4 che è minore di 5 e dato che deve essere preso il minimo ogni valutazione risulta inutile.
È così? 5 quindi è alfa che evita valutazioni di rami Min in cui compare un valore minore. Beta invece evita valutazioni in rami Max se compare un valore più grande di esso

Grazie per tutto l’aiuto comunque

PS: sfortunatamente non vengono rappresentati gli spazi che portano lo schema ad essere più comprensibile...

Aggiornamento: AlfaBeta messo, i risultati sono corretti ma il tempo è uguale a prima
 
Ultima modifica:
Considera che TicTacToe ha 9 possibili mosse per il primo giocatore, 8 per il secondo e così via. In teoria sarebbero quindi 9! mosse, ma nella pratica termina prima (non tutte le partite richiedono 9 mosse). Le simulazioni sono molte per noi , per rappresentarle su carta, ma non sono così tante. Quindi la potatura avrà un impatto inferiore.
Questo è ciò che intendeva dire rctimelines presumo.

Tornando all'algoritmo, ed andando molto OT, diciamo semplificando che se ti trovi a dover valutare un nodo MIN allora è importante che il valore beta del primo figlio non sia minore di alpha; se lo è, è inutile verificare l'altro nodo.

Immagina, semplificando molto la struttura, un albero di questo tipo:

Codice: 
    B
  /  \
 C    D

B è un nodo MAX, mentre C e D sono MIN.
Si può quindi dire che al livello di MAX lo scopo è considerare il figlio (C o D) con valore maggiore. I valori di alpha e beta sono rispettivamente -inf e +inf.
Ipotizziamo di essere alla foglia C, e di trovare il valore 4. E' necessario considerare max(-inf, 4) che restituirà ovviamente 4.

Ora la scelta: è necessario guardare l'altro figlio, ovvero D? Per saperlo si deve testare questo valore, ed ovviamente beta < alpha torna falso (beta è ancora +inf, mentre alpha è ora 4).
Si valuta quindi D, e si scopre il valore 7. A questo punto max(4, 7) restituisce 7, e questo è il valore del nodo B.

Immagina una situazione analoga, ma più in profondità nell'albero. Quando il valore di B verrebbe restituito, questo diventerebbe il nuovo valore di beta del nodo padre. Supponi quindi - scoprendo un altra parte di albero - di avere:

Codice: 
       A
     /   \
   B      E
  / \    / \
 C   D  F   G
A questo punto A ha quindi beta = 7, e di conseguenza passa questo valore ad E, che vedrà beta=7 ed alpha = -inf.
Prendiamo quindi i figli, iniziando da F; supponiamo di trovare il valore 10. Discorso analogo a prima alpha = max(-inf, 10), che restituirà 10. Adesso E avrà un beta = 7 e alpha = 10. La condizione valutata sul nodo B, in questo caso diventa vera e ci fa ignorare il valore di G (potando quindi il ramo che porta a G).

Il valore che viene quindi restituito ad A è beta=10. Il nodo A avrà di conseguenza beta=10 e alpha = 7 ed il valore di A è quindi min(7, 10), ovvero 7.


P.S. se hai altre domande apri un altro topic, quotando anche il contenuto ed eventualmente linkando questo; ti rispondo volentieri, ma qui si sta andando parecchio OT. ;)

pps. dovrebbero vedersi decentemente gli "alberi", spero...
 
Pubblicità
Pubblicità
Indietro
Top