Το Tetris αναδεικνύεται ένα από τα πιο δύσκολα προβλήματα μαθηματικών

39

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

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

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

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

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

Ένα ακόμα πρόβλημα NP-πλήρες είναι ο ναρκαλιευτής, αναφέρει το Scientific American. Οπότε, την επόμενη φορά που θα αποτύχετε σε ένα από τα δύο αυτά προβλήματα θα ξέρετε ότι και ένας υπολογιστής δεν θα τα κατάφερνε πολύ καλύτερα -τουλάχιστον σε ικανοποιητικό χρόνο.

Newsroom ΑΛΤΕΡ ΕΓΚΟ