Τρίτη, 29 Μαρτίου 2011

Πτυχιακή.



Στις 28 Απριλίου παραδίνω πτυχιακή, μετά στις 11 Μαΐου πρέπει να κάνω μια δημόσια παρουσίαση - το "Poster session" που λένε. Το λένε έτσι επειδή υποτίθεται οτι φτιάχνεις μια ας την πούμε αφίσσα, που να εξηγεί την πτυχιακή σου, και την αναρτάς σ' έναν πίνακα για να έχεις κάτι να δείχνεις όσο κάνεις την παρουσίαση. Η δική μου πτυχιακή είναι λογισμικό οπότε δεν χρειάζεται να κάνω τέτοιες ιστορίες αλλά ίσως φτιάξω έναν πίνακα με διαγράμματα κλπ. Την ημέρα της παρουσίασης, πρέπει κατ' αρχήν να παρουσιάσω τη δουλειά μου στους δύο εξεταστές και έπειτα σε όποιον άλλον ενδιαφέρεται.

Το λογισμικό μου τώρα, είναι ένα πρόγραμμα τεχνητής νοημοσύνης- ενα έμπειρο σύστημα (expert system). "Έμπειρο σύστημα" εννοούμε συνήθως ένα πρόγραμμα που έχει σκοπό να κωδικοποιήσει την γνώση των ειδικών σε κάποιον τομέα, ωστε να χρησιμοποιηθεί (και από μη-ειδικούς) συνήθως για την εξαγωγή συμπερασμάτων και τη λήψη αποφάσεων. Για παράδειγμα, ένα από τα πρώτα έμπειρα συστήματα ήταν το MYCIN, που ο σκοπός του ήταν να βοηθήσει στη διάγνωση βακτηριακών μολύνσεων.

Ο τομέας που έχει εφαρμογή το πρόγραμμά μου είναι ένα επιτραπέζιο παιχνίδι στρατηγικής με συλλεκτικές κάρτες, το Magic: the Gathering. Είναι ένα παιχνίδι που έπαιζα πολύ σε μικρότερη ηλικία. Πλέον δεν μ' ενδιαφέρει τόσο το παιχνίδι (έχω χρόνια να παίξω) όσο κάποια χαρακτηριστικά του που είναι κλασσικά προβλήματα που εξετάζει η τεχνητή νοημοσύνη.



Κατ' αρχήν οι κάρτες με τις οποίες παίζεται το παιχνίδι έχουν πάνω τους κείμενο που εξηγεί πως παίζεται η κάρτα. Αυτό το κείμενο είναι σε μια γλώσσα που είναι σχεδόν Αγγλικά, δηλαδή σχεδόν φυσική γλώσσα. Λέω "σχεδόν" επειδή έχει ιδιαίτερη σύνταξη και σύμβολα, τα οποία κάνουν την κατανόησή της από ένα πρόγραμμα ευκολότερη υπόθεση απ' ό,τι αυτή της φυσικής γλώσσας (ιδίως των Αγγλικών που είναι παναήα μου, απ' αυτήν την άποψη). Η γλώσσα αυτή είναι στην ουσία μια γλώσσα προγραμματισμού. Ένα μέρος λοιπόν του προγράμματός μου ασχολείται μ' αυτό ακριβώς: διαβάζει το κείμενο των καρτών και το εκτελεί κατευθείαν, σαν να ήταν μια γλώσσα προγραμματισμού. Αυτό είναι παγκόσμια πρωτιά της Στάσσας σας κι είμαι ιδιαίτερα περήφανη γι' αυτό. Υπάρχουν αρκετά προγράμματα για να παίξει κανείς Magic στον υπολογιστή του, ή στην κονσόλα του, και μερικά απ' αυτά είναι κανονικά εμπορικά προϊόντα με τα όλα τους. Όλα όμως χρησιμοποιούν μια ενδιάμεση σύνταξη που είναι πιο άμεσα κατανοητή από τον υπολογιστή, αντί για την σχεδόν-φυσική γλώσσα των καρτών. Το αποτέλεσμα είναι οτι πρέπει να μεταφράζουν κάθε κάρτα στην ενδιάμεση σύνταξη που χρησιμοποιούν και συχνά χρειάζεται να γράψουν νέο κώδικα, ειδικά για κάποια καινούργια κάρτα που θέλουν να προσθέσουν στη βάση δεδομένων τους.



Η κατανόηση φυσικής γλώσσας είναι από τα βασικά μου ενδιαφέροντα, γι' αυτό προτίμησα να γράψω ένα πρόγραμμα γραμματικής ανάλυσης και ερμηνείας ("parser/ interpeter"). Ο σκοπός μου ήταν κατ' αρχήν να εξοικονομήσω χρόνο, γιατί αλλοιώτικα θα έπρεπε να επινοήσω μια δική μου ενδιάμεση σύνταξη και να μεταφράσω το κείμενο των καρτών που ήθελα να χρησιμοποιήσω, σ' αυτήν την ενδιάμεση σύνταξη ωστε να το καταλάβει ο μηχανισμός κανόνων (rules engine) του προγράμματός μου. Στην πορεία συνειδητοποίησα κάτι που μ' έκανε να αλλάξω ελαφρώς το θέμα της πτυχιακής μου, από ένα απλό παίχτη τεχνητής νοημοσύνης, που ήταν στην αρχή σ' αυτό που είναι τώρα, ένα πλήρες έμπειρο σύστημα. Αυτό το καινούργιο δεδομένο είναι οτι χάρη στο πρόγραμμα γραμματικής ανάλυσης το πρόγραμμά μου όχι μόνο καταλαβαίνει το κείμενο από τις κάρτες που έχω προσθέσει στη βάση δεδομένων του- καταλαβαίνει επίσης το κείμενο από κάρτες που δεν έχει ξαναδεί.



Μ' αυτό δεν εννοώ οτι το προγραμματάκι μου απέκτησε ξαφνικά αυτοσυνείδηση! Εννοώ οτι η κατανόηση του κειμένου στηρίζεται σε ένα σύνολο γραμματικών κανόνων, που είναι αρκετά γενικοί ωστε να καλύπτουν μεγάλο αριθμό συνδυασμών τους (κι η γλώσσα στις κάρτες υπακούει, γενικά, σ' αυτούς τους κανόνες). Αυτό βέβαια συμβαίνει με κάθε είδους γραμματικούς κανόνες- δεν είναι κάτι καινούργιο. Αυτό σημαίνει "γραμματικοί κανόνες"! Για να είμαι ειλικρινής απλά δεν περίμενα να το πετύχω τόσο γρήγορα και εύκολα αλλά ας όψεται η επιλογή μου της γλώσσας προγραμματισμού που χρησιμοποιώ: 49 κατασκευαστές γραμματικών αναλυτών συνιστούν... Prolog! Σ' αυτή τη γλώσσα είναι τόσο απλό να γράψεις γραμματικούς αναλυτές που σχεδόν ντρέπομαι να το λέω.

Ο γραμματικός αναλυτής μπορεί επίσης να επαληθεύσει την σύνταξη μιας φράσης στην γλώσσα των καρτών, να αναγνωρίσει δηλαδή κατά πόσο αυτή η φράση "στέκει" γραμματικά (αλλά και σε σχέση με τα συμφραζόμενα ενός παιχνιδιού σε εξέλιξη). Τέλος, μπορεί να παράγει φράσεις στη γλώσσα του παιχνιδιού- απ' αυτήν την άποψη θα μπορούσε να χρησιμέψει στους δημιουργούς του παιχνιδιού ως εργαλείο για να σχεδιάσουν γρήγορα καινούργιες κάρτες.



Το υπόλοιπο πρόγραμμα κάνει αρκετά συνηθισμένα πράγματα. Κατ' αρχήν, έχει έναν μηχανισμό κανόνων που εφαρμόζει κατά γράμμα τους κανόνες του παιχνιδιού, στην αυστηρή εκδοχή τους που χρησιμοποιείται σε επαγγελματικά παιχνίδια (το Magic παίζεται επαγγελματικά με βραβεία δεκάδων χιλιάδων δολλαρίων). Έχει επίσης έναν παίχτη τεχνητής νοημοσύνης, ένα AI, που παίζει Magic ενάντια στον χρήστη.

