Newsgroup: it.comp.lang.c++
Titolo: Algoritmo tctactoe

Salve,
tictactoe per cosï¿œ dire: in realtï¿œ finirebbe per l'essere applicabile a 
qualsiasi soluzione di sorta. Mi spiego:
Volendo implementare il tictactoe, quale sarebbe un buon algoritmo per 
controllare uno stato di vittoria di uno dei due players? Per ora il mio 
codice ï¿œ qualcosa del genere (non fate caso alla notazione della matrice 
stile C#)
//WHAT THE FUCK IS THIS SHIT
if (
	(Board[0, 0] == Board[0, 1] && Board[0, 1] == Board[0, 2] && Board[0, 
0] != Status.Empty) ||
(Board[1, 0] == Board[1, 1] && Board[1, 1] == Board[1, 2] && Board[1, 0] 
!= Status.Empty) ||
(Board[2, 0] == Board[2, 1] && Board[2, 1] == Board[2, 2] && Board[2, 0] 
!= Status.Empty) ||
(Board[0, 0] == Board[1, 0] && Board[1, 0] == Board[2, 0] && Board[0, 0] 
!= Status.Empty) ||
(Board[0, 1] == Board[1, 1] && Board[1, 1] == Board[1, 2] && Board[0, 1] 
!= Status.Empty) ||
(Board[0, 2] == Board[1, 2] && Board[1, 2] == Board[2, 2] && Board[0, 2] 
!= Status.Empty) ||
(Board[0, 0] == Board[1, 1] && Board[1, 1] == Board[2, 2] && Board[0, 0] 
!= Status.Empty) ||
(Board[2, 0] == Board[1, 1] && Board[1, 1] == Board[0, 2] && Board[2, 0] 
!= Status.Empty)
)
	return true;
else
	return false;
Che prende in considerazione ogni combinazione vincente, oltre a 
controllare che almeno una cella della terzina non sia Vuoto (Status ï¿œ 
un enum). Ora, io vorrei implementare qualcosa che funzioni bene in ogni 
caso, tipo controllare i valori della matrice vicini all'ultimo toccato, 
ma mi viene in mente solo qualcosa di molto piï¿œ pizzoso di questo. E 
inoltre questo non mi da nemmeno la possibilitï¿œ immediata di sapere chi 
ha vinto (si fa lo stesso eh).
Grazie in anticipo per l'attenzione
saluti,
M


Dimenticavo, tra l'altro portarlo su larga scala (vedi altri giochi, con 
lo stesso principio ma tabelle piï¿œ grandi) diventa impossibile da 
implementare (giusto giusto generando il file con uno script...).
saluti,
M

[CUT]
Bho, mi viene un qualcosa del tipo controllo orizzontale, controllo 
verticale, controllo obliquo.
Quindi una brutta cosa + o - cosi'
if(Hchk() || Vchk() || Dchk()) theWinnerIs();
ed
Hchk(){
int maxCol=2;  // Numero di colonne esistenti
int maxRow=2;  // Numero di colonne esistenti
int tris=0;
int idxC=0;
int idxR=0;
int rc=0;
for(idxR=0;idxR<=maxRow;idxR++){
  tris=0;  // resetto il contatore del controllo sul tris per ogni riga 
analizzata
  for(idx=1;idx<=maxCol;idx++){
    if(Board[idxR,idx-1]==Board[idxR,idx] && Board[idxR,idx]!=Status.Empty)
       tris++;
  }
  if(tris==maxCol) rc=1; // rc=1 se trova il vincitore
  // in realta' cosi' facendo faresti un sacco di cicli inutili anche se hai 
gia' verificato che hai vinto. Con il tris lo puoi ignorare ma con giochi 
con tabelle sensibilmente grosse sarebbe un inutile perdita di cpu e tempo. 
Un ciclo while si addice di piu' al ciclo esterno ma ora non ho voglia di 
riscriverlo
}
return rc;
}
Non conosco C# quindi ho scritto un codice C like. La tabella Board devi 
averla inizializzata da qualche altra parte del programma e deve essere 
chiaramente accessibile alle funzioni, magari come parametro se non la vuoi 
come variabile globale.
L'ho scritta di getto quindi potrei averci messo degli errori ma il concetto 
credo si comprenda.
Ciao
Le funzioni Vchk e Dchk in modo analogo
-- 
 ************** (.)_(.) *******************
 Un amico ï¿œ uno che sa tutto di te e,
 nonostante questo, gli piaci
(E. Hobbard) 


Intanto ti ringrazio tanto, don't worry per il codice C (piuttosto per i 
nomi di variabile, eek!), lo mastico bene (non avevo semplicemente 
voglia di rimettere le mani su quella porzione di codice). Ora non sono 
in condizioni di provare, ma mi pare una cosa accettabile a colpo 
d'occhio, appena posso provo ad integrarlo al mio codice e vedo se le 
performance non si fskano troppo ;)
Tra l'altro ï¿œ anche facilmente adeguabile al controllo di file di 
elementi uguali superiori a 3: in tabelle piï¿œ grandi le condizioni di 
vittoria dovrebbero essere determinate da file piï¿œ lunge di elementi uguali.
In ogni caso il mio problema ï¿œ risolto, grazie ancora
saluti
M

 uguali*.
*Ponendo attenzione al fatto che:
x x x o x x
...
Nel caso in cui la condizione di vittoria fosse fila da 4, genererebbe 
la vittoria di X, a torto.
M

 ha vinto (si fa lo stesso eh).
In realtà sì.. è vincente proprio l'owner dell'ultima casella toccata
Per renderlo invece estendibile a qualunque grandezza di matrice come
ti è stato suggerito avrai bisogno di costrutti con cicli anziché
avere tutti i controlli hard-coded.
Io me lo implementerei così:
Una funzione che controlla che la casella[l][c] sia uguale alla casella
[l+loff][c+off] (controllando anche i boundaries):
inline bool check_single( int l, int c, int loff, int coff );
Una funzione che preso come parametri una delle 4 direzioni possibili
conti quante sono le caselle in fila uguali all'ultima toccata, ad
esempio:
( sia W il numero di caselle di fila valide per vincere, per tictactoe
W = 3)
bool check_row( int l, int c, int loff, int coff ) {
    int left,right;
    for( left = 1; left < W && check_single(l,c,-loff*left,-
coff*left); left++ );
    for( right = 1; right < W && check_single
(l,c,loff*right,coff*right); right++ );
    return left+right-1 >= W;
}
e infine la funzione che controlli le 4 direzioni a partire
dall'ultima casella toccata:
bool vincente =
        check_row(l,c,0,1) || // * H
        check_row(l,c,1,0) || // * V
        check_row(l,c,1,-1) || // * D1
        check_row(l,c,1,1); // * D2
Con questo algoritmo puoi controllare il vincente di tictactoe, ma
anche di forza4 ed eventuali forzaX con X>4 :P
PS per altri lettori: non datemi del Ciista-incallito che scrive
codice illeggibile, secondo questo è molto elegante :)
Ciauz
Mtc

> tris++;
else
  tris=0;
Ciao



Ah beh, allora dico anche io la mia :-)
Ho preferito la leggibilità alle prestazioni, tanto per il problema
alla mano dubito ci siano problemi di sorta. Altrimenti bisognerebbe
probabilmente memoizzare e vedere cosa succede (dynamic programming,
anyone?).
PS. meglio usare std::pair<> nell'array directions.
m.
-----------------------------------------------------
#include <sys/types.h>
#include <cstring>
#include <stdexcept>
class TicTacToe
{
	typedef unsigned int direction_t;
public:
	enum Player
	{
		cell_empty = 0,
		player_O,
		player_X
	};
	TicTacToe (size_t row_size = 3)
	  : row_size (row_size), board (new Player[row_size*row_size])
	{
	}
	TicTacToe (const TicTacToe& other)
	  : row_size (other.row_size), board (new Player[row_size*row_size])
	{
		std::memcpy (board, other.board, row_size*row_size*sizeof(Player));
	}
	~TicTacToe ()
	{
		delete [] board;
	}
	void clear ()
	{
		const Player *end = npos ();
		for (Player *it = board; it < end; ++it)
			*it = cell_empty;
	}
	void set_player (Player player, size_t index)
	{
		if (index > row_size*row_size)
			throw std::range_error ("You're trying to access cells outside of
the game board");
		board[index] = player;
	}
	Player get_player (size_t index) const
	{
		if (index > row_size*row_size)
			throw std::range_error ("You're trying to access cells outside of
the game board");
		return board[index];
	}
	bool check_victory (const Player player) const
	{
		if (player == cell_empty)
			throw std::invalid_argument ("Player used to check victory
conditions must be either X or O");
		// Directions are: horizontal, vertical,
		// diagonal LR, diagonal RL
		const direction_t directions[4][2] = { {0,1}, {0,row_size},
{0,row_size+1}, {row_size-1,row_size-1} };
		for (int i = 0; i < 4; ++i)
			if (check_victory_in (player, directions[i]))
				return true;
		return false;
	}
private:
	TicTacToe& operator= (const TicTacToe&);
	bool check_victory_in (const Player player,
                 const direction_t* start_and_stride) const
	{
		bool victory = true;
		Player *it = board + start_and_stride[0];
		for (size_t i = 0; i < row_size; ++i)
		{
			if (!(victory &= (*it == player)))
				return false;
			it += start_and_stride[1];
		}
		return true;
	}
	Player* npos () const
	{
		return board + row_size*row_size;
	}
	size_t row_size;
	Player *board;
};
int main ()
{
	TicTacToe ttt;
	size_t moves[] = { 0+2, 3+1, 6+0 };
	for (int i = 0; i < 3; ++i)
		ttt.set_player (TicTacToe::player_X, moves[i]);
	return ttt.check_victory (TicTacToe::player_X);
}

         return ttt.check_victory (TicTacToe::player_X);
Si ma è un caso che check_victory ti ritorna true =) La tua soluzione
controlla le 4 direzioni ma soltanto per la prima riga, la prima
colonna, e le due diagonali principali.
Ad occhio se metti moves[] = { 3,4,5 } ritorna erroneamente false.
Inoltre in una tabella piu grande di 3x3 io credo che vorrei
controllare tutte le diagonali e non soltanto quelle principali
(definendo il numero di caselle in fila per vincere)