Connect4
Alexandru Coles 332CB
La joc participa doi jucatori (om vs. om, om vs. computer, sau computer vs. computer), fiecare are piesele lui, trebuind sa aleaga o coloana in care depune o piesa. Piesa pusa intr-o coloana va ocupa randul cel mai de jos posibil(ea cade acolo). Daca o coloana este plina nu se mai pot pune piese acolo. Scopul jucatorului este de a ‘conecta’ primul 4 piese(minim) proprii pe o linie (verticala sau orizontala), sau pe o diagonala. Jocul se poate termina la egalitate daca nici unul din jucatori nu a reusit sa conecteze 4 piese si tabla de joc este plina.
Implementarea jocului a fost facuta in C++ si OpenGL pentru reprezentarea grafica. Mediul de dezvoltare este Microsoft Visual Studio 6.0, iar pentru sistemul de ferestre am folosit biblioteca Glut 3.1. Teoretic, din cauza bibliotecilor folosite, jocul poate fi purtat cu usurinta pe alte platforme precum Unix/Linux.
Reprezentarea tabelei de joc e facuta prin mapare de texturi asupra unor poligoane ce genereaza o "grila". Texturile folosite pot imbunatati aspectul tabelei... actualele fiind "programmer art". Acestea pot fi inlocuite usor cu orice textura TGA 64x64 sau 128x218 24bit, acestea fiind puse in directorul \Texture .
Functiile de baza ale jocului Connect4 sunt continute in fisierul C4.C . Ele contin si functii pe baza carora calculatorul poate juca Connect4, chiar si cu setari non-standard (standard 7x6 tabela... 4 piese ce trebuie conectate).
Starea unui joc este retinuta intr-o structura 'Game_state' :
typedef struct {
char **board; //tabela
de joc [x][y] specifica pozitia pe coloana x si randul y
int *(score_array[2]); //tabloul in care sunt retinute statisticile pentru jucatori
0 si 1
int score[2]; //scorurile efective, deduse ca suma scorurilor din score_array,
pastrate pentru eficienta
short int winner; //castigatorul jocului: player 0, 1 sau C4_NONE
int num_of_pieces; //numarul de piese de pe tabela, pastrate separat pentru
eficienta
} Game_state;
Cu ajutorul acestei structuri implementez o stiva de stari, starea curenta analizata aflandu-se in varf; retin si numarul starilor alocate. De asemenea retin si un pointer catre varful acesteia. Atunci cand exista un joc in desfasurare (initializat cu functia c4_new_game) fiecare jucator alege o coloana pentru a pune o piesa. Dupa fiecare mutare scorul curent al fiecarui jucator este recalculat cu functia <update_score>. Pe baza acestor scoruri, calculatorul va decide urmatoarea sa mutare.
/* Simulam toate mutarile posibile si vedem rezultatele. */
for (i=0; i<size_x; i++) {
push_state();
current_column = drop_order[i];
/* Daca coloana e plina, o scoatem din calcul. */
if (drop_piece(real_player, current_column) < 0) {
pop_state();
continue;
}
/* Daca mutarea e castigatoare, am gasit-o! */
if (current_state->winner == real_player) {
best_column = current_column;
pop_state();
break;
}
/* Altfel, vezi cat de buna poate fi mutarea pe viitor
*/
/* presupunand ca oponentul face cele mai bune mutari */
else {
goodness = evaluate(real_player, level, -(INT_MAX), -best_worst);
}
/* Daca mutarea e mai buna decat cea calculata inainte,
o salvez */
if (goodness > best_worst) {
best_worst = goodness;
best_column = current_column;
num_of_equal = 1;
}
/* Daca doua mutari sunt la fel de bune, ia una din ele
*/
else if (goodness == best_worst) {
num_of_equal++;
if (rand()%10000 < ((float)1/(float)num_of_equal) * 10000)
best_column = current_column;
}
pop_state();
}
Mutarea cea mai buna, in cazul ca nu e imediat castigatoare, este decisa pe baza functiei recursive <evaluate>. Sunt analizate mutarile anticipat, presupunand ca ambii jucatorii fac cele mai bune decizii posibile. Variabilele alpha si beta sunt folosite pentru a parcurge arborele de joc spre a evita parcurgerea unor cai ce nu duc la rezultate bune.Cel mai slab rezultat (goodness) pe care starea curenta il poate produce in numarul de mutari (=level) precalculate este returnat. Acesta este cel mai bun rezultat la care jucatorul poate spera avand in vedere ca oponentul face cele mai bune mutari posibile. De observat ca preferinta pentru mutare este stabilita pentru coloanele din centru.
if (level == depth)
return goodness_of(player);
else {
/* Este tura celuilalt jucator */
best = -(INT_MAX);
maxab = alpha;
for(i=0; i<size_x; i++) {
push_state();
if (drop_piece(other(player), drop_order[i]) < 0) {
pop_state();
continue;
}
if (current_state->winner == other(player))
goodness = INT_MAX - depth;
else
goodness = evaluate(other(player), level, -beta, -maxab);
if (goodness > best) {
best = goodness;
if (best > maxab)
maxab = best;
}
pop_state();
if (best > beta)
break;
}
/* Ceea ce este bine pentru celalalt jucator nu e bine
pentru acesta */
return -best;
}
Nivelul de joc al calculatorului (1-10) se poate seta din fisierul .INI . Acesta reprezinta numarul de mutari in avans analizat. Astfel calculatorul devine un jucator redutabil de la nivelul 4 in sus! Se poate analiza si un joc intre doua calculatoare de nivele egale sau diferite...