Προς το παρόν, αυτό το AI είναι αρκετά ναΐφ, επειδή είναι ακόμη σε αρχικό στάδιο. Ξεφεύγει λίγο από τα συνηθισμένα από την άποψη οτι δεν χρησιμοποιεί μόνο μαθηματική/ στατιστική ανάλυση για να πάρει αποφάσεις και να κάνει την κίνησή του, αλλά κι ένα σύστημα κανόνων, διατυπωμένων με συμβολικό τρόπο. Αυτή είναι η "εμπειρία" που είναι κωδικοποιημένη στο σύστημα. Γενικά, η πολυπλοκότητα των υπολογισμών που χρειάζονται για ένα γύρο Magic μπορεί να ξεπεράσει κατά πολύ τις δυνατότητες ενός απλού υπολογιστή, γι' αυτό κι ακόμη δεν υπάρχουν προγράμματα που να παίζουν Magic καλύτερα από ανθρώπινους παίχτες (όπως υπάρχουν πχ για το σκάκι, τη ντάμα, το πόκερ, το μπριτζ, το τάβλι και πολλά άλλα παιχνίδια στρατηγικής). Η γνώμη μου είναι οτι για να λυθεί το πρόβλημα αυτό, χρειάζεται και συμβολική επεξεργασία, αλλά κι αυτή δεν θα είναι ποτέ αρκετή από μόνη της. Το ΑΙ μου συνδυάζει και τα δύο- αλλά όπως είπα προς το παρόν είναι σ' εμβρυακό στάδιο. Δεν βιαζόμαστε όμως- σκοπεύω να συνεχίσω να το δουλεύω για τα επόμενα ένα-δυο χρόνια, απλά όχι με τους τρελλούς ρυθμούς αυτής της χρονιάς (έριξα κάτι ξεγυρισμένα δεκαεξάωρα τη μέρα που το φχαριστήθηκε η ψυχή μου). Προς το παρόν, αυτό που έχω να παραδώσω σ' ένα μήνα είναι "proof of concept" ένα πρώτο μοντέλο- ένα "prototype". Πτυχιακή είναι- δεν είναι διδακτορικό!

Μπορώ να πω όμως οτι είμαι αρκετά ευχαριστημένη με τη δουλειά μου. Ακόμη δεν έχει τελειώσει βέβαια- θέλω ακόμη ένα μήνα. Κι όταν λέω "ένα μήνα" εννοώ ένα μήνα στο ίδιο τρελλό πήξιμο, απλά πλέον έχω φάει το βόδι και δεν πρόκειται να κολλήσω στην ουρά, σιγά. Ωχ, "famous last words"... ! :)

12 σχόλια:

Ο χρήστης Blogger aizen999 είπε...

Καλο ακουγεται το προγραμμα που εφτιαξες..
περα απο αυτο,omfg!!magic the gathering!το επαιζα κι εγω!και η lilianna vess!Θα πηδηχτω απ'το παραθυρο!

Τετάρτη, 30 Μαρτίου 2011 - 12:03:00 π.μ. EEST  
Ο χρήστης Blogger Νάρκισσος είπε...

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

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

3.Αν, δε, σε συνδυασμό με τα άνωθεν, μάθει και για τα δεκάποντα στην Πνύκα, με βλέπω να παίρνω πόδι ως ελαττωματικό είδος.

4. Αυτόγραφα τι ώρες υπογράφεις;

XD

Τετάρτη, 30 Μαρτίου 2011 - 2:29:00 π.μ. EEST  
Ο χρήστης Anonymous Ανώνυμος είπε...

ό,τι πιο βαρετό έχω διαβάσει τα τελευταία 50 χρόνια.

Κρίμας που χασες το χρόνο σου για την τεχνητή νοημοσύνη, ως λογοτέχνις τα πας πολύ καλύτερα.

Σόρυ για το στυφό του ποστ,
αλλά έτσι είναι τα βλογς,
το κοινό είτε σε ραίνει με τριαντάφυλλα
είτε με στραγάλια.

