Το περίφημο σκακιστικό πρόβλημα που κανένας υπολογιστής δεν μπορεί να λύσει facebook twitter

Ένα δημοφιλές σκακιστικό πρόβλημα, ο Γρίφος της Βασίλισσας, έχει πονοκεφαλιάσει μαθηματικούς, σκακιστές και πληροφορικούς για δεκαετίες και δεκαετίες, αν και κανείς δεν έχει βρει έναν αλγόριθμο που να τον λύνει εύκολα και αποτελεσματικά.


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

Ο γρίφος υπάρχει από τη δεκαετία του 1850 και μας προκαλεί να τοποθετήσουμε 8 βασίλισσες σε μια σκακιέρα έτσι ώστε καμία από αυτές να μην μπορεί να επιτεθεί στην άλλη.

Το σκακιστικό πρόβλημα έχει λυθεί από τους ανθρώπους, καθώς έχουν προταθεί 92 λύσεις από τους 4.426.165.368 πιθανούς συνδυασμούς τοποθέτησης των 8 βασιλισσών στην ασπρόμαυρη σκακιέρα, αν και τόσο οι μαθηματικοί όσο και οι πληροφορικοί δεν μπορούν να βρουν μια μαγική και γρήγορη φόρμουλα.

Όσο μάλιστα η σκακιέρα γίνεται μεγαλύτερη και τοποθετούνται περισσότερες βασίλισσες, τότε το πράγμα γίνεται σαφώς δυσκολότερο, όπως μας λέει η μελέτη που δημοσιεύτηκε στο «The Journal of Artificial Intelligence Research», και ισχυρίζεται ότι είναι πρακτικά αδύνατο για έναν υπολογιστή να το λύσει σε εύλογο χρονικό διάστημα!

«Υπολογιστικά κοστοβόρο» το λένε, καθώς σε μια σκακιέρα 27x27 τετραγώνων υπάρχουν 2,34 τετράκις εκατομμύρια πιθανές λύσεις. Όταν μάλιστα η σκακιέρα φτάσει στα 1.000x1.000 τετράγωνα και ο υπολογιστής πρέπει να τοποθετήσει 1.000 βασίλισσες, τότε χάνεται στην άβυσσο των τρελά μεγάλων αριθμών.

Όπως μας λέει ο επικεφαλής της έρευνας και καθηγητής πανεπιστημίου Ian Gent, κάθε υπολογιστής (ακόμα και τα θρυλικά supercomputers) θα χρειάζονταν χιλιάδες χρόνια για να βρουν την αποδοτικότερη λύση και ο ερευνητής είναι έτοιμος να στοιχηματίσει 1 εκατ. δολάρια σε αυτό! Ποσό που προσφέρεται πράγματι από το αμερικανικό Clay Mathematics Institute.

Ο Gent μας λέει ότι όποιος καταφέρει να λύσει με κάποιο πρόγραμμα τον Γρίφο της Βασίλισσας, τότε θα έχει στα χέρια του έναν πανίσχυρο αλγόριθμο που θα μπορούσε να διαχειριστεί και τα άλλα σχεδόν αδύνατα προβλήματα της ανθρωπότητας, όπως η αποκωδικοποίηση των σοβαρότερων κρυπτογραφημάτων. Επιμένει πάντως πως το τυράκι είναι αυτό το «πολύ γρήγορα», καθώς αυτό θέλει από τις μηχανές.

Οι οποίες φαίνεται να αποτυγχάνουν εκεί που οι σκακιστές τα καταφέρνουν εμπειρικά…

Πηγή: newsbeast.gr

Πηγή: http://ift.tt/2gIkY8L

loading...