• ΚΡΟΤΟΣ
• Windows
• Antivirus
• Antivirus
• ΓΡΑΦΙΚΕΣ ΤΕΧΝΕΣ

ανταγωνιστικό παιχνίδι. Επίλυση ανταγωνιστικών παιχνιδιών μήτρας Αρχές επίλυσης ανταγωνιστικών παιχνιδιών μήτρας

Η θεωρία παιγνίων είναι μια θεωρία μαθηματικών μοντέλων λήψης αποφάσεων υπό συνθήκες σύγκρουσης ή αβεβαιότητας. Υποτίθεται ότι οι ενέργειες των μερών στο παιχνίδι χαρακτηρίζονται από ορισμένες στρατηγικές - σύνολα κανόνων δράσης. Αν το κέρδος της μιας πλευράς οδηγεί αναπόφευκτα στην απώλεια της άλλης πλευράς, τότε μιλούν για ανταγωνιστικά παιχνίδια. Εάν το σύνολο των στρατηγικών είναι περιορισμένο, τότε το παιχνίδι ονομάζεται παιχνίδι μήτρας και η λύση μπορεί να ληφθεί πολύ απλά. Οι λύσεις που λαμβάνονται με τη βοήθεια της θεωρίας παιγνίων είναι χρήσιμες για την κατάρτιση σχεδίων ενόψει πιθανής αντίθεσης από ανταγωνιστές ή αβεβαιότητας στο εξωτερικό περιβάλλον.

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

Αυτό το παιχνίδι είναι ανταγωνιστικό. Σε αυτό j \u003d x2 - O, P και R (O, O] \u003d H (P, P) \u003d -I και R (O, P) \u003d R (P, O) \u003d 1, ή σε μορφή μήτρας o p

Αφήστε κάποια κατηγορία παιχνιδιών Г να είναι "καθρέφτη-κλειστά", π.χ. μαζί με καθένα από τα παιχνίδια του περιέχει ένα κατοπτρικό ισομορφικό παιχνίδι (καθώς όλα τα παιχνίδια που είναι ισόμορφα με καθρέφτη σε ένα δεδομένο είναι ισόμορφα μεταξύ τους, μπορούμε, σύμφωνα με όσα μόλις ειπώθηκαν, να μιλάμε για ένα ισόμορφο παιχνίδι καθρέφτη). Μια τέτοια κλάση είναι, για παράδειγμα, η κλάση όλων των ανταγωνιστικών παιχνιδιών ή η κλάση όλων των παιχνιδιών matrix.

Υπενθυμίζοντας τον ορισμό των αποδεκτών καταστάσεων στο ανταγωνιστικό παιχνίδι, λαμβάνουμε ότι η κατάσταση (X, Y) στη μικτή επέκταση του παιχνιδιού μήτρας είναι αποδεκτή για τον παίκτη 1 εάν και μόνο εάν για οποιοδήποτε x G x η ανισότητα

Η διαδικασία μετατροπής των παιχνιδιών σε συμμετρικά ονομάζεται συμμετρία. Περιγράφουμε εδώ μια μέθοδο συμμετρίας. Μια άλλη, θεμελιωδώς διαφορετική εκδοχή συμμετρισμού θα δοθεί στην Ενότητα 26.7. Και οι δύο αυτές παραλλαγές συμμετρίας ισχύουν στην πραγματικότητα σε αυθαίρετα ανταγωνιστικά παιχνίδια, αλλά θα διατυπωθούν και θα αποδειχθούν μόνο για παιχνίδια matrix.

Έτσι, οι αρχικοί όροι και ονομασίες της θεωρίας των γενικών ανταγωνιστικών παιχνιδιών συμπίπτουν με τους αντίστοιχους όρους και ονομασίες της θεωρίας των παιχνιδιών μήτρας.

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

Η εξέταση των παιχνιδιών matrix δείχνει ήδη ότι υπάρχουν ανταγωνιστικά παιχνίδια χωρίς καταστάσεις ισορροπίας (και ακόμη και χωρίς καταστάσεις e-ισορροπίας για αρκετά μικρό e > 0) στις αρχικές στρατηγικές των παικτών.

Αλλά κάθε παιχνίδι πεπερασμένου (μήτρας) μπορεί να επεκταθεί σε ένα άπειρο παιχνίδι, για παράδειγμα, παρέχοντας σε κάθε παίκτη οποιονδήποτε αριθμό κυριαρχούμενων στρατηγικών (βλ. 22 Κεφ. 1). Προφανώς, μια τέτοια επέκταση του συνόλου στρατηγικών του παίκτη δεν θα σημαίνει πραγματικά επέκταση των δυνατοτήτων του και η πραγματική συμπεριφορά του στο διευρυμένο παιχνίδι δεν θα πρέπει να διαφέρει από τη συμπεριφορά του στο αρχικό παιχνίδι. Έτσι, αποκτήσαμε αμέσως έναν επαρκή αριθμό παραδειγμάτων άπειρων ανταγωνιστικών παιχνιδιών που δεν έχουν σημεία σέλας. Υπάρχουν επίσης παραδείγματα αυτού του είδους.

Έτσι, για να εφαρμοστεί η αρχή maximin σε ένα άπειρο ανταγωνιστικό παιχνίδι, είναι απαραίτητη, όπως στην περίπτωση ενός πεπερασμένου (matrix) παιχνιδιού, κάποια επέκταση των στρατηγικών δυνατοτήτων των παικτών. Για το 96

Όπως και στην περίπτωση των παιχνιδιών matrix (βλ. Κεφ. 1, 17), για τα γενικά ανταγωνιστικά παιχνίδια σημαντικό ρόλο παίζει η έννοια του φάσματος μεικτής στρατηγικής, η οποία όμως εδώ πρέπει να δοθεί ένας γενικότερος ορισμός.

Τέλος, σημειώστε ότι το σύνολο όλων των μικτών στρατηγικών του παίκτη 1 σε ένα αυθαίρετο ανταγωνιστικό παιχνίδι είναι, όπως στο matrix

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

Έτσι, για παράδειγμα (βλ. Εικ. 3.1), έχουμε ήδη σημειώσει ότι ο «Εργολάβος» σχεδόν ποτέ δεν χρειάζεται να αντιμετωπίσει την αβεβαιότητα συμπεριφοράς. Αλλά αν πάρουμε το εννοιολογικό επίπεδο του τύπου «Διαχειριστής», τότε όλα είναι ακριβώς το αντίθετο. Κατά κανόνα, ο κύριος τύπος αβεβαιότητας που πρέπει να αντιμετωπίσει ένας τέτοιος «ο υπεύθυνος λήψης αποφάσεων» είναι η «Σύγκρουση». Τώρα μπορούμε να διευκρινίσουμε ότι αυτή είναι συνήθως μια μη αυστηρή αντιπαλότητα. Κάπως σπανιότερα, ο «Διαχειριστής» παίρνει αποφάσεις σε συνθήκες «φυσικής αβεβαιότητας», ενώ ακόμη πιο σπάνια συναντά μια αυστηρή, ανταγωνιστική σύγκρουση. Επιπλέον, η σύγκρουση συμφερόντων κατά τη λήψη αποφάσεων από τον "Διαχειριστή" συμβαίνει, θα λέγαμε, "μία φορά", δηλαδή στην κατάταξή μας, παίζει συχνά μόνο ένα (μερικές φορές πολύ μικρό αριθμό) παιχνιδιών του παιχνιδιού. Οι κλίμακες για την αξιολόγηση των συνεπειών είναι πιο συχνά ποιοτικές παρά ποσοτικές. Η στρατηγική ανεξαρτησία του «Διαχειριστή» είναι μάλλον περιορισμένη. Λαμβάνοντας υπόψη τα παραπάνω, μπορεί να υποστηριχθεί ότι οι προβληματικές καταστάσεις αυτού του μεγέθους τις περισσότερες φορές πρέπει να αναλύονται χρησιμοποιώντας μη συνεργατικά μη ανταγωνιστικά παιχνίδια διμήτρας, επιπλέον, σε καθαρές στρατηγικές.