Τετάρτη, 30 Μαρτίου 2011 - 3:14:00 π.μ. EEST  
Ο χρήστης Blogger Αιθεροβάμων είπε...

OMG, geeky mode on! You go girl! Πάω τώρα να μαδήσω τριαντάφυλλα να σε ράνω με ροδοπέταλα. :p

Τετάρτη, 30 Μαρτίου 2011 - 3:40:00 π.μ. EEST  
Ο χρήστης Blogger stassa είπε...

aizen,

Γειά! Α, κι εσύ ομοιοπαθής ε; Εγώ έχω χρόνια να παίξω, ευτυχώς το ξεπέρασα (γιατί είχα ένα μικρό εθισμό).

Η Liliana είναι θεά!

Ναρκίσσα,

όχι καλέ, δες' το αλλοιώς. Εσύ έκανες και κάτι χρήσιμο στη ζωή σου, εγώ κοτζάμ γαϊδάρα και ακόμη παίζω με χαρτάκια. Το μόνο χειρότερο θά 'τανε νά 'χα φτιάξει πρόγραμμα να παίζει πόκεμον. Και να δεις που θα φάω και τα υπόλοιπα δυο χρόνια απ' τη ζωή μου μ' αυτές τις αηδίες. Και γιατί; Επειδή είμαι πολύ χαζή για να μάθω να παίζω καλά μόνη μου και χρειάζεται να γράψω ολόκληρο πρόγραμμα να παίζει για πάρτη μου!

