Brute Force αλγόριθμος τρίλιζας

[migf1]

Την Κυριακή το απόγευμα (χτες) ψιλοβαριόμουν και είπα να φτιάξω για πλάκα μια τρίλιζα ( σε C φυσικά ) χωρίς όμως να χρησιμοποιήσω τον κλασικό minmax+alpha pruning αλγόριθμο του game-tree (αυτό το είχα φτιάξει όταν ήμουν φοιτητής ).

 

Το έκανα με τον brute-force αλγόριθμο, μια εκδοχή του οποίου μπορεί να βρει κανείς στην Wikipedia.

 

Τα 2 πρώτα βήματα είναι εύκολα! Υπάρχουν διάφοροι τρόποι, εγώ τα υλοποίησα με bitwise AND ως εξής:

 

Έβαλα σε όλα τα τετράγωνα του ταμπλό δυνάμεις του 2, δηλαδή...

 

>
1	2 	4
8	16	32
64	128	256

και κάθε φορά που ένας παίκτης παίζει σε κάποιο τετράγωνο προστίθεται σε ένα unsigned πεδίο της δομής του (που το ονομάζω win-status και ξεικάνει με τιμή 0) τον αριθμό που υπάρχει στο συγκεκριμένο τετράγωνο.

 

Οπότε, αν οι θέσεις του ταμπλό έχουν αριθμηθεί για παράδειγμα από το 0 έως το 8 ...:

>
0	1	2
3	4	5
6	7	8

τότε αν ο παίκτης έχεις ήδη παίξει ας πούμε στα τετράγωνα 1, 4 και 8 τότε το win-status του είναι: 2+16+256 = 274.

 

Εφόσον το συνολικό πλήθος νικητήριων συνδυασμών στην τρίλιζα είναι 8 (3 γραμμές +3 στήλες + 2 διαγώνιοι) με τα αντίστοιχα αθροίσματά τους τα παρακάτω:

>
1 + 2 + 4	= 7	// γραμμή 0
8 + 16 + 32	= 56	// γραμμή 1
1 + 8 + 64	= 73	// στήλη 0
4 + 16 + 64	= 84	// δεξιά διαγώνιος
2 + 16 + 128	= 146	// στήλη 1
1 + 16 + 256	= 273	// αριστερή διαγώνιος
4 + 32 + 256	= 292	// στήλη 2
64 + 128 + 256	= 448	// γραμμή 2

τότε για να δούμε αν ένας παίκτης έχει κερδίσει, εξετάζουμε αν το bitwise AND του win-status του παίκτη με οποιοδήποτε από τα νικητήρια αθροίσματα ισούται με αυτό το νικητήριο άθροισμα.

 

Ο παρακάτω συγκεντρωτικός πίνακας το κάνει πιο ξεκάθαρο...

 

>
1	2	4	| 7
8	16	32	| 56
64	128	256	| 448
-------------------------------- 
84	73	146	292  	273 

 

Και κάπου εδώ τελείωσαν τα εύκολα!

 

Συγκεκριμένα αντιμετώπισα (κι αντιμετωπίζω) μεγάλο πρόβλημα στην πρόληψη για πιθανό fork του αντιπάλου (όπου fork η διπλή απειλή τρίλιζας). Το πρόβλημα είναι πως αποτελεί εξαίρεση ("ανωμαλία") στην ακολουθία των γενικών κανόνων που διέπουν το παιχνίδι σε οποιαδήποτε άλλη περίπτωση.

 

Όποιος έχει όρεξη μπορεί να διαβάσει μια εξαιρετική ανάλυση του συγκεκριμένου προβλήματος, εδώ: http://www.cs.berkel.../v1ch6/ttt.html (στην ενότητα Strategy, τα βήματα 3, 4, 4a, 4b.

 

Δυστυχώς, η προτεινόμενη λύση στο παραπάνω link βασίζεται στην χρήση συγκεκριμένων δομών (λίστες & arrays) που για να τις υιοθετήσω πρέπει να αλλάξω όλο το πρόγραμμα. Μοιάζει κάπως με μια άλλη προτεινόμενη λύση (πάντα χωρίς χρήση game-tree) η οποία χρησιμοποιεί pattern matching, εξετάζοντας μονάχα 3 τετράγωνα του ταμπλό, το οποίο και περιστρέφει μέχρι 4 φορές: http://webster.cs.uc...cToe/ttt_1.html (υλοποιημένη σε assembly). Αυτή χρειάζεται ακόμα μεγαλύτερες αλλαγές στο πρόγραμμα που έχω φτιάξει.

 

Βασικά το πρόγραμμα το έχω τελειώσει (με 3 επίπεδα δυσκολίας και δυνατότητα 4 ειδών game-play: Human vs CPU, CPU vs Human, CPU vs CPU και Human vs Human) με τη διαφορά πως το θέμα του fork το έχω υλοποιήσει με ειδικό έλεγχο που εξετάζει brutally συγκεκριμένες θέσεις X και O στο ταμπλό...

 

 

 

>
/* ---------------------------------------------------------------------
*
* ---------------------------------------------------------------------
*/
Bool BAD_ai_hard_defened_fork(
int pordcpu,
int pos,
BrdSquare simboard[ BRD_SIZE],
Player players[2],
int *rank
)
{
unsigned wsopp = players[ 1-pordcpu ].wstatus;		/* opponent's win-status  */
enum CharDisplay cdispcurr = players[ pordcpu ].cdisp;	/* current player's cdisp */

if (
( (pos == 2 || pos == 6) && simboard[4].cdisp == cdispcurr && wsopp == 257 )
|| ( (pos == 0 || pos == 8) && simboard[4].cdisp == cdispcurr && wsopp == 68 )
){
	*rank = -45;
}
if ( (pos == 0 || pos == 2 || pos == 6 || pos == 8)
&& simboard[4].cdisp == cdispcurr
&& (wsopp == 66 || wsopp == 258 || wsopp == 12|| wsopp == 264 || wsopp == 129 || wsopp == 132 || wsopp == 96 || wsopp == 32)
){
	*rank = -45;
}

return TRUE;
}

 

 

 

Κάτι που όχι μόνο είναι "απαράδεκτο" αλγοριθμικά, αλλά προκαλεί και συγγραφή κακάσχημου κώδικα!

 

Συμπτωματικά βρήκα την υλοποίηση κι άλλου ένα Έλληνα, σε C++, που δίχως να χρησιμοποιεί game-tree, χρησιμοποιεί μια minmax evaluation συνάρτηση (σαν heuristic) για να κάνει simulate τις κινήσεις της CPU και του παίκτη, βαθμολογώντας το κάθε τετράγωνο κάθε φορά, επιλέγοντας στο τέλος ως επόμενη κίνηση εκείνο με τη μεγαλύτερη βαθμολογία! Πάνω λοιπόν που χάρηκα ότι βρήκα έτοιμη μια φόρμουλα, τη δοκιμάζω για να διαπιστώσω με μεγάλη μου λύπη ππως ούτε αυτή λαμβάνει υπόψη της την περίπτωση των forks. Κατεβάζοντας μάλιστα τον κώδικά του, διαπίστωσα πως κι αυτός καταφεύγει στη λύση του ειδικού ελέγχου, με τον ίδιο κακάσχημο κώδικα με τον δικό μου

Αποφεύγει μάλιστα να το σχολιάσει στο blog του, και απλά αναφέρεται σε αυτή τη συνάρτηση στα γρήγορα, χωρίς εξήγηση, λέγοντας απλά πως κάνει τη CPU καλύτερο παίκτη.

 

Το blog του για όποιον ενδιαφέρεται, είναι εδώ: http://www.codercast...gence-opponent/

 

Όποιος ξέρει ή ενδιαφέρεται να προτείνει λύση στο θέμα του fork ενταγμένη αρμονικά σε γενικότερο αλγόριθμο (και όχι ως brutal special case) αλλά απλούστερη από τις παραπάνω, ας την παραθέσει.

[bnvdarklord]

Δεν μπόρεσα να βρώ περισσότερα από 5 καταστάσεις fork(x4 περιστροφές):

0 4 6, 0 2 6, 0 3 4, 0 1 4, 0 1 5 (αν τα αριθμήσεις 0-8)

 

Τότε ή απλά υπάρχουν πολύ περισσότερες οπότε αυτό δεν δουλεύει, είτε ειναι αυτές(αντε και αλλη μία) και μπορείς ξέροντας τες από πρίν να τις αποτρέψεις.

[migf1]

Θέλεις δηλαδή να με βάλεις να κάνω περιστροφές του ταμπλό;

[bnvdarklord]

Θα μπορούσες απλά να βρείς τα αθροίσματα των 5x4 = 20 αυτών fork καταστάσεων και να τα θεωρίσεις win-states έτσι ώστε να τα αποτρέπει το CPU με τον αλγόριθμο που αποτρέπει τα πραγματικά win-states.

[migf1]

Θα μπορούσες απλά να βρείς τα αθροίσματα των 5x4 = 20 αυτών fork καταστάσεων και να τα θεωρίσεις win-states έτσι ώστε να τα αποτρέπει το CPU με τον αλγόριθμο που αποτρέπει τα πραγματικά win-states.

Κάτι τέτοιο κάνει και τώρα η συνάρτηση που έβαλα σε spoiler στο αρχικό ποστ, με λίγο διαφορετικό τρόπο... εννοώ δεν έχει διαφορά στη φιλοσοφία προσέγγισης (brutal εξαίρεση είναι κι αυτό).

 

 

Στο link που πόσταρα με την υλοποίηση σε logo, κάνει κάτι έξυπνο: σε κάθε κίνηση μετατρέπει το ταμπλό σε 8 triples (τριπλέτες) όπως τα λέει, 3 για τις γραμμές, 3 για τις στήλες και 2 για τις διαγώνιους. Στην κάθε τριπλέτα αντιστοιχεί το υπάρχον σύμβολο του αντίστοιχου τετραγώνου (Ο, Χ ή η αρίθμησή του).

 

Για παράδειγμα, αν η 1η γραμμή περιέχει με τη σειρά ένα X, ένα Ο κι ένα κενό τετράγωνο, η τριπλέτα της είναι: xo3 (3 είναι η αρίθμηση του 3ου τετραγώνου, την ξεκινάει από 1 αυτός αντί από 0 που το έχω εγώ). Οπότε για να βρει πιθανά τετράγωνα που δημιουργούν fork για κάποιον παίκτη, ψάχνει για τριπλέτες που αποτελούνται από 1 σύμβολο του παίκτη και 2 νούμερα. Τριπλέτες με κάποια κοινά νούμερα αρίθμησης έχουν το κοινό τους νούμερο να αντιστοιχεί σε τετράγωνο που δημιουργεί fork. Πολύ έξυπνο, αλλά πρέπει να αλλάξω τα πάντα στο υπάρχον πρόγραμμά μου

 

Κοιτάω τώρα να φτιάξω μια συνάρτηση που θα της περνάω θέση ταμπλό κι ένα σύμβολο (cdisp τα λέω στον κώδικά μου, από το "char displayed") και θα μου μετράει πόσες νικητήριες γραμμές/στήλες/διαγώνιοι του συγκεκριμένου σύμβολου περιέχουν τη συγκεκριμένη θέση. Αν συνολικά είναι πάνω από 2 τότε αυτή η θέση δημιουργεί fork (ελπίζω να είναι σωστό ως σκέψη)!

 

Οποιαδήποτε άλλη ιδέα ευπρόσδεκτη!

[bnvdarklord]

Σωστό, και πιο αυτοματοποιημένο.

[migf1]

Τζίφος, έπεσα πάλι στην ίδια τρύπα του αλγόριθμου

 

Θα το αφήσω έτσι, δεν μαμιέται. Θα βάλω σχόλια στον κώδικα και θα τον ποστάρω αύριο (τελικά game-trees και ξερό ψωμί, θα το είχα έτοιμο από χτες )

[migf1]

... Θα βάλω σχόλια στον κώδικα και θα τον ποστάρω αύριο...

 

Τελικά ούτε σχόλια του έβαλα ούτε το πόσταρα

 