Αρχές για την επίλυση ανταγωνιστικών παιχνιδιών μήτρας

Ως αποτέλεσμα, είναι λογικό να αναμένεται ότι στο παιχνίδι που περιγράφηκε παραπάνω, οι αντίπαλοι θα τηρήσουν τις επιλεγμένες στρατηγικές τους. Matrix ανταγωνιστικό παιχνίδι για το οποίο max min fiv = min max Aiy>

Ωστόσο, δεν είναι όλα τα ανταγωνιστικά παιχνίδια matrix, και στη γενική περίπτωση

Έτσι, στη γενική περίπτωση, για να λυθεί ένα ανταγωνιστικό παιχνίδι μήτρας διάστασης /uxl, είναι απαραίτητο να λυθεί ένα ζεύγος προβλημάτων διπλού γραμμικού προγραμματισμού, με αποτέλεσμα ένα σύνολο βέλτιστων στρατηγικών, / και το κόστος του παιχνιδιού v.

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

Ποιες είναι οι μέθοδοι για την απλοποίηση και την επίλυση ανταγωνιστικών παιχνιδιών μήτρας

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

Όπως έχει ήδη σημειωθεί, το τελικό ανταγωνιστικό παιχνίδι ονομάζεται matrix.

MATRIX GAMES - μια κατηγορία ανταγωνιστικών παιχνιδιών στα οποία συμμετέχουν δύο παίκτες και κάθε παίκτης έχει έναν πεπερασμένο αριθμό στρατηγικών. Εάν ένας παίκτης έχει m στρατηγικές και ο άλλος παίκτης έχει n στρατηγικές, τότε μπορούμε να κατασκευάσουμε έναν πίνακα παιχνιδιού με διάσταση txn. Μι. μπορεί να έχει ή όχι σημείο σέλας. Στην ΤΕΛΕΥΤΑΙΑ περιπτωση

Ινστιτούτο Ηλεκτρομηχανικής της Μόσχας

(Πολυτεχνείο)

Αναφορά εργαστηρίου

στη θεωρία παιγνίων

"Ένα πρόγραμμα αναζήτησης για βέλτιστες στρατηγικές για ένα ζευγαρωμένο ανταγωνιστικό παιχνίδι που δίνεται σε μορφή μήτρας"

Συμπληρώθηκε από μαθητές

όμιλος Α5-01

Ashrapov Daler

Ασράποβα Όλγα

Βασικές έννοιες της θεωρίας παιγνίων

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

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

παιχνίδι που ονομάζεται απλοποιημένο επισημοποιημένο μοντέλο μιας κατάστασης σύγκρουσης.

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

Το κόμμα αποτελείται από κινείται , δηλ. επιλέγοντας παίκτες από ένα σύνολο πιθανών εναλλακτικών.

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

Ονομάζονται παιχνίδια στα οποία υπάρχει τουλάχιστον μία προσωπική κίνηση στρατηγικό .

Τα παιχνίδια στα οποία όλες οι κινήσεις είναι τυχαίες ονομάζονται ΤΥΧΕΡΑ ΠΑΙΧΝΙΔΙΑ .

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

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

Ταξινόμηση μοντέλων θεωρίας παιγνίων

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

Σύμφωνα με αυτόν τον χαρακτηρισμό, μπορεί να προταθεί η ακόλουθη ταξινόμηση μοντέλων θεωρίας παιγνίων:

Διακριτικά (σύνολα στρατηγικών διακεκριμένος)

Τελικός

Ατελείωτες

Συνεχής (σύνολα στρατηγικών συνεχής)

Ατελείωτες

nάτομα (
)

Συνασπισμός (συνεταιρισμός)

Μη συνεργάσιμο (μη συνεργάσιμο)

2 άτομα (σε ζευγάρια)

Ανταγωνιστικά (παιχνίδια μηδενικού αθροίσματος)

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

Μη ανταγωνιστική

Με πλήρεις πληροφορίες (αν ο παίκτης που κάνει μια προσωπική κίνηση γνωρίζει ολόκληρο το ιστορικό του παιχνιδιού, δηλαδή όλες τις κινήσεις του αντιπάλου)

Με ελλιπείς πληροφορίες

Με μηδενικό ποσό (η συνολική πληρωμή είναι μηδέν)

Με μη μηδενικό άθροισμα

Μονόδρομος (λαχεία)

πολλαπλών κατευθύνσεων

Αναπαράσταση μήτρας ενός ζευγαρωμένου ανταγωνιστικού παιχνιδιού

Σε αυτό το σεμινάριο, θα εξετάσουμε ανταγωνιστικά παιχνίδια δύο ατόμων δίνεται σε μορφή μήτρας. Αυτό σημαίνει ότι γνωρίζουμε το σύνολο των στρατηγικών του πρώτου παίκτη (παίκτης ΕΝΑ){ ΕΝΑ Εγώ }, Εγώ = 1,…, Μκαι το σύνολο των στρατηγικών του δεύτερου παίκτη (παίκτης σι){ σι ι }, ι = 1,..., nκαι η μήτρα ΕΝΑ = || ένα ij || τις απολαβές του πρώτου παίκτη. Δεδομένου ότι μιλάμε για ένα ανταγωνιστικό παιχνίδι, υποτίθεται ότι το κέρδος του πρώτου παίκτη είναι ίσο με την απώλεια του δεύτερου. Θεωρούμε ότι το στοιχείο μήτρας ένα ijείναι η ανταμοιβή του πρώτου παίκτη όταν επιλέγει μια στρατηγική ΕΝΑ Εγώκαι η απάντηση του δεύτερου παίκτη με τη στρατηγική σι ι. Θα αναφερθούμε σε ένα τέτοιο παιχνίδι όπως
, όπου Μ - αριθμός στρατηγικών παικτών ΑΛΛΑ,n - αριθμός στρατηγικών παικτών ΣΤΟ.Γενικά, μπορεί να αναπαρασταθεί από τον ακόλουθο πίνακα:

Παράδειγμα 1

Ως απλό παράδειγμα, θεωρήστε ένα παιχνίδι στο οποίο το παιχνίδι αποτελείται από δύο κινήσεις.

1η κίνηση: Παίκτης ΑΛΛΑεπιλέγει έναν από τους αριθμούς (1 ή 2) χωρίς να πει στον αντίπαλο για την επιλογή του.

2η κίνηση: Παίκτης ΣΤΟεπιλέγει έναν από τους αριθμούς (3 ή 4).

Αποτέλεσμα: Επιλογή παίκτη ΑΛΛΑκαι ΣΤΟπροσθέτω. Αν το άθροισμα είναι άρτιο, τότε ΣΤΟπληρώνει την αξία του στον παίκτη ΑΛΛΑ, αν είναι περιττό - αντίστροφα, ΑΛΛΑπληρώνει τον παίκτη ΣΤΟ.

Αυτό το παιχνίδι μπορεί να αναπαρασταθεί ως
με τον εξής τρόπο:

