El joc dels «tres en ratlla» clàssic és un senzill però bonic exercici de programació.
Es tracta de programar un algorisme que guanyi la partida si es presenta l’oportunitat.
Les regles del joc són:
El joc es juga a un tauler de tres per tres caselles.
El jugador humà juga amb les “X”, l’ordinador amb les “O”.
El jugador que comença la partida es tria aleatòriament.
A una jugada, el jugador marca una casella que no estigui marcada prèviament.
Quan el jugador ha marcat una casella buida, el torn passa a l’altre jugador.
El jugador que aconsegueix primer marcar tres caselles alineades ( en horitzontal, vertical o diagonal) guanya la partida i acaba el joc
Quan les nou caselles estan ocupades acaba el joc
Si cap jugador ha aconseguit posar tres marques en ratlla, el joc acaba amb empat.
Si heu dedicat alguna estona a aquest joc ja sabreu que dos jugadors que facin un joc òptim empataran.
El que faig al post d’avui és presentar un petit programa en C++ que juga al tres en ratlla.
Vet aquí el codi :
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
class Triplet {
public:
int indexes[3];
Triplet(int index0, int index1, int index2) {
Triplet::indexes[0] = index0;
Triplet::indexes[1] = index1;
Triplet::indexes[2] = index2;
}
};
class Triplets {
public:
vector<Triplet> triplets;
Triplets() {
triplets.push_back(newTriplet(0, 1, 2));
triplets.push_back(newTriplet(3, 4, 5));
triplets.push_back(newTriplet(6, 7, 8));
triplets.push_back(newTriplet(0, 3, 6));
triplets.push_back(newTriplet(1, 4, 7));
triplets.push_back(newTriplet(2, 5, 8));
triplets.push_back(newTriplet(0, 4, 8));
triplets.push_back(newTriplet(6, 4, 2));
}
Triplet newTriplet(int index0, int index1, int index2) {
Triplet triplet(index0, index1, index2);
return triplet;
}
};
class Board {
public:
vector<string> cells;
Board() {
for (int i = 0; i < 9; i++) {
Board::cells.push_back(" ");
}
}
void show() {
for (int row = 0; row < 3; row++) {
for (int column = 0; column < 3; column++) {
cout << " | " << row * 3 + column << " "
<< Board::cells.at(row * 3 + column) << " |";
}
cout << endl;
}
cout << "----------------------------------------------------" << endl;
}
};
class HumanPlayer {
public:
void humanMove(Board *board) {
bool validMove = false;
int index = -1;
while (!validMove) {
while ((index < 0) || (index > 8)) {
cout << "Jugues tu (humà)" << endl;
cout << "A quina casella vols posar la fitxa ? ( 0 - 8 ) ?"
<< endl;
cin >> index;
}
if (board->cells.at(index) == " ") {
validMove = true;
board->cells.at(index) = "X";
} else {
cout << "La casella " << index
<< " ja està ocupada. Tria'n una altre." << endl;
index = -1;
}
}
}
};
class ComputerPlayer {
int scoreTable[9];
bool isCentralCellAvailable() {
bool centralCellAvailable = false;
if (board->cells.at(4) == " ") {
board->cells.at(4) = "O";
cout << "Jo jugo a la casella 4" << endl;
centralCellAvailable = true;
}
return centralCellAvailable;
}
bool canIWin() {
bool iWin = false;
for (int indexTriplet = 0; indexTriplet < 8; indexTriplet++) {
int iNumComputerCoins = 0;
int indexFreeCell = -1;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[0])
== "O")
iNumComputerCoins++;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[1])
== "O")
iNumComputerCoins++;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[2])
== "O")
iNumComputerCoins++;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[0])
== " ")
indexFreeCell = 0;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[1])
== " ")
indexFreeCell = 1;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[2])
== " ")
indexFreeCell = 2;
if ((iNumComputerCoins == 2) && (indexFreeCell >= 0)) {
cout << "Jo jugo a la casella "
<< triplets.triplets.at(indexTriplet).indexes[indexFreeCell]
<< endl;
cout << "Guanyo jo!" << endl;
board->cells.at(
triplets.triplets.at(indexTriplet).indexes[indexFreeCell]) =
"O";
iWin = true;
break;
}
}
return iWin;
}
bool canIBlock() {
bool iBlock = false;
for (int indexTriplet = 0; indexTriplet < 8; indexTriplet++) {
int iNumHumanCoins = 0;
int indexFreeCell = -1;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[0])
== "X")
iNumHumanCoins++;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[1])
== "X")
iNumHumanCoins++;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[2])
== "X")
iNumHumanCoins++;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[0])
== " ")
indexFreeCell = 0;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[1])
== " ")
indexFreeCell = 1;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[2])
== " ")
indexFreeCell = 2;
if ((iNumHumanCoins == 2) && (indexFreeCell >= 0)) {
cout << "Jo jugo a la casella "
<< triplets.triplets.at(indexTriplet).indexes[indexFreeCell]
<< endl;
board->cells.at(
triplets.triplets.at(indexTriplet).indexes[indexFreeCell]) =
"O";
iBlock = true;
break;
}
}
return iBlock;
}
void chooseOne() {
cleanScoreTable();
calculateScoreTable();
// showScoreTable();
int indexCell = selectMostValuableCell();
board->cells.at(indexCell) = "O";
cout << "Jo jugo a la casella " << indexCell << endl;
}
void cleanScoreTable() {
for (int i = 0; i < 9; i++) {
scoreTable[i] = 0;
}
}
void calculateScoreTable() {
for (int i = 0; i < 9; i++) {
calculateScoreCell(i);
}
}
void showScoreTable() {
cout << "---------------------------------------------------------"
<< endl;
cout << "score table :";
for (int i = 0; i < 9; i++) {
cout << " " << scoreTable[i];
}
cout << endl;
cout << "---------------------------------------------------------"
<< endl;
}
void calculateScoreCell(int indexCell) {
if ((board->cells.at(indexCell) == "O")
|| (board->cells.at(indexCell) == "X")) {
scoreTable[indexCell] = 0;
} else {
scoreTable[indexCell] = numFreeTripletsForCell(indexCell);
}
}
int numFreeTripletsForCell(int indexCell) {
int numFreeTriplets = 0;
for (int indexTriplet = 0; indexTriplet < 8; indexTriplet++) {
if (isCellInTriplet(indexCell, indexTriplet)) {
if (isTripletFree(indexTriplet)) {
numFreeTriplets++;
}
}
}
return numFreeTriplets;
}
bool isCellInTriplet(int indexCell, int indexTriplet) {
bool isInTriplet = false;
if ((triplets.triplets.at(indexTriplet).indexes[0] == indexCell)
|| (triplets.triplets.at(indexTriplet).indexes[1] == indexCell)
|| (triplets.triplets.at(indexTriplet).indexes[2] == indexCell)) {
isInTriplet = true;
}
return isInTriplet;
}
bool isTripletFree(int indexTriplet) {
bool isTripletFree = false;
if (board->cells.at(triplets.triplets.at(indexTriplet).indexes[0])
== " "
&& board->cells.at(
triplets.triplets.at(indexTriplet).indexes[1]) == " "
&& board->cells.at(
triplets.triplets.at(indexTriplet).indexes[2]) == " ") {
isTripletFree = true;
}
return isTripletFree;
}
int selectMostValuableCell() {
int indexMax = -1;
int actualMax = 0;
for (int i = 0; i < 9; i++) {
if (scoreTable[i] > actualMax) {
actualMax = scoreTable[i];
indexMax = i;
}
}
if (indexMax == -1) {
indexMax = selectEmptyCell();
}
return indexMax;
}
int selectEmptyCell() {
int indexCell;
for (indexCell = 0; indexCell < 9; indexCell++) {
if (board->cells.at(indexCell) == " ")
break;
}
return indexCell;
}
public:
Board *board;
Triplets triplets;
void computerMove(Board* board) {
this->board = board;
cout << "Jugo jo (ordinador)" << endl;
if (!isCentralCellAvailable()) {
if (!canIWin()) {
if (!canIBlock()) {
chooseOne();
}
}
}
}
};
class Game {
const int HUMAN = 1;
const int COMPUTER = 0;
int firstPlayer() {
int i = rand() % 2;
return i;
}
bool isEndGame() {
bool endGame = false;
board.show();
if (isHumanWin() || isComputerWin() || isTie()) {
endGame = true;
}
return endGame;
}
bool isHumanWin() {
return isPlayerWin("X");
}
bool isComputerWin() {
return isPlayerWin("O");
}
bool isPlayerWin(string playerCoin) {
bool playerWin = false;
for (int indexTriplet = 0; indexTriplet < 8; indexTriplet++) {
if (board.cells.at(triplets.triplets.at(indexTriplet).indexes[0])
== playerCoin
&& board.cells.at(
triplets.triplets.at(indexTriplet).indexes[1])
== playerCoin
&& board.cells.at(
triplets.triplets.at(indexTriplet).indexes[2])
== playerCoin) {
playerWin = true;
break;
}
}
return playerWin;
}
bool isTie() {
bool tie = true;
for (int indexCell = 0; indexCell < 9; indexCell++) {
if (board.cells.at(indexCell) == " ") {
tie = false;
break;
}
}
if (tie) {
cout << "Hem empatat" << endl;
}
return tie;
}
public:
Board board;
Triplets triplets;
int currentPlayer;
HumanPlayer human;
ComputerPlayer computer;
Game() {
srand(time(NULL));
currentPlayer = firstPlayer();
}
void play() {
while (!isEndGame()) {
if (currentPlayer == HUMAN) {
human.humanMove(&board);
currentPlayer = COMPUTER;
} else {
computer.computerMove(&board);
currentPlayer = HUMAN;
}
}
}
};
int main() {
cout << "LAB - Tic Tac Toe" << endl;
cout << "----------------------------------------------------" << endl;
Game game;
game.play();
return 0;
}
El que he implementat és una versió de consola del “Tres en Ratlla”. He fet servir el llenguatge C++.
Game és la classe que gestiona el joc, és dir, qui juga primer, a qui li toca jugar, determina qui ha guanyat o si hi ha empat i quan acaba la partida.
Per a poder fer totes aquestes tasques, Game manté una instància de la classe Board. Board modela el tauler de jocs amb un vector públic de nou elements de tipus string. Board té un mètode show() per mostrar el vector com una taula de tres per tres. Inicialment, cada element del vector de Board conté un espai en blanc (” “) per indicar que la casella està buida, i, a més, aquest valor és convenient per a que la visualització del tauler tingui una mínima estètica.
Game també manté una instància de la classe HumanPlayer i una altre de ComputerPlayer. Totes dues reben un punter a Board, de forma que el poden actualitzar amb la jugada que facin. HumanPlayer es limita a recollir quina casella es vol marcar i comprovar que la jugada és vàlida. ComputerPlayer és la petita intel·ligència artificial que implementa l’estratègia de joc.
Per a comprovar fàcilment si hi ha guanyador, Game utilitza una instància de Triplets, que és un vector de instàncies de la classe Triplet (sense s final). Un Triplet és, essencialment, un array de tres enters on cada enter representa l’index (del vector de Board) d’una cel·la. Aleshores una triplet és un conjunt de tres de cel·les que estan en línia. En total hi han vuit combinacions de tres cel·les que estan en línia (tres horitzontals, tres verticals i dues diagonals). ComputerPlayer també fa servir Triplets per calcular les seves jugades.
L’estratègia de ComputerPlayer és molt senzilla:
Si la casella central està buida, l’ocupa.
Si no està buida, comprova si marcant alguna cel·la, guanya. És dir, cerca Triplets en que hi ha una casella buida i dues caselles marcades amb “O”. Si és el cas, marca la casella buida amb “O”.
Si no pot guanyar, comprova si pot bloquejar la victòria del jugador humà. És dir, cerca Triplets en que hi ha una casella buida i dues caselles marcades amb “X”. Si és el cas, marca la casella buida amb “O”.
Si no es dona cap dels casos anteriors, aleshores ha de triar una de les caselles lliures. El que cal és avaluar quina és la millor casella de les que estan disponibles. He observat (moltes hores jugant xD xD xD) que la millor casella és la que habilita més possibilitats de guanyar.
Què vol dir això? Quan el tauler és buit, la casella central participa en quatre trios guanyadors (les dues diagonals i les centrals horitzontal i vertical ). Les cantonades, en tres (els dos costats i la diagonal). Les caselles centrals de cada costat, només dos (el costat i la central horitzontal o vertical). Per tant, la casella central és la millor opció d’inici, perquè és la que habilita més possibilitats de guanyar.
Quan la casella central està ocupada, el jugador contrari troba que ara les cantonades habiliten dos trios guanyadors (els dos costats), i les caselles centrals de cada costat només un (el costat). La millor opció, la que habilita més possibilitats de guanyar, és una de les cantonades.
Per a triar quina casella escollir, el mètode chooseOne recalcula una taula de puntuacions a partir de l’estat actual del Board i, senzillament, tria la cel·la que té la puntuació més alta.
Vet aquí un joc de prova :
LAB - Tic Tac Toe | 0 | | 1 | | 2 | | 3 | | 4 | | 5 | | 6 | | 7 | | 8 | Jugues tu (humà) A quina casella vols posar la fitxa ? ( 0 - 8 ) ? 4 | 0 | | 1 | | 2 | | 3 | | 4 X | | 5 | | 6 | | 7 | | 8 | Jugo jo (ordinador) Jo jugo a la casella 0 | 0 O | | 1 | | 2 | | 3 | | 4 X | | 5 | | 6 | | 7 | | 8 | Jugues tu (humà) A quina casella vols posar la fitxa ? ( 0 - 8 ) ? 1 | 0 O | | 1 X | | 2 | | 3 | | 4 X | | 5 | | 6 | | 7 | | 8 | Jugo jo (ordinador) Jo jugo a la casella 7 | 0 O | | 1 X | | 2 | | 3 | | 4 X | | 5 | | 6 | | 7 O | | 8 | Jugues tu (humà) A quina casella vols posar la fitxa ? ( 0 - 8 ) ? 6 | 0 O | | 1 X | | 2 | | 3 | | 4 X | | 5 | | 6 X | | 7 O | | 8 | Jugo jo (ordinador) Jo jugo a la casella 2 | 0 O | | 1 X | | 2 O | | 3 | | 4 X | | 5 | | 6 X | | 7 O | | 8 | Jugues tu (humà) A quina casella vols posar la fitxa ? ( 0 - 8 ) ? 5 | 0 O | | 1 X | | 2 O | | 3 | | 4 X | | 5 X | | 6 X | | 7 O | | 8 | Jugo jo (ordinador) Jo jugo a la casella 3 | 0 O | | 1 X | | 2 O | | 3 O | | 4 X | | 5 X | | 6 X | | 7 O | | 8 | Jugues tu (humà) A quina casella vols posar la fitxa ? ( 0 - 8 ) ? 8 | 0 O | | 1 X | | 2 O | | 3 O | | 4 X | | 5 X | | 6 X | | 7 O | | 8 X | Hem empatat
El codi del post es pot trobar a https://github.com/abaranguer/lab-tictactoe
Apunts de Tecnologia 