Tρίλιζα ή Tic-tac toe

​

Το παιχνίδι Τρίλιζα:

Η τρίλιζα, γνωστή και σαν Tic-tac toe, είναι ένα παιχνίδι που λειτουργεί ως εξής.

Ξεκινάμε με ένα τετράγωνο πλέγμα 9 κενών πεδίων:

​

 

Το Tic-tac-toe παίζεται με δύο παίκτες, οι οποίοι σημειώνουν εναλλάξ ένα από τα κενά πεδία. Ο πρώτος παίκτης χρησιμοποιεί το Χ  ως σήμα του, ο δεύτερος χρησιμοποιεί το Ο . Ο πρώτος που θα καταφέρει να βάλει 3 γράμματα Χ ή Ο στη σειρά (οριζόντια), στήλη (κάθετα) ή διαγώνια κερδίζει το παιχνίδι.

Για παράδειγμα οι θέσεις που κερδίζει ο πρώτος παίκτης είναι:

 

 

​

​

​

​

​

​

​

Ομοίως αν κερδίσει ο δεύτερος

 

Λέμε ότι το Tic-tac-toe είναι ένα παιχνίδι μηδενικού αθροίσματος , που σημαίνει ότι μια νίκη για έναν από τους 2 παίκτες σημαίνει ίση απώλεια για τον άλλο παίκτη. Αυτό είναι λογικό: όταν έχεις τρεις στη σειρά, κερδίζεις και ο αντίπαλός σου χάνει. Δεν μπορείτε να κερδίσετε και οι δύο. Ωστόσο, μπορείτε να ισοφαρίσετε, εάν όλα τα πεδία είναι συμπληρωμένα και κανείς δεν κέρδισε. Τέτοιες περιπτώσεις έχουμε, για παράδειγμα δείτε το διπλανό σχήμα.

 

 

 

 

 

Ένα τυπικό παιχνίδι Tic-tac-toe μπορεί να ξεκινήσει ως εξής:

1η Κίνηση: Το παίκτης X παίζει πάνω αριστερά

​

​

 

 

2η Κίνηση: Ο παίκτης Ο αντιδρά και παίζει στο μεσαίο τετράγωνο.

 

 

​

​

 

3η Κίνηση: Το παίκτης X παίζει κάτω δεξιά

 

 

 

 

 

 

 

4η Κίνηση: Στη συνέχεια ο παίκτης Ο παίζει κάτω αριστερά

 

 

 

 

 

 

5η Κίνηση: Το X παίζει πάνω δεξιά

 

 

 

 

 

 

 

 

6η Κίνηση: Το O παίζει στη κορυφή και στο μέσο.

 

 

 

 

 

 

7η Κίνηση: Το X παίζει δεξιά και κάτω. (Για κάποιο λόγο, υποτίθεται ότι πρέπει να τραβήξετε μια γραμμή ανάμεσα στους 3 βαθμούς που κερδίζετε.)

 

 

 

 

Έτσι σε αυτό το παιχνίδι, ο παίκτης Χ κερδίζει. Το θέμα όμως είναι: πώς αποφασίζεις ποια κίνηση θα παίξεις;

Από την έκτη έως την τελευταία θέση, ήταν ένα αρκετά εύκολο έργο για τον παίκτη Χ. Υπήρχαν 3 διαθέσιμες κινήσεις για τον παίκτη Χ (σημειώνουμε με 1, 2 και 3):

​

​

​

​

 

 

Η κίνηση 1 δεν είναι «καλή» για τον παίκτη Χ. Στην πραγματικότητα, δίνει στον παίκτη Ο την ευκαιρία να κερδίσει παίζοντας στη θέση με ένδειξη 2.

Η κίνηση με ένδειξη 3, από την άλλη πλευρά, είναι μια άμεση νίκη για το Χ. Η κίνηση με ένδειξη 2 μπορεί να θεωρηθεί ουδέτερη, καθώς δεν δίνει στον παίκτη Χ μια νίκη, αλλά ούτε και μια ήττα.

Θα μπορούσαμε λοιπόν να ταξινομήσουμε αυτές τις 3 κινήσεις ως προς τη χρησιμότητα ως εξής (αν και σημειώστε ότι αυτό είναι απλοποιημένο):

• κίνηση 1: χρησιμότητα 1 (καθώς είναι μια άμεση νίκη)

• κίνηση 2: χρησιμότητα 0 (ισοπαλία)

• κίνηση 3: χρησιμότητα -1 (καθώς οδηγεί σε πιθανή απώλεια)

Και έτσι η προφανής κίνηση για παιχνίδι είναι η κίνηση 1.

Τι γίνεται όμως με μια κίνηση νωρίτερα; Θυμηθείτε, η κατάσταση ήταν ως εξής:

Πώς πρέπει ο Χ να αποφασίσει ποια κίνηση θα κάνει;

 

 

 

​

​

 

Ο παίκτης Χ έχει 5 πιθανές κινήσεις, καμία από τις οποίες δεν είναι άμεσα νίκη. Πώς λοιπόν ο Χ να αποφασίσει ποια είναι η καλύτερη κίνηση; Πώς πρέπει να εκχωρήσει βοηθητικά προγράμματα στις πιθανές μετακινήσεις;