Είναι εύκολο να το δεις αυτό αυτό το παιχνίδιείναι ανταγωνιστικό, επιπλέον, είναι ένα παιχνίδι με ελλιπείς πληροφορίες, αφού παίχτης ΣΤΟ,κάνοντας μια προσωπική κίνηση, δεν είναι γνωστό τι επιλογή έκανε ο παίκτης ΑΛΛΑ.

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

Όταν λύνετε ένα παιχνίδι σε μορφή matrix, θα πρέπει να ελέγξετε το παιχνίδι για την παρουσία σημείο σέλας . Για αυτό, εισάγονται δύο τιμές:

είναι το κατώτερο όριο για την τιμή του παιχνιδιού, και

είναι η ανώτερη εκτίμηση της τιμής του παιχνιδιού.

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

Μπορεί να αποδειχθεί ότι α ≤ V ≤ β , όπου V–τιμή παιχνιδιού , δηλαδή η πιθανή πληρωμή του πρώτου παίκτη.

Αν η σχέση α = β = V, τότε το λένε το παιχνίδι έχει ένα σημείο σέλας
, και επιλύονται σε καθαρές στρατηγικές . Με άλλα λόγια, υπάρχουν μερικές στρατηγικές
, δίνοντας στον παίκτη ΑΛΛΑV.

Παράδειγμα 2

Ας επιστρέψουμε στο παιχνίδι που εξετάσαμε στο Παράδειγμα 1 και ας το ελέγξουμε για την ύπαρξη ενός σημείου σέλας.

Για αυτό το παιχνίδι
= -5,
= 4,
, επομένως, δεν έχει σημείο σέλας.

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

Παράδειγμα 3

Ας κάνουμε μερικές αλλαγές στους κανόνες του παιχνιδιού από το παράδειγμα 1. Ας δώσουμε τον παίκτη ΣΤΟπληροφορίες επιλογής παίκτη ΑΛΛΑ.Επειτα ΣΤΟΥπάρχουν δύο επιπλέον στρατηγικές:

- μια στρατηγική που είναι επωφελής για ΑΛΛΑ.Αν επιλογή Α'1,έπειτα ΣΤΟεπιλέγει 3 εάν επιλογή Α2,έπειτα ΣΤΟεπιλέγει 4?

- μια στρατηγική που δεν είναι επωφελής για ΑΛΛΑ.Αν επιλογή Α'1,έπειτα ΣΤΟεπιλέγει 4 εάν επιλογή Α2,έπειτα ΣΤΟεπιλέγει 3.

Αυτό το παιχνίδι είναι γεμάτο πληροφορίες.

Σε αυτήν την περίπτωση
= -5,
= -5,
, επομένως το παιχνίδι έχει σημείο σέλας
. Αυτό το σημείο σέλας αντιστοιχεί σε δύο ζεύγη βέλτιστων στρατηγικών:
και
. Τιμή παιχνιδιού V= -5. Είναι προφανές ότι για ΑΛΛΑαυτό το παιχνίδι είναι άχρηστο.

Τα παραδείγματα 2 και 3 αποτελούν μια καλή απεικόνιση του παρακάτω θεωρήματος, που αποδεικνύεται στη θεωρία παιγνίων:

Θεώρημα 1

Κάθε ζευγαρωμένο ανταγωνιστικό παιχνίδι με τέλειες πληροφορίες λύνεται σε καθαρές στρατηγικές.

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

Στην περίπτωση απουσίας σημείου σέλας, το λεγόμενο μικτές στρατηγικές :, όπου Π Εγώ καιq ιείναι οι πιθανότητες επιλογής στρατηγικών ΕΝΑ Εγώ και σι ιο πρώτος και ο δεύτερος παίκτες, αντίστοιχα. Η λύση του παιχνιδιού σε αυτή την περίπτωση είναι ένα ζευγάρι μικτών στρατηγικών
μεγιστοποιώντας τη μαθηματική προσδοκία της τιμής του παιχνιδιού.

Μια γενίκευση του Θεωρήματος 1 στην περίπτωση ενός παιχνιδιού με ελλιπείς πληροφορίες είναι το ακόλουθο θεώρημα:

Θεώρημα 2

Κάθε ζευγαρωμένο ανταγωνιστικό παιχνίδι έχει τουλάχιστον μία βέλτιστη λύση, δηλαδή ένα ζευγάρι μικτών στρατηγικών στη γενική περίπτωση
, δίνοντας στον παίκτη ΑΛΛΑβιώσιμο κέρδος ίσο με την τιμή του παιχνιδιού V, Εξάλλου α ≤ V ≤ β .

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

Η απλούστερη περίπτωση, που επεξεργάζεται λεπτομερώς στη θεωρία παιγνίων, είναι ένα παιχνίδι πεπερασμένων ζευγών μηδενικού αθροίσματος (ένα ανταγωνιστικό παιχνίδι δύο προσώπων ή δύο συνασπισμών). Σκεφτείτε αυτό το παιχνίδι σολ, στην οποία δύο παίκτες ΑΛΛΑκαι ΣΤΟ,έχοντας αντίθετα συμφέροντα: το κέρδος του ενός ισούται με την απώλεια του άλλου. Από την πληρωμή του παίκτη ΑΛΛΑισούται με την πληρωμή του παίκτη Μέσα μεαντίθετο πρόσημο, μπορεί να μας ενδιαφέρει μόνο η ανταμοιβή έναπαίχτης ΑΛΛΑ.Φυσικά, ΑΛΛΑθέλει να μεγιστοποιήσει και AT -σμικροποιώ ένα.Για απλότητα, ας ταυτιστούμε νοητικά με έναν από τους παίκτες (ας είναι ΑΛΛΑ)και θα τον λέμε «εμείς», και ο παίκτης AT -"αντίπαλος" (φυσικά, δεν υπάρχουν πραγματικά πλεονεκτήματα για ΑΛΛΑδεν προκύπτει από αυτό). Ας έχουμε tπιθανές στρατηγικές ΑΛΛΑ 1 , ΕΝΑ 2 , ..., ΑΛΛΑ Μκαι ο εχθρός nπιθανές στρατηγικές ΣΤΟ 1 , ΑΤ 2 , ..; ΣΤΟ n(ένα τέτοιο παιχνίδι ονομάζεται παιχνίδι t × n). Σημαίνω ένα ijη ανταμοιβή μας αν χρησιμοποιήσουμε τη στρατηγική ΕΝΑ Εγώ , και ο εχθρός είναι στρατηγική σι ι .

Πίνακας 26.1

Ας υποθέσουμε ότι για κάθε ζεύγος στρατηγικών Α<, ΣΤΟ,νίκη (ή μέση νίκη) ένα, ιξέρουμε. Στη συνέχεια, καταρχήν, είναι δυνατή η σύνταξη ενός ορθογώνιου πίνακα (μήτρας), ο οποίος παραθέτει τις στρατηγικές των παικτών και τις αντίστοιχες αποδόσεις (βλ. πίνακα 26.1).

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

Εξετάστε ένα παράδειγμα παιχνιδιού σολ(4×5) σε μορφή μήτρας. Στη διάθεσή μας (για να διαλέξουμε) τέσσερις στρατηγικές, ο εχθρός έχει πέντε στρατηγικές. Η μήτρα του παιχνιδιού δίνεται στον πίνακα 26.2