Τώρα όμως βρήκα λίγο χρόνο και το έκανα port από κονσόλα σε GTK+2. Βασικά διατήρησα και την κονσόλα για ταυτόχρονο output παράλληλα με το γραφικό περιβάλλον (την κονσόλα την ανοίγει από default το GTK+2, κι άμα δεν τη θέλεις την αφαιρείς στον linker με -mwindows).

 

Τα βρήκα λίγο μπαστούνια, αφενός γιατί είχα πάρα πολύ καιρό να ασχοληθώ με event-driven προγραμματισμό γενικότερα κι αφετέρου επειδή είχα ακόμα περισσότερο καιρό να προγραμματίσω σε GTK ειδικότερα.

 

Ήταν και το port στη μέση, οπότε ο κώδικας θα μπορούσε να είναι και πιο απλός, αλλά δεν βαριέσαι... καλό είναι κι έτσι. Ακόμα το έχω σε ένα μόνο αρχείο, χωρίς makefiles, κλπ... αν προλάβω θα το χωρίσω σε source modules και θα ποστάρω τον κώδικα σήμερα, αλλιώς τις επόμενες 2-3 μέρες.

 

Προς το παρόν ποστάρω μερικά screenshots, για να υπάρχει μια γενική ιδέα...

 

 

Την εικόνα τη βρήκα στην Wikipedia και την έσπασα σε κομμάτια,... υπάρχουν κάποιες ατέλειες γιατί η ορίτζιναλ είχε strike-through μια νικητήρια τριάδα στην αριστερή διαγώνιο (π.χ. φαίνεται στις ενώσεις του πλέγματος αν το παρατηρήσετε καλά).

 

Α, θέλω να βάλω και Ελληνική μετάφραση (άμα βρω πως γίνεται το internationalization στο GTK+ )

[geo1st487]

Προς το παρόν ποστάρω μερικά screenshots, για να υπάρχει μια γενική ιδέα...

 

 

Την εικόνα τη βρήκα στην Wikipedia και την έσπασα σε κομμάτια,... υπάρχουν κάποιες ατέλειες γιατί η ορίτζιναλ είχε strike-through μια νικητήρια τριάδα στην αριστερή διαγώνιο (π.χ. φαίνεται στις ενώσεις του πλέγματος αν το παρατηρήσετε καλά).

 

Α, θέλω να βάλω και Ελληνική μετάφραση (άμα βρω πως γίνεται το internationalization στο GTK+ )

 

Τελικά τα screenshots ειναι απο την εφαρμογη σου ή απο την Wikipedia; Σε ποια εικονα αναφερεσε οταν λες οτι την βρηκες στη Wikipedia;

[migf1]

Τα screeshots είναι το προγραμματάκι της τρίλιζας που έφτιαξα, απλώς η εσωτερική εικόνα που χρησιμοποίησα είναι παρμένη από την Wikipedia: http://nrm.wikipedia...tic_tac_toe.png

 

Btw, το ξανάπιασα σήμερα να του βάλω σχόλια και να το χωρίσω σε source modules και να το ποστάρω.Με την ευκαιρία βελτίωσα και την εσωτερική δομή του και τα γενικότερα abstractions του, χωρίς αυτό να σημαίνει πως είναι όπως πρέπει να είναι (αυτά είναι αποτελέσματα βιασύνης, όταν δεν κάθεται κανείς να σχεδιάσει πρώτα σε χαρτί πριν αρχίσει να γράφει κώδικα).

 

Τελικά δεν θα το χωρίσω σε source modules όμως. Χώρισα τις συναρτήσεις σε OOP like κατηγορίες (χρήσης και ονομάτων) και θα το αφήσω έτσι... μου περίσσεψαν και μερικές χωρίς κατηγορία

 

Τα σχόλια θέλω να τελειώσω (μαζί με τον κώδικα θα βγουν περίπου 2200 γραμμές, με καθαρό κώδικα σχεδόν το μισό). Θέλω να γράψω κι ένα μικρό readme που να λέει πως να το κάνετε compile στα Windows, γιατί θέλει το runtime του GTK+2 (οι Linux-άδες το έχουν έτοιμο λογικά).

 

Εγώ πάντως σε Windows το έγραψα και compile το κάνω είτε με mingw32 είτε με Pelles-C (και τα 2 free και ισχυρότατα).

 

Σε Windows, για να τρέξει το εκτελέσιμο χρειάζεται να κατεβάσει κανείς το GTK+2... βασικά αυτό εδώ: http://ftp.gnome.org...11122_win32.zip, το οποίο το ξεζιπάρει σε όποιον φάκελο επιθυμεί, κατά προτίμηση σε κάποιον που υπάρχει ήδη στο PATH των Windows (αλλιώς πρέπει απλά να προσθέσει τον φάκελο μόνος του στο PATH).

 

Π.χ. αν ξεζιπάρετε στο: C:\gtk2 πρέπει να προσθέσετε στο PATH των Windows τον φάκελο: C:\gtk2\bin (ίσως και το C:\gtk2, εγώ τα έχω και τα 2 αλλά δεν θυμάμαι αν χρειάζονται και τα 2).

 

Αν ξέρετε ήδη πως να κάνετε compile με GTK+ ή βαριέστε να με περιμένετε να τελειώσω με τα σχόλια και τα readme ή έστω απλά σας ενδιαφέρει να δείτε πως είναι μέχρι στιγμής κώδικας και resource file, το επισυνάπτω με executable από Pelles-C...

 

gtk_tic.zip

[geo1st487]

Στο screenshot Preferences τα έχεις ολα στα αγγλικα εκτος απο το κουμπι που λεει ενταξει.

 

Δεν δοκιμασα την τριλιζα που εφτιαξες αλλα εχω παρατηρησει το παρακατω οταν επαιζα παλια τριλιζα

 

Αν οι παικτες μετα το κεντρο βαζουν στις γωνιες τοτε το παιχνιδι τελειωνει ισοπαλια (εκτος αν καποιος εχει 2 ιδια στη σειρα και ο αλλος δεν το δει για να το κλεισει).

Αν το γνωριζουν αυτο οι παικτες τοτε το παιχνιδι θα τελειωνει παντα ισοπαλια.

[migf1]

Στο screenshot Preferences τα έχεις ολα στα αγγλικα εκτος απο το κουμπι που λεει ενταξει.

Εγώ όλα στα Αγγλικά τα έχω, αλλά επειδή στα Windows μου έχω τα Regional Settings ρυθμισμένα για Ελλάδα, όλα τα system dependent strings βγαίνουν αυτόματα στην γλώσσα που είναι ρυθμισμένο το λειτουργικό.

 

Δεν δοκιμασα την τριλιζα που εφτιαξες αλλα εχω παρατηρησει το παρακατω οταν επαιζα παλια τριλιζα

 

Αν οι παικτες μετα το κεντρο βαζουν στις γωνιες τοτε το παιχνιδι τελειωνει ισοπαλια (εκτος αν καποιος εχει 2 ιδια στη σειρά και ο αλλος δεν το δει για να το κλεισει).

Αν το γνωριζουν αυτο οι παικτες τοτε το παιχνιδι θα τελειωνει παντα ισοπαλια.

Η μετάφραση σε αλγόριθμο είναι δυστυχώς πολύ πιο δύσκολη. Κανονικά θέλει minmax gametree αλλά εγώ το 'χω κάνει με μια παραλλαγή του brutal αλγόριθμου, χωρίς bakctracking (που με αναγκάζει να καταφύγω σε ακόμα πιο brutal tests για το μπλοκάρισμα της πιθανότητας να απειλήσει με διπλή τρίλιζα ο αντίπαλος (fork).

 

Αυτά μόνο για το Expert επίπεδο. Στο Medium δεν κοιτάει καθόλου για forks, ενώ στο Novice παίζει τελείως στην τύχη.

[geo1st487]

Εγώ όλα στα Αγγλικά τα έχω, αλλά επειδή στα Windows μου έχω τα Regional Settings ρυθμισμένα για Ελλάδα, όλα τα system dependent strings βγαίνουν αυτόματα στην γλώσσα που είναι ρυθμισμένο το λειτουργικό.

 

Αυτο με τα Regional Settings συμβαινει με τα MessageBox οπως αυτο που βλεπω στην τριτη εικονα που το μηνυμα του MessageBox ειναι στα αγγλικα και τα κουμπια γραφουν ναι και οχι.

 

Η φορμα Preferences φαινεται πως δεν ειναι καποιο MessageBox αλλα μια φορμα πανω στην οποια εβαλες και το κουμπι που γραφει ενταξει. Αν δουλευεις με οπτικο προγραμματισμο μπορεις να ρυθμισεις τα properties του κουμπιου οπως το κειμενο και να το ορισεις ακριβως το κειμενο του στα ελληνικα ή στα αγγλικα.

 

Η μετάφραση σε αλγόριθμο είναι δυστυχώς πολύ πιο δύσκολη. Κανονικά θέλει minmax gametree αλλά εγώ το 'χω κάνει με μια παραλλαγή του brutal αλγόριθμου, χωρίς bakctracking (που με αναγκάζει να καταφύγω σε ακόμα πιο brutal tests για το μπλοκάρισμα της πιθανότητας να απειλήσει με διπλή τρίλιζα ο αντίπαλος (fork).

 

Αυτά μόνο για το Expert επίπεδο. Στο Medium δεν κοιτάει καθόλου για forks, ενώ στο Novice παίζει τελείως στην τύχη.

 

Αυτο που θελω να πω ειναι οτι και στο Expert επιπεδο, αν ο παικτης που παιζει με αντιπαλο τον υπολογιστη βαζει στις γωνιες τοτε δεν προκειτε ποτε να χασει απο τον υπολογιστη διοτι δεν θα δωσει την ευκαιρια στον υπολογιστη να απειλησει με διπλη τριλιζα.

[migf1]

Ναι έτσι είναι, μπορείς να τα κάνεις όλα Ελληνικά αν το θέλεις, αλλά δεν το βρίσκω κακό να βγαίνουν αυτά τα strings στη ρυθμισμένη γλώσσα του συστήματος. Στο GTK+ έχεις την επιλογή να ΜΗΝ χρησιμοποιήσεις stock widgets, αλλά τα κουμπιά και κάποια menu-items τα έχω επιλέξει επίτηδες ως stock items, γιατί αλλιώς θα έπρεπε να ρυθμίσω χειροκίνητα κάποιες ιδιότητές τους (όπως π.χ. τα εικονίδιά τους) και... βαριόμουν

 

Όσο για το gameplay, και πάλι ναι... όταν οι 2 παίκτες παίζουν ιδανικά, το παιχνίδι λήγει ισόπαλο. Αυτό επιδεικνύεται εύκολα βάζοντας στο πρόγραμμα να παίζουν 2 CPU μεταξύ τους, σε Expert level... όλα τα παιχνίδια τους λήγουν ισόπαλα

 

Σε κάνα 2ωρο υπολογίζω να το έχω ποστάρει κομπλέ το πρόγραμμα, με αναλυτικό readme τόσο για τα abstractions του κώδικα. όσο και οδηγίες για το compiling, καθώς και οδηγίες & links για εγκατάσταση του GTK+ και του Glade στα Windows.

 

Bασικά σε λόγια φαίνονται πολύ περισσότερα από ότι πραγματικά είναι στην πράξη. Ακόμα κι αν δεν υπάρχει απολύτως τίποτα εγκατεστημένο στο σύστημα, όλο κι όλο είναι: 3 downloads (code::blocks, gtk+, glade-3) ισάριθμα ξεζιπαρίσματα σε φακέλους (της αρεσκείας του καθένα) και δημιουργία 2-3 environment variables.

 

EDIT:

 

Και προφανώς αυτά γίνονται μία μόνο φορά και από κει και πέρα μπορείς να τρέχεις οποιαδήποτε GTK+ εφαρμογή και κυρίως να φτιάχνεις προγράμματα με GTK+ aware γραφικό περιβάλλον

[migf1]

Δεν μπορώ να επεξεργαστώ πλέον το αρχικό μήνυμα, οπότε τα βάζω εδώ.

 