Το πρόβλημα εδώ είναι ότι η χρησιμότητα κάθε κίνησης εξαρτάται από το τι θα κάνει ο παίκτης  Ο στην κίνησή του.

Σε αυτήν την περίπτωση, η πάνω δεξιά κίνηση είναι αρκετά καλή, καθώς δίνει δύο δυνατότητες (τα σκιασμένα πεδία) για νίκη στην επόμενη κίνηση:

Η πάνω δεξιά κίνηση δίνει λοιπόν βεβαιότητα να κερδίσετε την επόμενη κίνηση. Καθώς ο παίκτης Ο μπορεί να μπλοκάρει μόνο έναν από αυτούς στην επόμενη κίνησή του, ο παίκτης Χ μπορεί να εγγυηθεί μια τέτοια νίκη.

Τι γίνεται όμως με την πρώτη κίνηση του παιχνιδιού; Ποιος είναι ο καλύτερος τρόπος για να ξεκινήσετε το παιχνίδι; Αυτό εξαρτάται από το τι θα κάνει ο παίκτης Ο στην πρώτη του κίνηση το οποίο εξαρτάται από το τι θα κάνει ο παίκτης  Χ στη δεύτερη κίνησή. 

Αποδεικνύεται ότι υπάρχει ένας πολύ ακριβής τρόπος για να υπολογίσετε την καλύτερη κίνηση σε οποιαδήποτε κατάσταση  χρησιμοποιώντας τον αλγόριθμο Minimax .

​

Παίξτε το παιχνίδι της ΤΡΙΛΙΖΑΣ

​

Ο αλγόριθμος λειτουργεί ως εξής.

Σε μια δεδομένη κατάσταση, σκεφτείτε όλες τις κινήσεις που έχετε στη διάθεσή σας. (Στην αρχή του παιχνιδιού, αυτό είναι 9 κινήσεις.)

Σε κάθε βήμα εκχωρούμε ένα ποιοτικό στοιχείο χρησιμότητας  (= -1,0,1). Αυτό βοηθά στην κατανόηση του αλγορίθμου.

Εάν μια τέτοια κίνηση είναι άμεση νίκη (δημιουργεί μια γραμμή, στήλη ή διαγώνιο 3 από τα σημάδια σας), εκχωρήστε την τιμή 1 στη χρησιμότητα.

Εάν σε μια κίνηση κανείς δεν κερδίζει, έχουμε ισοπαλία — εκχωρήστε 0 στη χρησιμότητα, για  αυτήν την κίνηση.

Η κίνηση δεν είναι ούτε νίκη, ούτε ισοπαλία; Τότε τα πράγματα είναι πιο ενδιαφέροντα: ο αντίπαλός σου θα αντιδράσει σε αυτή την κίνηση. Επομένως, εξετάζουμε όλες τις πιθανές κινήσεις που μπορεί να κάνει ο αντίπαλός σας ως αντίδραση στην κίνηση που σκέφτηκες.

Είναι  μια τέτοια κίνηση νίκη για τον αντίπαλό σας; Εκχωρήστε στη χρησιμότητα -1. 

Είναι ισοπαλία; εκχωρήστε 0.

Δεν κέρδισε ο αντίπαλός σας και είναι δυνατή μια αντεπίθεση από εσάς; Εξετάστε όλες αυτές τις πιθανές αντεπιθέσεις. Και ούτω καθεξής. 

Με αυτόν τον τρόπο, τελικά αναζητούμε όλα τα πιθανά παιχνίδια. 

Πώς όμως εκχωρούμε χρησιμότητα σε κινήσεις που δεν τελειώνουν το παιχνίδι;

​

Ας δούμε ένα παράδειγμα. Ας πούμε ότι ξεκινάμε με την ακόλουθη θέση:

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Ας θεωρήσουμε σαν  τελευταία κίνηση αυτή που βλέπετε στην κορυφή. 

• Στο επόμενο παίζει ο παίκτης Χ.

Η κίνηση είναι μια άμεση νίκη για τον Χ και αντιστοιχούμε σε αυτήν τη χρησιμότητα 1.  Η μεσαία κίνηση οδηγεί σε νίκη. Ας επεξεργαστούμε τις υπόλοιπες.​

• Ας πάμε στην τελευταία σειρά. 

Τα δύο ακραία πλέγματα είναι ισοπαλίες και έχουν χρησιμότητα 0. Το μεσαίο πλέγμα είναι νίκη για τον πάικτη Χ και έχει χρησιμότητα 1.

•  ​Ας ανεβούμε μια σειρά.

Το πρώτο από αριστερά πλέγμα είναι απώλεια για τον Χ, άρα έχει χρησιμότητα -1.

Το δεύτερο έχει 1 πιθανή συνέχεια και λαμβάνει τη χρησιμότητα αυτής της συνέχειας 0

Το τρίτο είναι νίκη για τον παίκτη Χ και λαμβάνει τη χρησιμότητα 1.