Ας σκεφτούμε ποια στρατηγική εμείς (ο παίκτης ΑΛΛΑ)εκμεταλλεύομαι? Το Matrix 26.2 έχει τη δελεαστική απόδοση "10". έχουμε τραβηχτεί να επιλέξουμε μια στρατηγική ΑΛΛΑ 3 , στο οποίο θα πάρουμε αυτό το "τσιγκούνι". Αλλά περιμένετε, ούτε ο εχθρός είναι ηλίθιος! Αν επιλέξουμε στρατηγική ΑΛΛΑ 3 , αυτός, για να μας κακομαθαίνει, θα επιλέξει στρατηγική ΣΤΟ 3 , και παίρνουμε κάποια άθλια ανταμοιβή "1". Όχι, επιλέξτε στρατηγική ΑΛΛΑ 3 ειναι ΑΠΑΓΟΡΕΥΜΕΝΟ! Πώς να είσαι; Προφανώς, με βάση την αρχή της προσοχής (και είναι η κύρια αρχή της θεωρίας παιγνίων), πρέπει να επιλέξουμε

Πίνακας 26.2

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

Ξαναγράφουμε τον πίνακα 26.2 και στη δεξιά πρόσθετη στήλη σημειώνουμε την ελάχιστη τιμή της πληρωμής σε κάθε γραμμή, (ελάχιστη γραμμή). ας το ορίσουμε για Εγώ-η σειρά α Εγώ(βλ. πίνακα 26.3).

Πίνακας 26.3

Από όλες τις αξίες α Εγώ(δεξιά στήλη) επισημαίνεται το μεγαλύτερο (3). Ταιριάζει με τη στρατηγική ΕΝΑτέσσερα. Έχοντας επιλέξει αυτή τη στρατηγική, μπορούμε, σε κάθε περίπτωση, να είμαστε σίγουροι ότι (για οποιαδήποτε συμπεριφορά του εχθρού) θα κερδίσουμε όχι λιγότερο από 3. Αυτή η αξία είναι το εγγυημένο μας κέρδος. Προσέχοντας, δεν μπορούμε να πάρουμε λιγότερα από αυτό (μπορεί να πάρω περισσότερα). Αυτή η πληρωμή ονομάζεται χαμηλότερη τιμή του παιχνιδιού (ή "maximin" - το μέγιστο των ελάχιστων αποδόσεων). Θα το υποδηλώσουμε ένα.Στην περίπτωσή μας α = 3.

Τώρα ας πάρουμε την άποψη του εχθρού και ας επιχειρηματολογήσουμε υπέρ αυτού. Δεν είναι κάποιο πιόνι, αλλά και λογικό! Επιλέγοντας μια στρατηγική, θα ήθελε να δώσει λιγότερα, αλλά πρέπει να υπολογίζει στη συμπεριφορά μας, που είναι ό,τι χειρότερο για αυτόν. Αν επιλέξει στρατηγική ΣΤΟ 1 , θα του απαντήσουμε ΑΛΛΑ 3 , και θα δώσει 10? αν το επιλέξει σι 2 - θα του απαντήσουμε ΑΛΛΑ 2 , και θα δώσει 8 κτλ. Προσθέτουμε μια επιπλέον κάτω σειρά στον πίνακα 26.3 και γράφουμε σε αυτόν τα μέγιστα των στηλών β ι. Προφανώς, ένας προσεκτικός αντίπαλος θα πρέπει να επιλέξει τη στρατηγική που ελαχιστοποιεί αυτήν την τιμή (η αντίστοιχη τιμή του 5 επισημαίνεται στον Πίνακα 26.3). Αυτή η τιμή του β είναι η τιμή του κέρδους, περισσότερο από αυτό που σίγουρα δεν θα μας δώσει ένας λογικός αντίπαλος. Ονομάζεται ανώτερη τιμή του παιχνιδιού (ή "minimax" - το ελάχιστο των μέγιστων κερδών). Στο παράδειγμά μας, β = 5 και επιτυγχάνεται με τη στρατηγική του αντιπάλου σι 3 .

Έτσι, με βάση την αρχή της προσοχής (ο κανόνας αντασφάλισης «πάντα να υπολογίζεις στα χειρότερα!»), πρέπει να επιλέξουμε μια στρατηγική ΑΛΛΑ 4 , και ο εχθρός – στρατηγική ΣΤΟ 3 . Τέτοιες στρατηγικές ονομάζονται "minimax" (βάσει της αρχής minimax). Εφόσον και τα δύο μέρη στο παράδειγμά μας τηρούν τις ελάχιστες στρατηγικές τους, η ανταμοιβή θα είναι ένα 43 = 3.

Τώρα φανταστείτε για μια στιγμή ότι μάθαμε ότι ο εχθρός ακολουθεί στρατηγική ΣΤΟ 3 . Έλα, ας τον τιμωρήσουμε για αυτό και ας επιλέξουμε στρατηγική ΑΛΛΑ 1 - θα πάρουμε 5, που δεν είναι και τόσο κακό. Αλλά μετά από όλα, ο εχθρός δεν είναι επίσης χαμένη. ενημερώστε του ότι η στρατηγική μας ΑΛΛΑ 1 ; είναι επίσης γρήγορος στην επιλογή ΣΤΟ 4 , μειώνοντας την ανταμοιβή μας σε 2, κ.λπ. Με μια λέξη, ελάχιστες στρατηγικές στο παράδειγμά μας ασταθής σε σχέση μεπρος την πληροφορίες σχετικά με τη συμπεριφορά του άλλου μέρους·αυτές οι στρατηγικές δεν έχουν την ιδιότητα ισορροπίας.

Είναι πάντα έτσι; Όχι πάντα. Εξετάστε ένα παράδειγμα με τον πίνακα που δίνεται στον Πίνακα 26.4.

Σε αυτό το παράδειγμα, η χαμηλότερη τιμή του παιχνιδιού είναι ίση με την ανώτερη: α = β = 6. Τι προκύπτει από αυτό; Στρατηγικές παικτών Minimax ΑΛΛΑκαι ΣΤΟθα είναι βιώσιμη. Εφόσον και οι δύο παίκτες μένουν σε αυτά, η ανταμοιβή είναι 6. Ας δούμε τι θα συμβεί αν το κάνουμε (ΑΛΛΑ)να ξέρεις ότι ο εχθρός (ΣΤΟ)

Πίνακας 26.4

εμμένει στη στρατηγική σι 2 ? Και ακριβώς τίποτα δεν θα αλλάξει. Διότι κάθε παρέκκλιση από τη στρατηγική ΑΛΛΑ 2 μπορεί μόνο να επιδεινώσει την κατάστασή μας. Ομοίως, οι πληροφορίες που λαμβάνει ο εχθρός δεν θα τον αναγκάσουν να υποχωρήσει από τη στρατηγική του. ΣΤΟ 2 . Ζεύγος στρατηγικών ΑΛΛΑ 2 , σι 2 έχει την ιδιότητα της ισορροπίας (ένα ισορροπημένο ζεύγος στρατηγικών) και η ανταμοιβή (στην περίπτωσή μας, 6) που επιτυγχάνεται με αυτό το ζεύγος στρατηγικών ονομάζεται «σημείο σέλας του πίνακα» 1). Ένα σημάδι της παρουσίας ενός σημείου σέλας και ενός ισορροπημένου ζεύγους στρατηγικών είναι η ισότητα των χαμηλότερων και ανώτερων τιμών του παιχνιδιού. η κοινή τιμή των α και β ονομάζεται τιμή του παιχνιδιού. Θα το χαρακτηρίσουμε v:

α = β = v

