Σάββατο, 10 Ιανουαρίου 2015

4.11 IF THEN ELSE : Τεχνητή Νοημοσύνη ,αλγόριθμος Minimax και έκβαση του επεισοδίου





Ας ξεκινήσω με αυτό σαν πρώτο άρθρο μιας και είχα άλλο στο μυαλό μου για πρώτο μου άρθρο αλλά θα το βγάλω άλλη μέρα. Ας εμβαθύνουμε λίγο περισσότερο στο καταπληκτικό επεισόδιο 4.11 Ιf Τhen Else.Μέσα απο το επεισόδιο έγινε αναφορά σε μια μορφή Τεχνητής Μάθησης και συγκεκριμένα στον αλγόριθμο Minimax που είναι μέρος της Τεχνητής Νοημοσύνης σε συνάρτηση και με άλλες μεθόδους με τις οποίες λειτούργησε η Μηχανή στο συγκεκριμένο επεισόδιο..Εδώ θα επικεντρωθούμε στον αλγόριθμο Minimax.


Και στα δύο παιχνίδια σκάκι με το Harold η Μηχανή μέσω της προσομοίωσης χρησιμοποιούσε εναν αλγόριθμο που στην επιστήμη της πληροφορικής λέγεται Minimax . Ο αλγόριθμος αυτός ουσιαστικά εγγυάται πάντα την πιο συμφέρουσα εξέλιξη του παιχνιδιού, υποθέτοντας ότι ο αντίπαλος επιλέγει διαρκώς τις καλύτερες για εκείνον κινήσεις και δεν κάνει λάθη.Kαλείται να αποφασίσει ποια θα είναι η επόμενη κίνηση του εναντίον του αντιπάλου. Κάθε φορά που εκτελείται αναπτύσσει το δένδρο του παιχνιδιού με ρίζα την τρέχουσα κατάσταση και ως ένα προκαθορισμένο βάθος, στη συνέχεια αποδίδει στα ευρετικές τιμές οι οποίες αξιολογούν τις αντίστοιχες καταστάσεις ως ευνοϊκές γι' αυτόν (μεγάλες τιμές)Max ή για τον αντίπαλο (μικρές τιμές)Mini,.Με τον Minimax υπάρχουν πάντα δυνατές κινήσεις οι οποίες φαίνεται να συμφέρουν περισσότερο αλλά αγνοούνται όμως όταν μπορεί να οδηγήσουν σε καταστάσεις όπου ο αντίπαλος -αν κάνει την καλύτερη επιλογή- αποκτά προβάδισμα. Ο αλγόριθμος AB (Άλφα Βήτα) είναι παραλλαγή του εξαντλητικού Minimax με κλάδεμα προκειμένου να εξοικονομηθεί χρόνος, όπου αγνοούνται καταστάσεις-παραλλαγές οι οποίες αποκλείεται να δώσουν την επιθυμητή έκβασή στο τέλος.


Ο αλγόριθμος Minimax συγκεκριμένα αποτελεί και μέρος/κανόνα της Τεχνητής Νοημοσύνης,να επιδιώκει το καλύτερο δυνατό αποτέλεσμα. Χρησιμοποιείται κυρίως σε "Μαθηματικά " παιχνίδια.Ειναι ο καλύτερος αλγόριθμος για να κερδίσεις παιχνίδια όταν όλοι οι παίχτες(ή αλλιώς παράγοντες) παίζουν/δρουν με το καλύτερο δυνατό τρόπο.


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


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




Έστω οτι ένας απο τους δύο αντιπάλους είναι ο υπολογιστής.

  • Το πρόγραμμα αναζήτησης πρέπει να εξετάσει όλες τις πιθανές κινήσεις που παράγονται απο μια αρχική κατάσταση. 
  • Ενα τέτοιο πρόγραμμα μπορεί να προβλέψει την έκβαση του παιχνιδιού μετά απο 10 κινήσεις.Ο άνθρωπος σταματά συνήθως μετά την πρόβλεψη 2 ή 3 κινήσεων. 

Παραδόξως οι διαφορές αυτές δεν κάνουν κάποιο πρόγραμμα τον "απόλυτο κυρίαρχο" οποιουδήποτε παιχνιδιού έναντι του ανθρώπου.Η ανωτερότητα των ανθρώπων έγκειται στους εξής παράγοντες:
  • Οι άνθρωποι επιλέγουν με κάποιον ευριστικό/δικό τους τρόπο τις εναλλακτικές κινήσεις. 
  • Διαθέτουν κάποια διαίσθηση για την κατάληξη του παιχνιδιού. 
  • Με την εμπειρία που αποκτούν μπορούν να σκέφτονται πολλές φορές εντελώς μηχανικά,ιδίως στα πρώτα και τελευταία στάδια του παιχνιδιού.





