Οι δημιουργοί του δημοφιλούς μαθηματικού παιχνιδιού γρίφων «Digit Party», Vincent Vatter από το Πανεπιστήμιο της Φλόριντα και Robert Brignall από το The Open University, δημοσίευσαν μια μελέτη στο περιοδικό «Math Horizons» αποκαλύπτοντας ότι για τρία χρόνια το σύστημά τους εμφάνιζε λανθασμένα τα ανώτατα δυνατά σκορ.
Το πρόβλημα της βελτιστοποίησης
Στο «Digit Party», οι παίκτες τοποθετούν αριθμούς σε ένα πλέγμα 5×5 με στόχο να ενώσουν όμοιους αριθμούς για να συγκεντρώσουν βαθμούς. Οι μαθηματικοί δεν μπορούσαν αρχικά να υπολογίσουν με ακρίβεια το απόλυτο μέγιστο σκορ για κάθε πιθανό συνδυασμό. Έτσι, εφάρμοζαν μια προσέγγιση που στο 5% των περιπτώσεων έδινε ένα σκορ το οποίο ήταν πρακτικά αδύνατο να επιτευχθεί. Από τις 1.096 καθημερινές πίστες των τελευταίων τριών ετών, το παιχνίδι έδωσε λανθασμένο μέγιστο σκορ συνολικά 55 φορές, με μια μικρή απόκλιση από 2 έως 6 βαθμούς.
Η μαθηματική λύση
Το ζήτημα αυτό αποτελεί κλασικό πρόβλημα συνδυαστικής βελτιστοποίησης, όπου η βέλτιστη λύση για ένα επιμέρους τμήμα δεν οδηγεί πάντα στη βέλτιστη συνολική λύση. Παρά τα 13,9 εκατομμύρια πιθανά σετ αριθμών, οι ερευνητές κατάφεραν να ομαδοποιήσουν τις καταστάσεις σε 1.291 βασικά μαθηματικά μοτίβα και διαπίστωσαν ότι μόνο 400 περιπτώσεις απαιτούσαν πραγματικούς συμβιβασμούς στην τοποθέτηση.
Υπολογίζοντας όλες τις πιθανές παραχωρήσεις, όπως τη θυσία των μικρότερων αριθμών υπέρ των μεγαλύτερων, επέτρεψαν στον αλγόριθμο να εμφανίζει πλέον το πραγματικό μέγιστο σκορ.
Παρά την επίλυση του υπολογισμού του μέγιστου σκορ, οι ίδιοι οι δημιουργοί παραδέχονται ότι η ιδανική στρατηγική για τον παίκτη παραμένει ακόμα ένα ανοιχτό μαθηματικό ζήτημα.