Minimax - Τι είναι, ορισμός και έννοια
Το ελάχιστο, στη θεωρία του παιχνιδιού, είναι μια μέθοδος που στοχεύει στην ελαχιστοποίηση της αναμενόμενης απώλειας. Για να το κάνει αυτό, ο παίκτης υποθέτει ότι η απόφαση που έλαβε ο αντίπαλός του θα είναι δυσμενής. Δηλαδή, το χειρότερο σενάριο αναμένεται πριν από την κίνηση του αντιπάλου.
Για να το θέσω με άλλο τρόπο, η ελάχιστη μέθοδος αποτελείται από τον τρόπο λήψης της καλύτερης απόφασης, υποθέτοντας ότι ο άλλος παίκτης θα επιλέξει το χειρότερο σενάριο για εσάς.
Πρέπει να λάβουμε υπόψη ότι αυτή η μέθοδος εφαρμόζεται σε ένα παιχνίδι δύο ατόμων (δύο παίκτες) και ότι δεν είναι συνεταιριστικό, αλλά ένα παιχνίδι μηδενικού αθροίσματος. Αυτό σημαίνει ότι αυτό που κερδίζει ένας παίκτης χάνεται από τον άλλο και αντίστροφα. Κατά συνέπεια, κάθε πράκτορας θα ενδιαφέρεται να μεγιστοποιήσει τη δική του χρησιμότητα, ακόμα κι αν αυτό βλάπτει τον άλλο.
Σε αυτό το σημείο, πρέπει επίσης να θυμόμαστε ότι η θεωρία του παιχνιδιού είναι ένας κλάδος μαθηματικών και οικονομικών που μελετά την επιλογή που βελτιστοποιεί την κατάσταση ενός ατόμου όταν το κόστος και τα οφέλη δεν καθορίζονται εκ των προτέρων, αλλά εξαρτώνται από τις αποφάσεις άλλων.
Ελάχιστος αλγόριθμος σε ένα δέντρο αποφάσεων
Μπορούμε να δούμε πώς εφαρμόζεται η μέθοδος ελαχιστοποίησης σε ένα δέντρο αποφάσεων με πολλούς κόμβους. Το παιχνίδι ξεκινά στο κάτω μέρος και τελειώνει με αποτέλεσμα στο ανώτερο επίπεδο.
Στη βάση του δέντρου, ο αντίπαλος κάνει την πρώτη κίνηση, οπότε αναμένεται το χειρότερο αποτέλεσμα. Στη συνέχεια, στο δεύτερο επίπεδο, εναπόκειται στον παίκτη x που θα επιδιώξει να μεγιστοποιήσει το κέρδος του, λαμβάνοντας υπόψη την απόφαση που είχε λάβει προηγουμένως ο αντίπαλος.
Στο τρίτο επίπεδο, είναι και πάλι η σειρά του αντιπάλου και ούτω καθεξής. Θα δείξουμε ένα παράδειγμα παρακάτω.
Παράδειγμα ελάχιστου αλγορίθμου
Στο δέντρο αποφάσεων που ακολουθεί, δείχνουμε τα αποτελέσματα που λαμβάνονται από τον παίκτη x σε κάθε στιγμή του παιχνιδιού. Στη βάση, στο πρώτο επίπεδο, ο αντίπαλος παίρνει την απόφαση. Για αυτόν τον λόγο, δίνονται τα σενάρια στα οποία ο παίκτης μπορεί να χάσει -10 ή να κερδίσει 5.
Στο δεύτερο επίπεδο, εξαρτάται από τον παίκτη x, οπότε θα μεγιστοποιήσει τα κέρδη του. Μεταξύ της απώλειας 10 ή της νίκης 1, θα κερδίσετε 1. Ομοίως, μεταξύ της νίκης 5 ή 7, θα κερδίσετε 7.
Στη συνέχεια, είναι και πάλι η σειρά του αντιπάλου, έτσι θα δοθούν τα σενάρια στα οποία ο παίκτης x έχει το χειρότερο αποτέλεσμα, -3 και 4, ανάλογα με την περίπτωση. Τέλος, μεταξύ της απώλειας 3 ή της νίκης 4, ο παίκτης x θα πάρει την απόφαση που θα επιτρέψει το τελευταίο.
Πρέπει να λάβουμε υπόψη ότι οι τιμές κάθε κόμβου θα εξαρτηθούν από μια συνάρτηση χρησιμότητας.
Για να κατανοήσετε καλύτερα το δέντρο, ας υποθέσουμε ότι στη βάση η απόφαση αφορά τη διανομή του προϊόντος. Ο αγωνιζόμενος (ο αντίπαλος) μπορεί να αναθέσει τη διανομή (δείτε την αριστερή πλευρά του δέντρου). Σε αυτήν την περίπτωση, πρέπει να επιλέξει, για παράδειγμα, μεταξύ του ντίλερ Α και του Β. Έτσι, επιλέγει τον πρώτο, προκαλώντας στον παίκτη x να χάσει 10 (Εάν επέλεξε Β, ο παίκτης x θα κερδίσει 12).
Ωστόσο, ίσως ο αντίπαλος προτιμά να διανείμει τα ίδια τα εμπορεύματά του, έχοντας τη δυνατότητα να νοικιάσει μηχανοκίνητα οχήματα ή να αγοράσει φορτηγό. Και από τα δύο σενάρια, επιλέξτε το πρώτο που είναι λιγότερο κολακευτικό για τον παίκτη x επειδή κερδίζει 5 και όχι 10.