Τελείωσα με τα σχόλια και το Readme οπότε παραθέτω την τρίλιζα ολοκληρωμένη. Επιδέχεται αρκετές βελτιώσεις ακόμα, μερικές από τις οποίες τις αναφέρω στο Readme, οπότε θα τον ξαναπιάσω κάποια στιγμή τον κώδικα για να το βελτιώσω.

 

gtk_tic.zip

 

Περιέχει...

 

• τον κώδικα (2256 γραμμές, μαζί με τα σχόλια, σε ANSI C89 + GTK+2)
• δυο Win32 εκτελέσιμα (ένα με console window, compiled με MingW32 GCC 4.6.2, κι ένα χωρίς console window, compiled με Pelles C 6.00)
• τον φάκελο \gui με τις bitmap εικόνες και 2 glade files (ένα Αγγλικό κι ένα πειραματικό Ελληνικό)
• Readme.txt (σημειώσεις για τον κώδικα και λεπτομερείς οδηγίες για compilation σε διάφορες πλατφόρμες,αλλά με έμφαση στα Windows)

Αν προτιμάτε να διαβάζετε στο insomnia, βάζω σε spoiler το Readme.txt (είναι στα Αγγικά και είναι αρκετά μεγάλο)...

 

 

 

/* ========================================================================

* PROJECT : TIC-TAC-TOE Overkill

* AUTHOR : migf1 <[email protected]>

* FILE : gtk_tic.c

* LANGUAGE : C (C89 + GTK+2)

* PLATFORM : Cross-platform

*

* DESCRIPTION : A classic tic-tac-toe game featuring:

* - cross-platform GUI ( GTK+2 )

* - 4 modes ( Human vs CPU, CPU vs Hum, CPU vs CPU, Hum vs Hum )

* - 3 levels of difficulty ( Expert, Casual, Novice )

*

* LICENSE : No License! Consider it freeware, public domain or whatever, and do

* whatever you want with it. All I ask is to reference my name and

* include the original package of the game if you decide to redistribute

* it. Oh, I'll be happy to see it ported or improved, so drop me a note

* if you feel like it

* ========================================================================

*/

 

 

==============================================================================

I M P L E M E N T A T I O N N O T E S

==============================================================================

 

The notes in this section will hopefully help you to get around the source code of this little game, although most of the source code contains commentary.

 

First I need to... confess that I was too lazy to properly design the structure of the program in a piece of paper before coding it, so things are not that well organized as they should (but they are not too bad either).

 

 

Environments

------------

 

The general idea was to separate the GUI from the game itself, so the action takes place mostly in two environments: the gaming environment, represented by the custom type: Game, and the GUI environment, represented by the custom type: Gui. Those two environments are abstract siblings inside the general environment of the program, represented by the custom type: GenEnv.

 

The general environment is responsible for controlling the interaction between the game and the GUI environments, while performing higher level tasks. As you can see in the source code, things didn't go exactly as intended, because as I explained above I was too lazy to thoughtfully prepare the design of the program before getting to code it. As a result, I've ended up with a few stray functions, not clearly belonging to any distinct environment. I left them "floating" around, tagging their names with the prefix "util_" (meaning: utility functions).

 

Speaking of prefixes, gui related functions have their names prefixed with "gui_", while game related functions have their names prefixed with "game_". Functions related to the general environment, have their names prefixed with "env_".

 

The gaming environment ( Game ) has a child environment, represented by the custom type: GamePlay, with related functions having the "gameplay_" prefix in their names. This GamePlay environment is not what its name may suggest at a first glance: it does not refer to the general game play. Instead, it refers to a single round inside a game (a single play). So a perhaps more intuitive name for this custom type would be something like: Round, but I started the code using Play as the name, later changed it to GamePlay, and I figured that once explained it is not that misleading after all.

 

There is more data-structure nesting going on in the source code (for example the custom types PlayBoard and Player, belonging to the GamePlay environment, or the custom types GamePrefs and GamePlaystats belonging to the Game environment) but those can be hardly thought as complete environments by themselves. So just think of them simply as interior parts of the basic environment they belong to.

 

 

Object Oriented Approach

------------------------

 

The above design is an Object Oriented approach, and actually most of those functions do operate on pointers to abstract objects, which are passed at the start of the argument list of the functions. So "env_" functions have their 1st argument being of type GenEnv *, while "game_" functions have their 1st argument being of type: Game *, and "gameplay_" functions have their 1st argument being of type: GamePlay *, and so on.

 

Exceptions to this OO convention are the "util_" and "debug_" functions, for the reasons I explained earlier (stray functions).

 

 

AI Algorithm

------------

 

Now a few words about the algorithms used for the 3 levels of AI strength. As you may already know, the most popular (and recommended) way to implement the Tic-Tac-Toe AI is using a game-tree, along with minmax heuristics, with or without alpha-pruning (better with).

 

I don't remember if I have mentioned it so far, but sometimes I can be very lazy! That's why I didn't took that route in the first place, for the Expert level. It turned out that if I was, I would have finished the game a lot earlier, and most importantly with a much cleaner AI code.

 

Nevertheless I did it with a variation of the brutal algorithm, using (as it again turned out to be) a not-that-good heuristic function for evaluating the board. Furthermore, I didn't implement backtracking when evaluating the board, thus I was forced to add a really ugly, brutal and frankly a quite messy function for blocking opponent forks. That function is called: util_ai_rank_fork_adjustment()... I didn't even manage to properly embed it into any of my environments (the latter holds for the board evaluation function too: util_ai_eval_board() ).

 

Anyway, at least it works

 

When in Casual strength level (Medium difficulty) the AI does not deal with opponent forks at all. It only checks for squares that lead to either an own or an opponent win. When in Novice strength level (Easy) the AI plays completely randomly!

 

 

GUI Implementation

------------------

 

For implementing the GUI I chose GTK+2, the de-facto cross-platform API for implementing graphical user interfaces with C. Since I have coupled it with standard C89 code, you can compile the source code on a vast variety of platforms, without changing anything.

 