Στρατηγικές ΕΝΑ Εγώ , σι ι(σε αυτήν την περίπτωση ΑΛΛΑ 2 , ΑΤ 2 ), για τις οποίες επιτυγχάνεται αυτή η απόδοση ονομάζονται βέλτιστες καθαρές στρατηγικές και η ολότητά τους ονομάζεται λύση στο παιχνίδι. Σε αυτή την περίπτωση, το ίδιο το παιχνίδι λέγεται ότι λύνεται σε καθαρές στρατηγικές. Δυο πλευρες ΑΛΛΑκαι ΣΤΟμπορεί κανείς να υποδείξει τις βέλτιστες στρατηγικές τους κάτω από τις οποίες η θέση τους είναι η καλύτερη δυνατή. Τι είναι ένας παίκτης ΑΛΛΑσε αυτήν την περίπτωση, 6 νίκες, και ο παίκτης AT -χάνει 6, - καλά, Αυτές είναι οι συνθήκες του παιχνιδιού: είναι επωφελείς για ΑΛΛΑκαι μειονεκτικά για ΣΤΟ

1) Ο όρος "σημείο σέλας" προέρχεται από τη γεωμετρία - αυτό είναι το όνομα του σημείου στην επιφάνεια, όπου επιτυγχάνεται ταυτόχρονα το ελάχιστο κατά τη μία συντεταγμένη και το μέγιστο κατά μήκος της άλλης.

Ο αναγνώστης μπορεί να έχει μια ερώτηση: γιατί οι βέλτιστες στρατηγικές ονομάζονται «καθαρές»; Κοιτώντας λίγο μπροστά, ας απαντήσουμε σε αυτό το ερώτημα: υπάρχουν «μεικτές» στρατηγικές, οι οποίες συνίστανται στο γεγονός ότι ο παίκτης χρησιμοποιεί όχι μία στρατηγική, αλλά πολλές, εναλλάσσοντάς τις τυχαία. Αν λοιπόν επιτρέψουμε, εκτός από αγνές, και μικτές στρατηγικές, οποιαδήποτε τέλος παιχνιδιούέχει μια λύση - ένα σημείο ισορροπίας. Αλλά ακόμα μιλάμε για το άτομο.

Η παρουσία ενός σημείου σέλας στο παιχνίδι απέχει πολύ από το να είναι ο κανόνας, αλλά είναι η εξαίρεση. Τα περισσότερα παιχνίδια δεν έχουν σημείο σέλας. Ωστόσο, υπάρχει μια ποικιλία παιχνιδιών που έχουν πάντα ένα σημείο σέλας και, ως εκ τούτου, λύνονται σε καθαρές στρατηγικές. Πρόκειται για τα λεγόμενα «παιχνίδια με πλήρη ενημέρωση». Ένα παιχνίδι με ένα ράφι πληροφοριών είναι ένα παιχνίδι στο οποίο κάθε παίκτης γνωρίζει ολόκληρη την ιστορία της ανάπτυξής του, δηλαδή τα αποτελέσματα όλων των προηγούμενων κινήσεων, τόσο προσωπικών όσο και τυχαίων, σε κάθε προσωπική κίνηση. Παραδείγματα παιχνιδιών με πλήρεις πληροφορίες είναι το πούλι, το σκάκι, το τικ-τακ κ.λπ.

Στη θεωρία παιγνίων, αποδεικνύεται ότι κάθε παιχνίδι με πλήρεις πληροφορίες έχει ένα σημείο σέλας,και ως εκ τούτου μπορεί να λυθεί σε καθαρές στρατηγικές. Σε κάθε παιχνίδι με τέλειες πληροφορίες, υπάρχει ένα ζευγάρι βέλτιστων στρατηγικών που δίνει μια σταθερή απόδοση ίση με την αλυσίδα του παιχνιδιού v. Εάν ένα τέτοιο παιχνίδι αποτελείται μόνο από προσωπικές κινήσεις, τότε όταν κάθε παίκτης εφαρμόζει τη δική του βέλτιστη στρατηγική, πρέπει να τελειώνει με έναν αρκετά συγκεκριμένο τρόπο - με μια αποπληρωμή ίση με την τιμή του παιχνιδιού. Έτσι, αν η λύση του παιχνιδιού είναι γνωστή, το ίδιο το παιχνίδι χάνει το νόημά του!

Ας πάρουμε ένα στοιχειώδες παράδειγμα παιχνιδιού με πλήρεις πληροφορίες: δύο παίκτες τοποθετούν εναλλάξ τα νίκελ σε ένα στρογγυλό τραπέζι, επιλέγοντας αυθαίρετα τη θέση του κέντρου του νομίσματος (δεν επιτρέπεται η αμοιβαία επικάλυψη κερμάτων). Νικητής είναι αυτός που θα βάλει την τελευταία δεκάρα (όταν δεν υπάρχει χώρος για άλλους). Είναι εύκολο να δει κανείς ότι το αποτέλεσμα αυτού του παιχνιδιού είναι ουσιαστικά ένα προκαθορισμένο συμπέρασμα. Υπάρχει μια συγκεκριμένη στρατηγική που διασφαλίζει ότι ο παίκτης που θα βάλει πρώτος το νόμισμα κερδίζει. Δηλαδή, πρέπει πρώτα να τοποθετήσει ένα νικέλιο στο κέντρο του τραπεζιού και μετά να απαντήσει σε κάθε κίνηση του αντιπάλου με μια συμμετρική κίνηση. Προφανώς, όπως και να συμπεριφέρεται ο αντίπαλος, δεν μπορεί να αποφύγει την ήττα. Η κατάσταση είναι ακριβώς η ίδια με το σκάκι και τα παιχνίδια με πλήρεις πληροφορίες γενικά: οποιοδήποτε από αυτά, γραμμένο σε μορφή μήτρας, έχει ένα σημείο σέλας, και ως εκ τούτου η λύση βρίσκεται σε καθαρές στρατηγικές και, επομένως, έχει νόημα μόνο εφόσον αυτό λύση δεν βρέθηκε. Ας πούμε ότι μια παρτίδα σκάκι είναι είτε πάντατελειώνει με τη νίκη White, ή πάντα -ο μαύρος κερδίζει, ή πάντα -ισοπαλία, μόνο με τι ακριβώς - δεν ξέρουμε ακόμα (ευτυχώς για τους λάτρεις του σκακιού). Ας προσθέσουμε κάτι ακόμα: δύσκολα θα ξέρουμε στο άμεσο μέλλον, γιατί ο αριθμός των στρατηγικών είναι τόσο τεράστιος που είναι εξαιρετικά δύσκολο (αν όχι αδύνατο) να περιορίσεις το παιχνίδι σε μορφή matrix και να βρεις ένα σημείο σέλας σε αυτό.

Τώρα ας αναρωτηθούμε τι να κάνουμε αν το παιχνίδι δεν έχει σημείο σέλας: α ≠ β ; Λοιπόν, αν κάθε παίκτης αναγκαστεί να επιλέξει ένα - τη μόνη καθαρή στρατηγική, τότε δεν υπάρχει τίποτα να κάνει: πρέπει να καθοδηγείται από την αρχή του minimax. Ένα άλλο πράγμα είναι εάν είναι δυνατό να «αναμειχθεί» ένα σύνολο στρατηγικών, εναλλάξ τυχαία με κάποιες πιθανότητες. Η χρήση μικτών στρατηγικών γίνεται με αυτόν τον τρόπο: το παιχνίδι επαναλαμβάνεται πολλές φορές. πριν από κάθε παιχνίδι του παιχνιδιού, όταν δίνεται στον παίκτη μια προσωπική κίνηση, "εμπιστεύεται" την επιλογή του στην τύχη, "ρίχνει κλήρες" και παίρνει τη στρατηγική που έπεσε έξω (ξέρουμε ήδη πώς να οργανώσουμε την παρτίδα από το προηγούμενο κεφάλαιο ).

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

Λοιπόν, ας μιλήσουμε για μικτές στρατηγικές. Θα υποδηλώσουμε τις μικτές στρατηγικές των παικτών ΑΛΛΑκαι ΣΤΟαντίστοιχα μικρόΑ = ( Π 1 , R 2 , ..., Π Μ), μικρό σι = (q 1 , q 2 , …, q n), όπου Π 1 , Π 2 , …, Π Μ(αποτελώντας ένα σύνολο) - οι πιθανότητες του παίκτη που χρησιμοποιεί ΑΛΛΑστρατηγικές ΑΛΛΑ 1 , ΕΝΑ 2 ,… , ΕΝΑ Μ ; q 1 , q 2 , …, q n- πιθανότητες χρήσης από τον παίκτη ΣΤΟστρατηγικές ΣΤΟ 1 , ΣΤΟ 2 , ..., ΣΤΟ n . Σε μια συγκεκριμένη περίπτωση, όταν όλες οι πιθανότητες, εκτός από μία, είναι ίσες με μηδέν και αυτή είναι ίση με μία, η μικτή στρατηγική μετατρέπεται σε καθαρή.

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

Ζεύγος βέλτιστων στρατηγικών
σχηματίζοντας τη λύση του παιχνιδιού έχει την ακόλουθη ιδιότητα: εάν ένας από τους παίκτες τηρήσει τη βέλτιστη στρατηγική του, τότε δεν μπορεί να είναι κερδοφόρο για τον άλλο να παρεκκλίνει από τη δική του.Αυτό το ζευγάρι στρατηγικών σχηματίζει ένα είδος ισορροπίας στο παιχνίδι: ο ένας παίκτης θέλει να μετατρέψει το κέρδος στο μέγιστο, ο άλλος στο ελάχιστο, ο καθένας τραβάει προς τη δική του κατεύθυνση και, με λογική συμπεριφορά και των δύο, μια ισορροπία και μια σταθερή καθιερώνεται κέρδος. v.Αν ένα v > 0, τότε το παιχνίδι είναι κερδοφόρο για εμάς αν v< 0 - για τον εχθρό? στο v= 0 το παιχνίδι είναι «δίκαιο», εξίσου ωφέλιμο και για τους δύο συμμετέχοντες.

Εξετάστε ένα παράδειγμα παιχνιδιού χωρίς σημείο σέλας και δώστε (χωρίς απόδειξη) τη λύση του. Το παιχνίδι έχει ως εξής: δύο παίκτες ΑΛΛΑκαι ΣΤΟταυτόχρονα και χωρίς να πεις λέξη δείξτε ένα, δύο ή τρία δάχτυλα. Η νίκη αποφασίζεται από τον συνολικό αριθμό των δακτύλων: αν είναι ζυγός, κερδίζει ΑΛΛΑκαι λαμβάνει από ΣΤΟποσό ίσο με αυτόν τον αριθμό· αν είναι περίεργο, τότε το αντίστροφο ΑΛΛΑπληρώνει ΣΤΟποσό ίσο με αυτόν τον αριθμό. Τι πρέπει να κάνουν οι παίκτες;

Ας δημιουργήσουμε μια μήτρα παιχνιδιού. Σε ένα παιχνίδι, κάθε παίκτης έχει τρεις στρατηγικές: να δείξει ένα, δύο ή τρία δάχτυλα. Ο πίνακας 3×3 δίνεται στον Πίνακα 26.5. η επιπλέον δεξιά στήλη δείχνει τα ελάχιστα σειρές και η επιπλέον κάτω σειρά δείχνει τα μέγιστα στηλών.

Η χαμηλότερη τιμή του παιχνιδιού α = - 3 και αντιστοιχεί στη στρατηγική ΕΝΑ 1 . Αυτό σημαίνει ότι με λογική, προσεκτική συμπεριφορά, εγγυόμαστε ότι δεν θα χάσουμε περισσότερα από 3. Μικρή παρηγοριά, αλλά ακόμα καλύτερη από, ας πούμε, μια νίκη του 5, που εμφανίζεται σε ορισμένα κελιά της μήτρας. Κακό για εμάς, τον παίκτη ΑΛΛΑ...Ας παρηγορηθούμε όμως:

Η θέση του αντιπάλου φαίνεται να είναι ακόμα χειρότερη: το χαμηλότερο κόστος του παιχνιδιού είναι β = 4, δηλαδή, με λογική συμπεριφορά, θα μας δώσει τουλάχιστον 4. Γενικά, η θέση δεν είναι πολύ καλή - ούτε για έναν ούτε για τον άλλη πλευρά. Ας δούμε όμως αν μπορεί να βελτιωθεί; Αποδεικνύεται ότι μπορείτε. Εάν κάθε πλευρά χρησιμοποιεί όχι μια καθαρή στρατηγική, αλλά μια μικτή, στην οποία

Πίνακας 26.5

το πρώτο και το τρίτο μπαίνουν με πιθανότητα 1/4 και το δεύτερο - με πιθανότητα 1/2, δηλ.

τότε η μέση ανταμοιβή θα είναι σταθερά ίση με το μηδέν (που σημαίνει ότι το παιχνίδι είναι «δίκαιο» και εξίσου ωφέλιμο και για τις δύο πλευρές). Στρατηγικές
αποτελούν μια λύση στο παιχνίδι και την τιμή του v= 0. Πώς βρήκαμε αυτή τη λύση; Αυτή είναι μια διαφορετική ερώτηση. Στην επόμενη ενότητα, δείχνουμε πώς λύνονται γενικά τα πεπερασμένα παιχνίδια.

Σκεφτείτε ένα παιχνίδι πεπερασμένου ζεύγους μηδενικού αθροίσματος. Σημειώστε με έναανταμοιβή του παίκτη ΕΝΑ, και μέσω σι- νίκη παίκτη σι. Επειδή ένα = –σι, τότε κατά την ανάλυση ενός τέτοιου παιχνιδιού δεν χρειάζεται να λάβετε υπόψη και τους δύο αυτούς αριθμούς - αρκεί να εξετάσετε την ανταμοιβή ενός από τους παίκτες. Ας είναι, για παράδειγμα, ΕΝΑ. Στη συνέχεια, για διευκόλυνση της παρουσίασης, η πλευρά ΕΝΑθα ονομάσουμε υπό όρους " εμείς«και το πλάι σι – "εχθρός".

Ας έχουμε Μπιθανές στρατηγικές ΕΝΑ 1 , ΕΝΑ 2 , …, Είμαικαι ο εχθρός nπιθανές στρατηγικές σι 1 , σι 2 , …, B n(ένα τέτοιο παιχνίδι ονομάζεται παιχνίδι m×n). Ας υποθέσουμε ότι κάθε πλευρά έχει επιλέξει μια συγκεκριμένη στρατηγική: έχουμε επιλέξει Ολα συμπεριλαμβάνονται, αντίπαλος Bj. Αν το παιχνίδι αποτελείται μόνο από προσωπικές κινήσεις, τότε η επιλογή των στρατηγικών Ολα συμπεριλαμβάνονταικαι Bjκαθορίζει μοναδικά το αποτέλεσμα του παιχνιδιού - την ανταμοιβή μας (θετική ή αρνητική). Ας υποδηλώσουμε αυτό το κέρδος ως aij(κερδίζουμε όταν επιλέγουμε τη στρατηγική Ολα συμπεριλαμβάνονται, και ο εχθρός - στρατηγικές Bj).