Μηχανή εναντίον Harold στο σκάκι:

Όπως ο Harold είπε , υπάρχουν περισσότερα πιθανά παιχνίδια σκάκι απ' όσα άτομα υπάρχουν στο σύμπαν. Κανένας δεν θα μπορεί να τα προβλέψει όλα.Είναι αδύνατο να υπολογίσεις κάθε μοναδική πιθανή κίνηση ακόμα και για εναν υπερυπολογιστή-ισχυρή τεχνητή νοημοσύνη. Αυτό το δέντρο του παιχνιδιού θα είναι υπερβολικά μεγάλο.

Υπάρχουν 2 μέθοδοι που χρειάζονται για να επιταχύνουν τα πράγματα (βλέπε προσομοίωση είχε 3 δευτερόλεπτα να κάνει τους υπολογισμούς.) :

1) Αποκλείοντας όλες τις πιθανές ενέργειες που οι παίχτες μπορεί να κάνουν (τις προφανές/στανταρ κινήσεις) γιατί και οι δύο έχουν πολυ καλύτερες δυνατές κινήσεις διαθέσιμες να κάνουν. Έτσι προχωράει σε κλάδεμα AB.


2)Να μήν προβλέψει το παιχνίδι μέχρι το τέλος,ας πούμε οτι προβλέπουμε τις 10 κινήσεις στο μέλλον.Ωστόσο, δεν μπορεί σε αυτή τη φάση να υπολογίσει την έκβαση της βαθμολογίας της κατάστασης της σκακιέρας με αυτό τον τρόπο. Οπότε χρειάζεται εναν τρόπο για να υπολογίσει πόσο καλά ειναι στημένη η σκακιέρα στην παρούσα φάση και αναλόγως με τα "πιόνια" και τις θέσεις τους στην σκακιέρα ποια μπορεί να είναι η πιθανή έκβαση της/το τελικό σκορ.


Υπάρχουν 3 σημαντικές φάσεις στη Μηχανή όταν παίζει εναντίον του Harold


1)Στην αρχή ο Finch περίμενε ώρες την Μηχανή να κάνει κάποια κίνηση. Η Μηχανή υπολόγιζε κάθε πιθανή κίνηση (brute force) και τις έπαιρνε "αιώνες" ωστε να κάνει την πρώτη κίνηση.Ο Finch είπε στη μηχανή οτι πρέπει να διαλέξει, δεν μπορεί να υπολογίζει για πάντα.(πράγμα που ήταν πολύ σημαντικό όπως είδαμε για τις προσομοιώσεις στο υπόλοιπο του επεισοδίου.).

2)Θυμάστε αυτές τις 2 βελτιστοποιήσεις που εκτέλεσε η Μηχανή; Η Μηχανή άρχισε να τις χρησιμοποιεί και ξεκίνησε να παίζει το παιχνίδι...Δεν προέβλεπε όλο το παιχνίδι πλέον αλλά μόνο λίγες κινήσεις μπροστά.Έτσι πώς έκανε τον υπολογσιμό της βαθμολογίας της σκακιέρας; Ανέλυσε το κάθε κομμάτι και είπε οτι ένα πιόνι δεν αξίζει πολύ καθώς για κάθε πιόνι στη σκακιέρα η βαθμολογία αυξάνεται κατα 1 ενώ απο την άλλη μεριά η Βασίλισσα ήταν πολύ πιο δυνατή (επέτρεπε μεγαλύτερο εύρος κινήσεων) και άξιζε 100 πόντους.Μια βασική κίνηση ενός ευρετικου μηχανισμού είναι να προστατέψεις τη βασίλισσα με πιόνια γιατί η αξία της είναι 99 φορές υψηλότερη απο αυτήν ενός πιονιού,έτσι το σκόρ θα ήταν καλύτερο..Ο Finch είπε οτι το να προστατεύεις την Βασίλισσα δεν είναι πάντα η καλύτερη στρατηγική/κίνηση,μερικές φορές το να την θυσιάζεις είναι καλύτερα,η Μηχανή έχασε καθώς στην προσπάθεια της να προστατέψει την βασίλισσα άφησε εκτεθειμένο τον Βασιλιά..

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