On the other hand, it requires some extra effort for installing GTK+2 and all its dependencies on platforms that do not have it pre-installed, most notably Windows. The same holds for Glade, the RAD tool for managing the equivalent of what is known as a GUI resource file in Windows (in GTK+ it's a plain XML file, usually created and graphically managed by Glade).

 

Fortunately, it's quite easy to install everything needed, by downloading convenient bundles containing Windows binaries (although they are a bit behind in development, compared to their Unix/Linux counterparts). Further below in this text I point you to the right direction & places for getting and setting up everything you need to compile the game (or any other GTK+ application) on Windows. It's far more easy than it may look when reading my instructions, because I try to make things clear even to people who have no or very little experience.

 

In any case, if you have no experience with this kind of stuff, I would recommend to install the cross-platform Code::Blocks IDE, which comes with the MinGW32 GCC toolchain embed in a Windows specific installer (more on this later).

 

As far as the source code is concerned, regarding the GUI, all graphical elements of the game are stored in the file: gui\gtk_tic_en.glade (obviously you need Glade (version 3.x) to open it, in case you want to take a look at it... you may open it with any text editor though, since it's just an XML file).

 

All those graphical elements are loaded into memory via the function: gui_init(). This function initializes the GTK+ API and then it loads the needed graphical elements into the Gui environment of the game, by reading the glade file via a local GtkBuilder object. This GtkBuilder object is unreferenced just before the function returns control back to the main() function of the program.

 

Actually this function serves as a convenient abstraction for loading GUI elements, making it a bit more easy to port the program into a different GUI. That being said, the Gui environment itself is far from being properly abstracted, because I didn't took the time to implement all the needed functions for such a task. There are quite a few GTK+ specific functions that are called directly in several places (for example, to activate/de-activate menu items) which should be abstracted into more generic functions. Most probably I will finish it up in next versions.

 

As a final note about the GUI, there is a second glade file, called: gtk_tic_el.glade inside the \gui folder. This is the Greek translation of the English file, but Greek is not properly supported in the source code just yet (there are a couple of references inside the code, but they are actually disabled).

 

The reason is that currently I'm brutally updating some text labels of the GUI from within the source code, using standard string-handling functions, such sprintf(), strncpy() etc. Some of those functions are not getting along with UTF8 encoded strings, since they are primarily designed to work with 8-bit ASCII codes. Now, the Pango library used by GTK+ for text formatting on the GUI, expects valid UTF8 encoded strings (7-bit ASCII is valid UTF8, 8-bit is not).

 

To make a long story short, the most viable fix for supporting Greek along with English is to put the strings of both languages into the glade file (most probably in a hidden object) load them into my Gui environment and then use them from there whenever I need to dynamically update a GUI text label.

 

I'm planning to do so in next version of the game. In the meanwhile, you may rename the file: gtk_tic_el.glade into gtk_tic_en.glade if you want most of the GUI show up in Greek (make sure you keep a backup of the file: gtk_tic_en.glade first). Of course the dynamically updated GUI strings will still show up in English.

 

 

Console Output

--------------

 

The game does utilize a GUI but it also uses the console to mirror its output. By default all GTK+ applications open a console window, along with the main window of the application. It is left to the application whether to use the console or not. Tic-Tac-Toe Overkill uses it (GTK+ uses the console for outputting error messages, which can prove quite handy for end users too).

 

If you don't like this kind of behaviour, then add the GCC command line flag: -mwindows when compiling the source code. This will prevent the console window from being opened.

 

However, when in Human vs CPU mode, the game clears the board as soon as any of the players wins the current play (round). By having the console window open, you will be able to actually see what the winning combo was, before the board got cleared.

 

And that's the end of this section. In the rest of the file I will show you how to setup the GTK+ environment on Windows, including Glade, and I will show you how to compile GTK+ applications with the most popular free compilers & IDEs on a variety of platforms (mostly on Windows, though).

 

 

 

=============================================================================

I N S T A L L I N G G T K +

==============================================================================

 

GTK+ comes pre-installed on most Unix/Linux distributions, so here I will only explain briefly how to install it on systems running Windows 2000 or newer.

 

If your Unix/Linux installation does not include GTK+, please visit the official GTK+ site for instructions on how to download and/or build it.

 

The most recent versions of GTK+ at the moment of this writing were:

 

ver 3.2 for GNU/Linux/Unix:

http://www.gtk.org/download/linux.php

 

ver 2.24.8 for Win32 (for for the all-in-one-bundle):

http://www.gtk.org/download/win32.php

 

ver 2.22 for Win64 (experimental using MinGW-w64)

http://www.gtk.org/download/win64.php

 

for Mac OSX:

http://www.gtk.org/download/macos.php

 

For the always most recent versions of GTK+, visit the downloads page of the official GTK+ site:

 

http://www.gtk.org/download/

 

 

Setting up the GTK+ All-In-One Bundle on Windows

------------------------------------------------

 

If you intend to develop GTK+ applications (and of course being able to compile the source code of the TicTacToe Overkill) you need the GTK+ developer packages.

 

GTK+ depends on a few other libraries (namely: glib, atk, pango and gdk-pixbuf) so unless you already have them installed on your system, you must download and set them up too (Windows do NOT have them by default).

 

Fortunately, the GTK+ project guys release very convenient all-in-one bundles, containing everything, arranged in the correct folder-tree too!

 

Ok, here are the 3 simple steps to follow...

 

1. The first thing to do is to download the latest all-in-one-bundle

(see the links above) and extract it into any folder you like.

Personally, I use C:\unix\gtk+ but most people use C:\GTK2

Your are completely free to choose any folder you wish, but for

the shake of this text I'll assume you extracted it into:

C:\GTK2

 

2. Next you need to create the following Windows environment variables:

 

GTK_HOME = C:\GTK2

PKG_CONFIG_PATH = C:\GTK2\LIB\pkgconfig

 

(replace C:\GTK2 with the folder into which you extracted the

all-in-one-bundle)

 

NOTE: *** If any of the above environment variables already ***

*** exist on your system, do NOT delete their previous ***

*** contents. Simply add the above values, separating ***

*** them from the old ones with a semi-colon: ; ***

*** Preferably, add the new values BEFORE the old ones ***

 

3. The last step is to add GTK+2's binaries folder: C:\GTK2\BIN into

your Windows' PATH environment variable.

 

Again, do NOT delete any previous contents of your PATH. Simply add

C:\GTK2\BIN to the already existing contents, separating it with a

semi-colon character: ;

 

 

In the rare case you do not know how to create/modify environment variables on Windows, right-click on My Computer icon, then select Properties, and in the Advance tab select Environment variables:

 

My Computer (right-click) -> Properties -> [Advanced | Environment vars..]

 

You'll see 2 lists of environment variables: User and System. To have your modifications affect all users on your machine, do them in the System list of variables. To affect only the current user (advisable), do your modifications to the User list of variables.

 

To give you a better hint, the following screenshot shows my own setup:

 

http://img811.images...703/environ.jpg

 

 

 

Setting up the GTK+ Runtime Environment on Windows

--------------------------------------------------

 

If you are only interested in running GTK+ application on Windows (that is, you don't care about developing GTK+ applications) then you need just the GTK+ runtime installer, which can be downloaded from the following link:

 

http://sourceforge.n...ojects/gtk-win/

 

It is advertised as setting-up everything for you, with an absolutely minimal effort from your part, but please note that I have NO personal experience with it (I always use the all-in-one bundles, that contain everything).

 

Feel free to explore the relative wiki, at the following address:

 

http://sourceforge.n...title=Main_Page

 

 

 

 

==============================================================================

I N S T A L L I N G G L A D E - 3

==============================================================================

 

Glade 3 is the de-facto, cross-platform, rapid development tool for designing GUI layouts, for applications developed with GTK+.

 

TIC-TAC-TOE Overkill comes with its own Glade-3 file, containing all its GUI elements (although some text labels are updated brutally, using the standard C library from within the source code). The file is called: GTK_TIC_EN.GLADE and it is located in the folder: GUI, along with the bitmap files used in the game.

 

As with all Glade-3 files, this is a plain XML file, but in order to browse/manage it graphically you need to open it with Glade-3. For more information check the Glade official site, at the following address: http://glade.gnome.org/

 

The Unix/Linux binaries of Glade-3 are most probably pre-installed on your distribution, along with at least the GTK+2 runtime binaries. But if you haven't updated your Unix/Linux recently, you may wish to do so in order to get the latest versions of both GTK+ and Glade (3.2 and 3.10, respectively). For Windows, the latest Glade version is 3.8.1, and you have to install it yourselves.

 

Note however, that this game only needs GTK+2. GTK+3 is advertised as backward compatible with GTK+2, but I haven't found the time to play with it yet, since I'm mostly working on Windows and there is no stable Windows GTK+3 yet.

 

 

Setting up Glade-3 on Windows

-----------------------------

 

***********************************************************************************

*** DO NOT USE the Glade-3 Windows Installer, not even form the official site ***

***********************************************************************************

 

The reason is that it contains a NASTY bug which will ERASE your Windows PATH environment variable. Thankfully not the one corresponding to your system environment, but it does erase the one corresponding to the environment of the current user.

 

Instead of the Windows installer, download the Glade 3.8.1 Win32 Binaries Bundle from this address (1st in the list):

 

http://www.optionexp...ndows/20111123/

 

or if for some reason the above link does not work for you, try this direct link:

http://www.optionexp...11123_win32.zip

 

The bundle DOES NOT need installation! Just extract it to any folder you like on your system (I use C:\UNIX\GLADE-3) and then add its binaries folder into the PATH environment variable of your windows. And that's all about it!

 

So, if for example you extracted the bundle into the folder: C:\GLADE-3, you need to add the folder: C:\GLADE-3\BIN into the PATH environment variable of Windows (I have already explained how to add/delete/modify Windows environment variables, in the section: "Setting up the GTK+ All-In-One Bundle on Windows").

 

To run Glade-3, just double-click its executable, located inside its binaries folder.

 

 

 

 

==============================================================================

C O M P I L I N G G T K _ T I C . C

==============================================================================

 

 

On Unix/Linux & Windows with Cygwin/MinGW32/MinGW-w64/GnuWin

------------------------------------------------------------------------------

 

Provided GTK+2 is already installed on your system, you can compile the source code by typing the following command line:

 

gcc gtk_tic.c -o gtk_tic.exe `pkg-config --cflags --libs gtk+-2.0`

 

NOTE: *** The backquotes in the line above are NOT single quotes !!! ***

*** If you are on Windows, use either MinGW32's MSYS or Cygwin's ***

*** mintty terminal, or GnuWin's shell, because cmd.exe does NOT ***

*** understand backquotes. ***

*** Also make sure that the backquoted part is the LAST one in ***

*** the command line! ***

 

 

On Unix/Linux & Windows using Code::Blocks

------------------------------------------------------------------------------

 

Provided GTK+2 is already installed on your system, you can use the excellent, cross-platform Code::Blocks IDE, which is a perfect match for GCC on all platforms (on Windows it even comes with an alternative installer which besides the IDE it installs and sets-up MinGW32 too, automatically).

 

Code::Blocks is GTK+ ready, meaning that it provides a project wizard for GTK+ applications. All you have to do is to provide the folder of GTK+ on your system ONCE and that's all about it!

 

Actually there is another little thing you must do BEFORE EVERYTHING ELSE: make Code::Blocks's GTK+ wizard being aware of a change made in GTK+2 that differentiated the gdk_pixbuf library.

 

Visit this link:

http://www.gtkforums...opic.php?t=8908

 

for nicely put, short, instructions. But do NOT download the GTK+2 bundle from that link, it is only for Windows and it's an old version too. For the most recent versions of GTK+ visit the download page at the official GTK+ site:

 

http://www.gtk.org/download/

 

 

On Windows using CMD.EXE

------------------------------------------------------------------------------

 

Provided GTK+2 and a Windows port of GCC are already installed and work on your system, you can compile the game (and every other GTK+ program) directly from the Windows command prompt. It's a bit tedious, but I'll give you an elegant solution to make it much simpler.

 

Assuming that a) GTK+2 is installed in the folder: C:\GTK2, you have put the folder: C:\GTK2\BIN in the PATH environment variable of your Windows, and c) you have created an environment variable GTK_HOME = "C:\GTK2", you can compile any GTK+2 application by typing the following (very long) command line at the prompt:

 

gcc gtk_tic.c -o gtk_tic.exe -mms-bitfields -Ic:/gtk2/include/gtk-2.0 -Ic:/gtk2/lib/gtk-2.0/include -Ic:/gtk2/include/atk-1.0 -Ic:/gtk2/include/cairo -Ic:/gtk2/include/pango-1.0 -Ic:/gtk2/include/glib-2.0 -Ic:/gtk2/lib/glib-2.0/include -Ic:/gtk2/include -Ic:/gtk2/include/freetype2 -Ic:/gtk2/include/libpng14 -Lc:/gtk2/lib -lgtk-win32-2.0 -lgdk-win32-2.0 -latk-1.0 -lgio-2.0 -lgdk_pixbuf-2.0 -lpangowin32-1.0 -lgdi32 -lpangocairo-1.0 -lpango-1.0 -lcairo -lgobject-2.0 -lgmodule-2.0 -lgthread-2.0 -lglib-2.0 -lintl

 

Of course, that is too much to type every time. All this line does is to direct GCC into specific folders for finding header files & libraries needed by GTK+2.

 

To make your life a lot easier, you can create ONCE two Windows environment variables, say GTK2_CFLAGS and GTK2_LIBS (you may give them any name you want) with the following contents:

 

GTK2_CFLAGS = "-mms-bitfields -Ic:/gtk2/include/gtk-2.0 -Ic:/gtk2/lib/gtk-2.0/include -Ic:/gtk2/include/atk-1.0 -Ic:/gtk2/include/cairo -Ic:/gtk2/include/pango-1.0 -Ic:/gtk2/include/glib-2.0 -Ic:/gtk2/lib/glib-2.0/include -Ic:/gtk2/include -Ic:/gtk2/include/freetype2 -Ic:/gtk2/include/libpng14"

 

GTK2_LIBS = "-Lc:/gtk2/lib -lgtk-win32-2.0 -lgdk-win32-2.0 -latk-1.0 -lgio-2.0 -lgdk_pixbuf-2.0 -lpangowin32-1.0 -lgdi32 -lpangocairo-1.0 -lpango-1.0 -lcairo -lgobject-2.0 -lgmodule-2.0 -lgthread-2.0 -lglib-2.0 -lintl"

 

Now you can compile any GTK+2 application by typing the following command line at the prompt:

 

gcc gtk_tic.c -o gtk_tic.exe %GTK2_CFLAGS% %GTK2_LIBS%

 

 

 

On Windows using Pelles C 6.00

------------------------------------------------------------------------------

 

This requires a bit of work on your part inside the IDE of Pelles C. The idea is to let Pelles C know where the GTK+2 header files & libraries are located, along with specifying which GTK+2 libraries should be linked to your executable.

 

I'm gonna use screenshots to walk you through the process, but KEEP IN MIND that on my setup GTK+2 is installed in the folder: C:\UNIX\GTK+ (in the previous paragraphs of this text I was using as an example the folder: C:\GTK2 instead, so make sure you adjust the folder to your own GTK+2 installation).

 

1. Create a new "Win32 Console Program (EXE)" empty project from within

the Pelles C IDE (you are free to use any folder you like of course)...

 

http://img412.images...snewproject.jpg

 

2. Add the GTK+2 binaries folder to Pelles C IDE, using the menu command:

Tools -> Options [Folders >> Executables] ...

 

http://img137.images...lestoolsbin.jpg

 

3. Add all other GTK+2 dependencies into your project, using the menu command:

Project -> Project options ...

 

a) The [Compiler] tab ...

 

http://img684.images...ectcompiler.jpg

 

The [Linker] tab...

 

http://img249.images...ojectlinker.jpg

 

To save you some typing (lots of it) here is the complete string

to paste right after "delayimp.lib" in the above screenshot (make

sure you type an empty space before pasting):

 

gtk-win32-2.0.lib gdk-win32-2.0.lib atk-1.0.lib gio-2.0.lib gdk_pixbuf-2.0.lib pangowin32-1.0.lib gdi32.lib pangocairo-1.0.lib pango-1.0.lib cairo.lib gobject-2.0.lib gmodule-2.0.lib gthread-2.0.lib glib-2.0.lib intl.lib

 

c) The [Folders] tab...

 

First the Libraries:

http://img685.images...projectlibs.jpg

 

Then the Includes:

http://img80.imagesh...jectinclude.jpg

 

To add and re-arrange the order of folders when you are in the

[Folders] tab, use the corresponding icons right next to the

drop-down list.

 

4. Save your project, hit the Build & Run button and you are all done!

 

By following the above steps you can compile, build and run the gtk_tic game from within Pelles C IDE, on Windows.

 

Unfortunately the GUI project manager of Pelles C does NOT allow project cloning, so it's not trivial to make a generic GTK+2 project and then graphically clone it for every new GTK+2 application you develop. Making a GTK+ project wizard is not trivial either, although it is ideal as a permanent solution (check the Pelles C SDK for working samples on creating project wizards).

 

You can still clone manually your project's folder using the Windows Explorer, but you must also rename/delete files inside that folder, and most importantly you should manually edit the *.ppj file to match your new project's naming. And of course you must add/remove source files to your new project, once you load it inside the IDE.

 

The above is equivalent to using Pelles C's make utility from the command line (it is called POMAKE.EXE) along with its /f switch, for building executables through any *.ppj file, but setting that up is out of the scope for this text!

 

 

 

==============================================================================

L I N K S O F R E F E R E N C E D S O F T W A R E

==============================================================================

 

Here is a list of links to the sites of all the software I have referenced in this text, in alphabetical order...

 

Code::Blocks IDE : http://www.codeblocks.org/

the Cygwin project : http://www.cygwin.com/

Glade (a User Interface Designer) : http://glade.gnome.org/

GnuWin (former GnuWin32) : http://gnuwin32.sourceforge.net/

the GTK+ project : http://www.gtk.org/

the MinGW32 project : http://www.mingw.org/

the MinGW-w64 project : http://mingw-w64.sourceforge.net/

Pelles C : http://www.smorgasbordet.com/pellesc/