Εάν το παιχνίδι περιέχει, εκτός από προσωπικές τυχαίες κινήσεις, τότε η ανταμοιβή για ένα ζευγάρι στρατηγικών Ολα συμπεριλαμβάνονται, Bjείναι μια τυχαία μεταβλητή που εξαρτάται από τα αποτελέσματα όλων των τυχαίων κινήσεων. Σε αυτή την περίπτωση, η φυσική εκτίμηση της αναμενόμενης απόδοσης είναι μαθηματική προσδοκία μιας τυχαίας νίκης. Για ευκολία, θα υποδηλώσουμε με aijτόσο η ίδια η ανταμοιβή (σε ένα παιχνίδι χωρίς τυχαίες κινήσεις) όσο και η μαθηματική προσδοκία του (σε ένα παιχνίδι με τυχαίες κινήσεις).

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

Ένας τέτοιος πίνακας ονομάζεται μήτρα πληρωμής του παιχνιδιούή απλά μήτρα παιχνιδιού.

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

Σκεφτείτε παράδειγμα 1 4×5 ανταγωνιστικό παιχνίδι. Έχουμε τέσσερις στρατηγικές στη διάθεσή μας, ο εχθρός έχει πέντε στρατηγικές. Η μήτρα του παιχνιδιού είναι η εξής:

Ποια στρατηγική πρέπει να έχουμε (δηλαδή, ο παίκτης ΕΝΑ) χρησιμοποιώ? Όποια στρατηγική κι αν επιλέξουμε, ένας λογικός αντίπαλος θα απαντήσει σε αυτήν με τη στρατηγική για την οποία η ανταμοιβή μας θα είναι ελάχιστη. Για παράδειγμα, αν επιλέξουμε τη στρατηγική ΕΝΑ 3 (δελεάζεται από μια νίκη 10), ο αντίπαλος θα επιλέξει μια στρατηγική ως απάντηση σι 1 , και η ανταμοιβή μας θα είναι μόνο 1. Προφανώς, με βάση την αρχή της προσοχής (και είναι η κύρια αρχή της θεωρίας παιγνίων), πρέπει να επιλέξουμε τη στρατηγική στην οποία το ελάχιστο κέρδος μας είναι το μέγιστο.

Σημειώστε με ένα iελάχιστη αξία απόδοσης για τη στρατηγική Ολα συμπεριλαμβάνονται:

και προσθέστε μια στήλη που περιέχει αυτές τις τιμές στη μήτρα του παιχνιδιού:

Όταν επιλέγουμε μια στρατηγική, πρέπει να επιλέξουμε αυτή για την οποία η αξία ένα iτο μέγιστο. Ας υποδηλώσουμε αυτή τη μέγιστη τιμή με α :

αξία α που ονομάζεται χαμηλότερη τιμή παιχνιδιούή maximin(μέγιστη ελάχιστη νίκη). Στρατηγική παίκτη ΕΝΑπου αντιστοιχεί στο μέγιστο α , λέγεται στρατηγική maximin.

Σε αυτό το παράδειγμα, το maximin α ισούται με 3 (το αντίστοιχο κελί στον πίνακα επισημαίνεται με γκρι) και η στρατηγική μεγιστοποίησης είναι ΕΝΑτέσσερα. Έχοντας επιλέξει αυτή τη στρατηγική, μπορούμε να είμαστε σίγουροι ότι για οποιαδήποτε συμπεριφορά του εχθρού θα κερδίσουμε όχι λιγότερα από 3 (και ίσως περισσότερα με την «παράλογη» συμπεριφορά του εχθρού). Αυτή η τιμή είναι το εγγυημένο ελάχιστο μας, το οποίο μπορούμε να διασφαλίσουμε για τον εαυτό μας, τηρώντας την πιο προσεκτική («αντασφαλιστική») στρατηγική.

Τώρα θα κάνουμε ανάλογο σκεπτικό για τον εχθρό σι σι ΕΝΑ σι 2 - θα του απαντήσουμε ΕΝΑ .

Σημειώστε με βj ΕΝΑ σι) για τη στρατηγική Ολα συμπεριλαμβάνονται:

βj β :

7. ΤΙ ΕΙΝΑΙ ΤΟ ΠΑΙΧΝΙΔΙ ΑΝΩΤΕΡΗΣ ΑΞΙΑΣ Τώρα θα κάνουμε παρόμοιο σκεπτικό για τον αντίπαλο σι. Ενδιαφέρεται να ελαχιστοποιήσει το κέρδος μας, να μας δώσει δηλαδή λιγότερα, αλλά πρέπει να υπολογίζει στη συμπεριφορά μας, που είναι ό,τι χειρότερο για εκείνον. Για παράδειγμα, αν επιλέξει τη στρατηγική σι 1 , τότε θα του απαντήσουμε με μια στρατηγική ΕΝΑ 3 , και θα μας δώσει 10. Αν το επιλέξει σι 2 - θα του απαντήσουμε ΕΝΑ 2 , και θα δώσει 8, και ούτω καθεξής. Προφανώς, ένας προσεκτικός αντίπαλος πρέπει να επιλέξει τη στρατηγική με την οποία το μέγιστο κέρδος μας θα είναι ελάχιστο.

Σημειώστε με βjοι μέγιστες τιμές στις στήλες του πίνακα πληρωμών (η μέγιστη απόδοση του παίκτη ΕΝΑ, ή, που είναι το ίδιο, η μέγιστη απώλεια του παίκτη σι) για τη στρατηγική Ολα συμπεριλαμβάνονται:

και προσθέστε μια σειρά που περιέχει αυτές τις τιμές στη μήτρα του παιχνιδιού:

Επιλέγοντας μια στρατηγική, ο εχθρός θα προτιμήσει αυτή για την οποία η αξία βjελάχιστο. Ας το χαρακτηρίσουμε με β :

αξία β που ονομάζεται κορυφαία τιμή παιχνιδιούή ελάχιστη(ελάχιστη μέγιστη νίκη). Η στρατηγική του αντιπάλου (του παίκτη) που αντιστοιχεί στο minimax σι), λέγεται στρατηγική minimax.

Minimax είναι η τιμή του κέρδους, περισσότερο από αυτό που σίγουρα δεν θα μας δώσει ένας λογικός αντίπαλος (με άλλα λόγια, ένας λογικός αντίπαλος δεν θα χάσει περισσότερο από β ). Σε αυτό το παράδειγμα, minimax β ισούται με 5 (το αντίστοιχο κελί στον πίνακα επισημαίνεται με γκρι) και επιτυγχάνεται με τη στρατηγική του αντιπάλου σι 3 .

Με βάση λοιπόν την αρχή της προσοχής («να περιμένεις πάντα το χειρότερο!»), πρέπει να επιλέξουμε στρατηγική ΕΝΑ 4, και ο εχθρός - μια στρατηγική σι 3 . Η αρχή της προσοχής είναι θεμελιώδης στη θεωρία παιγνίων και καλείται Αρχή minimax.

Σκεφτείτε παράδειγμα 2. Αφήστε τους παίκτες ΕΝΑκαι ΣΤΟένας από τους τρεις αριθμούς γράφεται ταυτόχρονα και ανεξάρτητα ο ένας από τον άλλο: είτε "1", είτε "2", είτε "3". Αν το άθροισμα των γραμμένων αριθμών είναι ζυγό, τότε ο παίκτης σιπληρώνει τον παίκτη ΕΝΑαυτό το ποσό. Εάν το ποσό είναι μονό, τότε ο παίκτης πληρώνει αυτό το ποσό ΕΝΑπαίχτης ΣΤΟ.

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

Παίχτης ΕΝΑπρέπει να τηρεί τη στρατηγική maximin ΕΝΑ 1 να κερδίσει τουλάχιστον -3 (δηλαδή να χάσει το πολύ 3). Minimax Player Strategy σιοποιαδήποτε από τις στρατηγικές σι 1 και σι 2, που εγγυάται ότι δεν θα δώσει περισσότερα από 4.

Το ίδιο αποτέλεσμα θα έχουμε αν γράψουμε τον πίνακα πληρωμής από την πλευρά του παίκτη ΣΤΟ. Στην πραγματικότητα, αυτή η μήτρα λαμβάνεται με τη μεταφορά της μήτρας που έχει κατασκευαστεί από τη σκοπιά του παίκτη ΕΝΑ, και αλλάζοντας τα σημάδια των στοιχείων στο αντίθετο (από την πληρωμή του παίκτη ΕΝΑείναι η απώλεια του παίκτη ΣΤΟ):

Με βάση αυτόν τον πίνακα, προκύπτει ότι ο παίκτης σιπρέπει να ακολουθήσει οποιαδήποτε από τις στρατηγικές σι 1 και σι 2 (και μετά δεν θα χάσει περισσότερα από 4), και ο παίκτης ΕΝΑ– στρατηγικές ΕΝΑ 1 (και μετά δεν θα χάσει περισσότερα από 3). Όπως μπορείτε να δείτε, το αποτέλεσμα είναι ακριβώς το ίδιο με αυτό που λήφθηκε παραπάνω, επομένως η ανάλυση δεν έχει σημασία από την άποψη του παίκτη που τη διενεργούμε.

8 ΤΙ ΕΙΝΑΙ ΕΝΑ ΠΟΛΥΤΙΜΟ ΠΑΙΧΝΙΔΙ.

9. ΑΠΟ ΤΙ ΑΠΟΤΕΛΕΙΤΑΙ Η ΑΡΧΗ MINIMAX. 2. Χαμηλότερη και ανώτερη τιμή του παιχνιδιού. Αρχή Minimax

Εξετάστε ένα παιχνίδι μήτρας του τύπου με μήτρα πληρωμής

Αν ο παίκτης ΑΛΛΑθα επιλέξει στρατηγική A i, τότε όλες οι πιθανές απολαβές του θα είναι στοιχεία Εγώ-η σειρά του πίνακα ΑΠΟ. Το χειρότερο για έναν παίκτη ΑΛΛΑπερίπτωση όταν ο παίκτης ΣΤΟεφαρμόζει μια στρατηγική κατάλληλη για ελάχιστοστοιχείο αυτής της γραμμής, η ανταμοιβή του παίκτη ΑΛΛΑθα είναι ίσο με τον αριθμό.

Επομένως, για να πάρει τη μέγιστη απόδοση, ο παίκτης ΑΛΛΑπρέπει να επιλέξετε μία από τις στρατηγικές για τις οποίες ο αριθμός το μέγιστο.

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

Στην ορολογία της θεωρητικής παιγνίων, το 1ο υποσύστημα ελέγχου ονομάζεται παίκτης 1, 2ο υποσύστημα ελέγχου - παίκτης 2, σκηνικά

ονομάζονται εναλλακτικές δράσεις τους σύνολα στρατηγικώναυτούς τους παίκτες. Αφήνω Χ- σύνολο στρατηγικών παίκτη 1, Υ- πολλές στρατηγικές

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

Χ∈Χκαι y∈Υ. Αφήνω φά(Χ,y) - εκτίμηση χρησιμότητας για τον παίκτη 1 αυτής της κατάστασης

το σύστημα στο οποίο περνά όταν ο παίκτης 1 επιλέγει μια στρατηγική Χκαι

στρατηγική παίκτη 2 στο. Αριθμός φά(Χ,y) λέγεται επιτυχήςπαίκτης 1 στην κατάσταση ( Χ,y), και τη συνάρτηση φά- Λειτουργία πληρωμής παίκτη 1. Νίκη παίκτη

Το 1 είναι επίσης η απώλεια του παίκτη 2, δηλαδή η αξία που ο πρώτος παίκτης επιδιώκει να αυξήσει και ο δεύτερος - να μειώσει. Αυτό είναι

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

Ένα ανταγωνιστικό παιχνίδι ορίζεται φυσικά από το σύστημα G=(Χ, Υ, Φ).

Σημειώστε ότι τυπικά το ανταγωνιστικό παιχνίδι τίθεται στην πραγματικότητα με τον ίδιο τρόπο όπως το πρόβλημα της λήψης απόφασης υπό συνθήκες αβεβαιότητας - εάν

ταυτοποίηση του υποσυστήματος ελέγχου 2 με το περιβάλλον. Η ουσιαστική διαφορά μεταξύ του υποσυστήματος ελέγχου και του περιβάλλοντος είναι ότι

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

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

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

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

Ορισμός.Αν ένα Χκαι Υείναι πεπερασμένα, τότε το ανταγωνιστικό παιχνίδι ονομάζεται μήτρα. Στο παιχνίδι matrix, μπορούμε να το υποθέσουμε Χ={1,…,n},

Υ={1,…,Μ) και βάλε aij=F(i,j). Έτσι, το παιχνίδι matrix καθορίζεται πλήρως από το matrix Α=(aij), Εγώ=1,…,n, j=1,…,Μ.

Παράδειγμα 3.1. Παιχνίδι με δύο δάχτυλα.

Δύο άτομα δείχνουν ταυτόχρονα ένα ή δύο δάχτυλα και καλούν τον αριθμό 1 ή 2, που, σύμφωνα με τον ομιλητή, σημαίνει τον αριθμό

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

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

Αυτό είναι ένα ανταγωνιστικό παιχνίδι matrix. Κάθε παίκτης έχει τέσσερις στρατηγικές: 1- δείξτε 1 δάχτυλο και πείτε 1, 2- δείξτε 1 δάχτυλο και πείτε 2, 3-

δείξτε 2 δάχτυλα και πείτε 1, 4 - δείξτε 2 δάχτυλα και πείτε 2. Στη συνέχεια, ο πίνακας πληρωμής A=(aij), i= 1,…, 4, j= 1,…, 4 ορίζεται ως εξής:

a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 διαφορετικά.

Παράδειγμα 3.2. Διακριτικό παιχνίδι τύπου μονομαχίας.

Οι εργασίες τύπου μονομαχίας περιγράφουν, για παράδειγμα, τον αγώνα δύο παικτών,

καθένα από τα οποία θέλει να εκτελέσει κάποια εφάπαξ ενέργεια (απελευθέρωση μιας παρτίδας αγαθών στην αγορά, μια αίτηση για αγορά σε μια δημοπρασία) και επιλέγει ένα χρόνο για αυτό. Αφήστε τους παίκτες να κινηθούν ο ένας προς τον άλλο nβήματα. Μετά από κάθε βήμα που γίνεται, ο παίκτης μπορεί να πυροβολήσει ή όχι στον αντίπαλο. Κάθε άτομο μπορεί να έχει μόνο μία βολή. Πιστεύεται ότι η πιθανότητα να χτυπήσετε τον εχθρό εάν προχωρήσετε κ n =5 έχει τη μορφή