(τί λέει, σ' ανέβασα;)

Αυτόγραφα μόνο από βράδυ για να μη με βλέπουνε οι πιστωτές μου! <_<


Ανώνυμη,

νομίζω εννοείς οτι και σαν λογοτέχνις είμαι για τα μπάζα, απλά αυτό εδώ σου φαίνεται ακόμη πιο χάλι.

Δεν πειράζει ρε. Όταν κατακτήσω τον κόσμο με τα ρομπότ μου θα δεις. ΜΠΟΥΑΧΑΧΑΧΑΧΑ!!!

Τετάρτη, 30 Μαρτίου 2011 - 3:46:00 π.μ. EEST  
Ο χρήστης Blogger stassa είπε...

Αιθ, ρίξε κάνα μύγδαλο ρε συ, μας έχει κόψει η λόρδα... XD

Τετάρτη, 30 Μαρτίου 2011 - 3:47:00 π.μ. EEST  
Ο χρήστης Blogger Αιθεροβάμων είπε...

Μην παρασύρεσαι Στάσσα. Ως γνωστόν ο κόσμος θα κατακτηθεί από αυτόνομα ρομπότ με νευρωνικά δίκτυα. Καλή και η Prolog αλλά ας μην υπερβάλλουμε. :p

Τώρα που το σκέφτομαι, πατατάκια θα σου ρίξω που ναι και πιο ελαφριά (δε λέει να σου ρθει όλο το μύγδαλο στο κεφάλι), επίσης το junk food ως γνωστόν είναι το φαγητό κάθε προγραμματιστικής διάνοιας. :p

Τετάρτη, 30 Μαρτίου 2011 - 5:53:00 μ.μ. EEST  
Ο χρήστης Anonymous Ανώνυμος είπε...

Stassa, αυτή την φορά δεν κρατήθηκα να μένω στο περιθώριο και αποφάσισα να βγώ απο το καβούκι μου και να αποδώσω τους χαιρετισμους μου και τον θαυμασμό μου! Δεν διαβάζω πολύ blogs αλλά στο νησάκι σου (with a special someone) ξεβραζόμαστε συχνά και ας μένουμε σε λίμνη. Τεσπα! σε χαιρέτησα. Το πρόγραμμα πότε θα το δοκιμάσω? Διατίθεμαι εγώ προσωπικά καθώς και το αφοσιωμένο στο magic team μου.

..... Το μωρό®

p.s. i was so touched (ages ago) για το country roads. αλλά τι να κάνω τώρα αποφάσiσα να το πώ. tnx!

Τετάρτη, 30 Μαρτίου 2011 - 8:43:00 μ.μ. EEST  
Ο χρήστης Blogger stassa είπε...

Αιθ, μην ταΐζετε τα ζώα!! Πατατάκια!!! Μόλις καταβρόχθισα μισή σακκούλα curly fries, μιλάμε σου ανοίγει η όρεξη για σκατολοΐδια με το coding γαμώτο! Πόσο δίκιο έχεις!!!

Τετάρτη, 30 Μαρτίου 2011 - 11:43:00 μ.μ. EEST  
Ο χρήστης Blogger stassa είπε...

Ωω! Αγαπητό μωρό™ τιμή μου να κάνω τη γνωριμία σας, έχω ακούσει τόσα! Θα πάρετε ένα νερατζάκι; XD

Το πρόγραμμα θα είναι έτοιμο σε ένα μήνα -τουλάχιστον για την παρουσίαση στους εξεταστές. Θα πάρει λίγο καιρό ακόμη μέχρι να μπορώ να στο δώσω να το τρέξεις στον υπολογιστή σου, γιατί βασικά με το λογισμικό που χρησιμοποιώ για να το αναπτύξω δεν μπορώ να βγάλω .exe αρχείο. Πρέπει να το μεταφέρω σε διαφορετικό περιβάλον προγραμματισμού. Αυτό δεν προφταίνω να το κάνω αυτή τη στιγμή, βάλε εξετάσεις Ιουνίου, διακοπούλες κλπ που θα αναγκαστώ να χαλαρώσω λίγο για να μην πάθω νευρικό κλονισμό, μιλάμε για μετά το καλοκαίρι, μάλλον. Ελπίζω να μη σ' απογοητεύω. Για να είμαι ειλικρινής, στην φάση που είναι (είπαμε, prototype, proof of concept κλπ) δεν νοιώθω άνετα να το δει κανείς. Άσε που αυτή τη στιγμή τρέχει ΟΚ επειδή φοβάται μην το αγριοκοιτάξω, δεν ξέρω τί θα γίνει αν δεν είμαι κι εγώ μπροστά όταν το τρέχεις- πόσο ξέρεις από κουμπιούτερ;

Επίσης- μια επισήμανση. Είπα οτι δεν είναι παιχνίδι; Δεν έχει γραφικά κλπ, καθόλου, τίποτα, το output είναι όλο text-based, είναι εντελώς εργαλείο έρευνας κατασταση. Αν θες πάντως να παίξεις ένα φρι παιχνίδι magic, δοκίμασε αυτό εδώ:

http://forge-card-game.googlecode.com/files/02-19-forge.zip

που έχει χίλιες τόσες κάρτες και ΑΙ αντίπαλο (απλά δεν παίζει και πολύ καλά).

Πάντως, σ' ευχαριστώ πολύ που προσφέρεσαι εθελοντικά, το εκτιμώ ιδιαίτερα. Όπως είπα σκοπεύω να συνεχίσω να το δουλεύω για τα επόμενα ένα-δυο χρόνια και θα χρειαστώ πειραματό... εεε, ηρωϊκούς εθελοντές, να με βοηθήσουνε να το τεστάρω.

O Μιγιαζάκης μαζί σου! Μου είπε ένα πουλάκι (με γαλάζιο φουλάρι) οτι σου άρεσε η αφιέρωση, ένοιωσα πολύ περήφανη :)

Τετάρτη, 30 Μαρτίου 2011 - 11:46:00 μ.μ. EEST  
Ο χρήστης Anonymous Ανώνυμος είπε...

Κοίτα, δεν το σπουδάζω το πράγμα αλλά καταλαβαίνω άνω του μετρίου θέλω να πιστεύω. Νταξ, δεν σκαμπάζω
από προγραμματισμό... έχω μείνει στην gwbasic (1983) και μετά κάτι πασαλείμματα από qubic. Όσο για prolog, δεν την έχω καν ακουστά. Δεν περίμενα γραφικά και τέτοια, άλλωστε από τα μεγαλύτερα κολλήματά μου ήταν το "the wizard's castle" (text based του 81) το έπαιζα στην 6η δημοτικού. αν και τότε υπήρχαν και καλύτερα σε γραφικά αλλά εμένα με τράβαγε κάτι στο text.
το ΑΙ σου θέλω να δω και τι εννοείς με την κωδικοποιημένη εμπειρία ;) Πρέπει να ντραφτάρουμε μια μέρα... αλλά έχω σαν και εσένα πάρει απόσταση τον τελευταίο καιρό...
thnx για το link,

ευελπιστώ να βρεθώ στο testing team.

το μωρό®.

Πέμπτη, 31 Μαρτίου 2011 - 12:29:00 π.μ. EEST  
Ο χρήστης Blogger stassa είπε...

Α, text based παιχνίδια κι εσύ, ε; Να σου γνωρίσω το ADOM:

http://www.adom.de/

Και το Nethack:

http://www.nethack.org/

Και το Angband:

http://rephial.org/

Και το Legend of the Green Dragon:

http://lotgd.net/home.php?

Και το Urban Dead:

http://www.urbandead.com/

ΟΚ, σταματάω εγώ γιατί δε χρειάζεται να το κάνουμε βούκινο οτι I don't have a life...! (I'll get one when I run out of Hit Points :)

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

Για την κωδικοποιημένη εμπειρία που λέω, εννοώ οτι το ΑΙ κάνει metagame, βασικά. Έχει διαφορετικές τακτικές για κάθε deck, και κάθε matchup, που τις συνδυάζει για να καταλήξει σε μια κίνηση. Αν δεν βρει κίνηση έτσι, καταφεύγει σε μια μαθηματική ανάλυση του παιχνιδιού και προσπαθεί να βρει μια καλή κίνηση με βάση αυτήν. Σ' αυτή τη φάση υπολογίζει το card ή tempo advantage που του δίνει κάθε κίνηση, κι αποφασίζει ανάλογα με το τί στόχο έχει το deck που παίζει (πχ, beatdown -> tempo ή control -> card advantage). Αυτά στη θεωρία για την ώρα, στην πράξη ένα deck ξέρει να παίξει προς το παρόν κι αυτό με υποτυπώδεις τακτικές, και το deck είναι ένα άκυρο με creatures χωρίς abilities και burn. Δεν προφταίνω να κάνω τίποτα πιο ψαγμένο μέχρι να το παραδώσω.

Εδώ αν θές το εξηγώ πιο αναλυτικά:

http://www.goblinopera.com/mathemagics/?p=202

Το θέμα είναι οτι η μαθηματική ανάλυση από μόνη της δε φτάνει για να παίξει καλά το ΑΙ, γιατί το Magic ανεβαίνει πολύ σε πολυπλοκότητα από ένα σημείο και μετά και εξαντλεί την υπολογιστική σου δυνατότητα πολύ γρήγορα. Κάποια προγράμματα που χρησιμοποιούνε έτσι, "στατιστική" ΑΙ μόνο, παίζουνε καλά μέχρι ένα σημείο αλλά καταλήγουνε πάντα να κάνουνε και μια-δυο άκυρες κινήσεις (πχ Giant Growth στα δικά σου πλάσματα κλπ). Απ' την άλλη, κι η έμπειρη γνώση έχει το μειονέκτημά της- οτι καλύπτει μόνο συγκεκριμμένες περιπτώσεις (πολλές ή λίγες, δεν έχει σημασία). Οπότε ο σκοπός μου είναι να συνδυάσω και τα δύο, αλλά γι' αυτό θα χρειαστεί πολύ περισσότερο ψάξιμο (και πιο προχωρημένες τεχνικές που προς το παρόν δεν κατέχω, πρέπει ν' ανέβω κάνα-δυο level :)

Φιού, αυτά. Ωχ πρέπει πάλι να κοιμηθώ απόψε...

Πέμπτη, 31 Μαρτίου 2011 - 3:28:00 π.μ. EEST  

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

Εγγραφή σε Σχόλια ανάρτησης [Atom]

Σύνδεσμοι σε αυτήν την ανάρτηση:

Δημιουργία Συνδέσμου

<< Αρχική σελίδα