Το τέταρτο έχει 1 πιθανή συνέχεια και λαμβάνει τη χρησιμότητα αυτής της συνέχειας 0.

• Τέλος ανεβαίνουμε ακόμα μια σειρά. 

Το πρώτο πλέγμα από αριστερά έχει 2 επακόλουθες ενέργειες με χρησιμότητα 0 και -1. Αν η κίνηση του παίκτη Ο είναι καλή, δηλαδή είναι αυτή με την οποία ο παίκτης Χ έχει τη μικρότερη χρησιμότητα ενώ για εμάς τη μεγαλύτερη (δεδομένου ότι το παιχνίδι είναι παιχνίδι μηδενικού αθροίσματος), θα πάρει χρησιμότητα -1. ​

Το μεσαίο πλέγμα, έχουμε ήδη μιλήσει για αυτό, έχει χρησιμότητα 1. 

Το τρίτο πλέγμα, με την ίδια λογική του πρώτου πλέγματος, ένας καλός αντίπαλος θα επιλέξει το δεξιό πλέγμα που έχει τη χαμηλότερη χρησιμότητα για εμάς. Άρα, η χρησιμότητά του είναι 0. 

​

Το πλέγμα ανωτέρου επιπέδου παίρνει τη χρησιμότητα από το χρησιμότερο πλέγμα στην επόμενη σειρά, για τον πάικτη που έχει σειρά να παίξει. 

Στη δεύτερη σειρά παίζει ο Χ και μπορεί να κερδίσει, άρα έχει χρησιμότητα 1.

Στη τρίτη σειρά παίζει ο παίκτης Ο και στο πρώτο αριστερά δέντρο  θα πάρει τη χρησιμότητα του πάικτη Ο που είναι -1, ενώ το δεξιό δέντρο η μέγιστη χρησιμότητα που θα μπορούσε να αποσπάσει ο παίκτης Ο είναι 0.

​

Με αυτόν τον τρόπο, μπορούμε να χρησιμοποιήσουμε το Minimax για να βρούμε την καλύτερη κίνηση σε κάθε κατάσταση — υποθέτοντας συνεχώς ότι ο αντίπαλός μας θα κάνει την κίνηση που είναι καλύτερη (χρήσιμη) γι' αυτόν . Αλλά φυσικά, αν ο αντίπαλός μας δεν παίξει τόσο καλά, αυτό μόνο προς όφελός μας μπορεί να είναι!

​

Το Minimax μπορεί να χρησιμοποιηθεί για οποιοδήποτε παιχνίδι μηδενικού αθροίσματος. Θεωρητικά βρίσκει την καλύτερη κίνηση και στο Σκάκι. Αλλά εδώ υπάρχει ένα τεράστιο πρακτικό πρόβλημα!

Στην αρχή του Tic-tac-toe, μπορούμε να επιλέξουμε από 9 πιθανές κινήσεις. Αφού το κάνουμε αυτό, ο αντίπαλός μας μπορεί να επιλέξει από 9 – 1 = 8 πιθανές κινήσεις. Στη συνέχεια, μπορούμε να επιλέξουμε από 7, κλπ. Ο συνολικός αριθμός των πιθανών παιχνιδιών είναι επομένως 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 9! = 362880. Ένας σύγχρονος υπολογιστής μπορεί εύκολα να ψάξει σε όλα αυτά τα παιχνίδια για να βρει την καλύτερη κίνηση. 

​

Ο συνολικός αριθμός πιθανών παιχνιδιών σκακιού είναι προς το παρόν άγνωστος, αλλά είναι τουλάχιστον 10^120 (ο αριθμός Shannon). Αυτό είναι ένα 1 ακολουθούμενο από 120 μηδενικά.

 

Ακόμα κι αν έχουμε έναν υπερυπολογιστή που πραγματοποιεί αναζήτηση σε ένα δισεκατομμύριο (109) παιχνίδια ανά δευτερόλεπτο, θα χρειαζόταν αυτός ο υπολογιστής περισσότερα από 3 * 10^103 χρόνια για να πραγματοποιήσει αναζήτηση σε όλα τα παιχνίδια. Ένας υπολογιστής που είναι δισεκατομμύρια φορές πιο γρήγορος από αυτόν; 3 * 1094 χρόνια. Μπορούμε απλά να το ξεχάσουμε. Για να αφήσουμε έναν υπολογιστή να παίξει Σκάκι, χρειαζόμαστε διαφορετικές τεχνικές (αν και ένα περιορισμένο Minimax μπορεί να είναι μέρος της λύσης).

​

Ας δούμε κάποια προγράμαμτα στη python και C++. Για να τρέξτε τα προγράμματα, αντιγράψτε με Ctrl+C τα παρακάτω αρχεία και με Ctrl+V επικολλήστε τα στον editor του compliler της python ή C++. Για τον complier μπείτε εδω: compiler

​

Το αρχείο είναι ένα παιχνίδι διαδραστικό στη PYTHON

​

Το αρχείο δίνει ένα παιχνίδι τρίλιζας στην C++

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​