Η Μηχανή εναντίον του Σαμαρείτη και των πρακτόρων

Σε ενα πολύ πιο περίπλοκο σενάριο όπως αυτό με άπειρες ενέργειες και πιθανές καταστάσεις η Μηχανή έπρεπε να κάνει πολύ σκλήρο optimization,δηλαδή να χρησιμοποιήσει πολύ δύσκολες βελτιστοποιήσεις σε ελάχιστο χρόνο.. Εξέταζε τα πιο πιθανά σενάρια και δεν μπορούσε να προβλέψει το τέλος γιατί ήταν πολύ μακριά στο μέλλον. Είχε μόνο 3 δευτερόλεπτα να διαλέξει την καλύτερη ακολουθία/σειρά ενεργειών/κινήσεων..Κάθε ενέργεια ενός μέλους μιας κατάστασης της προσομοίωσης πιθανόν υπολογιζόταν σε λιγότερο απο ένα χιλιοστό του δευτερολέπτου. Η Shaw ήταν σε ένα απο τα κλαδιά του δέντρου(ενεργειών/κινήσεων).Η πιθανότητα όμως η Shaw να μπορούσε να βοηθήσει με κάθε τρόπο ηταν πολύ χαμηλή για να σπαταλήσει επιπλέον χρόνο η Μηχανή (καθώς στις 2 αρχικές προσομοιώσεις η Shaw κατέληγε να τη συλλάβουν, έτσι στην τρίτη και τελική προσομοίωση λόγω υπερβολικά περιορισμένου χρόνου για επιπλέον υπολογισμούς ,τα κριτήρια για την τελική έκβαση και πιθανά άλλα ενδεχόμενα περιορίστηκαν δραστικά.Έτσι στην τελική προσομοίωση οσο αναφορά το τέλος της δεν είχε υπολογίσει στην προσομοίωση την εμφάνιση/βοήθεια της Shaw με οποιοδήποτε τρόπο.(σαν πιθανό σενάριο υπήρχε αλλά ήταν χαμένο κάπου μέσα στις απεριόριστες επιλογές)

Όπως είδαμε η Μηχανή προέβλεψε σωστά οτι η αγορά θα σταθεροποιηθεί και οτι η ομάδα είχε 2% πιθανότητες για να επιβιώση.Αυτό ήταν το καλύτερο δυνατό σενάριο που μπορούσε να υπολογιστεί στο παρόν χρονικό διάστημα 3 δευτερολέπτων.Μπορούμε να δούμε και το 3D δέντρο ενεργειών που τρέχουν στο παρασκήνιο.





Αποδεικνύεται όμως τελικά οτι η Μηχανή δεν προέβλεψε ακριβως την έκβαση των γεγονότων αφού χτυπήθηκε ο Reese στην προσπάθεια του να προστατέψει τον Finch και έτσι βλέπουμε η πιθανότητα επιβίωσης της ομάδας να κατεβαίνει κάτω απο το 2% πηγαίνοντας προς το 0% μέχρι που εμφανίστηκε η Shaw.Μια πολύ απίθανη περίπτωση που η Μηχανή δεν υπολόγισε για λόγους απόδοσης (δεδομένου οτι είχε 3 δευτερόλεπτα να υπολογίσει άπειρα σενάρια. ).Έτσι με την εμφάνιση της βλέπουμε οτι αυξάνονται οι πιθανότητες επιβίωσης φτάνοντας στο 22.48% ενώ συνεχίζουν να αυξάνονται.


Οι πιθανότητες επιβίωσης κατεβαίνουν πιο κάτω και απο 2% μετά το τραυματισμό του Reese. 

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

Δεν μπορούμε παρά να μιλήσουμε για ένα αριστούργημα επεισοδίου απο τους σεναριογράφους της σειράς,την σκηνοθεσία ,την απόδοση των ηθοποιών στους ρόλους τους και πώς ξεχωρίζουν όταν απλά εκτελούνε το ρόλο τους σε τέτοια ποιότητα. Και μην ξεχνάμε την απίστευτη δουλειά που γίνεται απο το crew του POΙ και την ομάδα που κάνει τα 3D .Επάξια λοιπόν πήρε 9.9 στο IMBD το επεισόδιο.

And that my friends είναι το πώς μπορείς να φτιάξεις μια επεισοδιάρα..
Εύγε Peson of Interest !!!My rescpect .. DimitrisD.

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου