Συνδυαστική θεωρία παιγνίων

Η συνδυαστική θεωρία παιγνίων, γνωστή και ως CGT, είναι ένας κλάδος των εφαρμοσμένων μαθηματικών και της θεωρητικής επιστήμης των υπολογιστών που μελετά τα συνδυαστικά παίγνια και διαφέρει από την "παραδοσιακή" ή "οικονομική" θεωρία παιγνίων. Η CGT προέκυψε σε σχέση με τη θεωρία των αμερόληπτων παιγνίων, ιδίως του παιγνίου Nim δύο παικτών, με έμφαση στην "επίλυση" ορισμένων τύπων συνδυαστικών παιγνίων.

Ένα παίγνιο πρέπει να πληροί διάφορες προϋποθέσεις για να είναι συνδυαστικό παίγνιο. Αυτές είναι οι εξής:

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

Η Θεωρία Συνδυαστικών Παιγνίων περιορίζεται σε μεγάλο βαθμό στη μελέτη ενός υποσυνόλου συνδυαστικών παιγνίων που είναι δύο παικτών, πεπερασμένα και έχουν νικητή και ηττημένο (δηλαδή δεν καταλήγουν σε ισοπαλία).

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

Οι Elwyn Berlekamp, John Conway και Richard Guy είναι οι θεμελιωτές της θεωρίας. Εργάστηκαν μαζί τη δεκαετία του 1960. Το δημοσιευμένο έργο τους ονομαζόταν Winning Ways for Your Mathematical Plays.

Ορισμοί

Στη θεωρία, υπάρχουν δύο παίκτες που ονομάζονται αριστερά και δεξιά. Ένα παιχνίδι είναι κάτι που επιτρέπει στο αριστερό και το δεξί να κάνουν κινήσεις σε άλλα παιχνίδια. Για παράδειγμα, στο παιχνίδι του σκακιού, υπάρχει ένα συνηθισμένο αρχικό setup. Θα μπορούσε, ωστόσο, κανείς να σκεφτεί μια παρτίδα σκάκι μετά την πρώτη κίνηση ως ένα διαφορετικό παιχνίδι, με διαφορετικό στήσιμο. Έτσι, κάθε θέση ονομάζεται επίσης παρτίδα.

Τα παιχνίδια έχουν τον συμβολισμό {L|R}. L {\displaystyle L} $L$ είναι τα παιχνίδια στα οποία μπορεί να μετακινηθεί ο αριστερός παίκτης. R {\displaystyle R} $R$ είναι τα παιχνίδια στα οποία μπορεί να μετακινηθεί ο δεξιός παίκτης. Αν γνωρίζετε τη σημειογραφία του σκακιού, τότε η συνήθης σκακιστική διάταξη είναι η παρτίδα

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Οι τελείες "..." σημαίνουν ότι υπάρχουν πολλές κινήσεις, οπότε δεν εμφανίζονται όλες.

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

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

Το πιο εύκολο παιχνίδι Nim ξεκινά χωρίς καθόλου μετρητές! Σε μια τέτοια περίπτωση, κανένας από τους δύο παίκτες δεν μπορεί να κινηθεί. Αυτό φαίνεται ως {|}. Και οι δύο πλευρές είναι άδειες, επειδή κανένας παίκτης δεν μπορεί να κινηθεί. Ο πρώτος παίκτης που θα φύγει δεν μπορεί να κινηθεί και έτσι θα χάσει. Στην CGT, οι άνθρωποι συχνά γράφουν {|} ως το σύμβολο 0 (μηδέν).

Το αμέσως επόμενο πιο εύκολο παιχνίδι έχει μόνο έναν σωρό, με έναν μόνο μετρητή. Αν ο αριστερός παίκτης πάει πρώτος, αυτός ο παίκτης πρέπει να πάρει τον μετρητή, αφήνοντας το δεξί χωρίς κινήσεις ({|}, ή 0). Αντίθετα, αν το δεξί παίξει πρώτο, δεν θα υπάρχουν άλλες κινήσεις για το αριστερό. Έτσι, τόσο το αριστερό όσο και το δεξί μπορούν να κάνουν μια κίνηση στο 0. Αυτό εμφανίζεται ως {{|}|{|}}, ή {0|0}. Ο πρώτος παίκτης που θα κινηθεί θα κερδίσει. Παιχνίδια ίσα με {0|0} είναι πολύ σημαντικά. Γράφονται με το σύμβολο * (αστέρι).

Ερωτήσεις και απαντήσεις

Ερ: Τι είναι η θεωρία συνδυαστικών παιγνίων;

A: Η Θεωρία Συνδυαστικών Παιγνίων (CGT) είναι ένας κλάδος των εφαρμοσμένων μαθηματικών και της θεωρητικής επιστήμης των υπολογιστών που μελετά τα συνδυαστικά παίγνια και διαφέρει από την "παραδοσιακή" ή "οικονομική" θεωρία παιγνίων.

Ερ: Ποιες προϋποθέσεις πρέπει να πληροί ένα παίγνιο για να θεωρηθεί συνδυαστικό παίγνιο;

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

Ερ: Σε ποιο είδος παιγνίων επικεντρώνεται η Συνδυαστική Θεωρία Παιγνίων;

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

Ερ: Πώς αναπαρίστανται αυτά τα είδη παιγνίων;

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

Ερ: Ποιοι είναι κάποιοι στόχοι για τους θεωρητικούς CG;

Α: Ορισμένοι στόχοι για τους θεωρητικούς της CG περιλαμβάνουν την εύρεση τιμών για αυτούς τους τύπους παιγνίων καθώς και την κατανόηση της έννοιας της "προσθήκης παιγνίων", η οποία περιλαμβάνει ότι κάθε παίκτης κάνει μόνο μία κίνηση σε δύο διαφορετικά παιγνίδια αφήνοντας το άλλο αμετάβλητο κατά τη διάρκεια της σειράς του.

Ερ: Ποιος ίδρυσε την CGT;

Α: Οι Elwyn Berlekamp, John Conway και Richard Guy πιστώνονται την ίδρυση της CGT στο δημοσιευμένο έργο τους με τίτλο Winning Ways for Your Mathematical Plays στη δεκαετία του 1960.