Μέθοδος Μόντε Κάρλο

Η μέθοδος Μόντε Κάρλο (αγγλικά: Monte Carlo method), ή πείραμα/προσoμοίωση Μόντε Κάρλο, είναι μια στοχαστική διαδικασία όπου με χρήση τυχαίων αριθμών και τη στατιστική προσπαθούμε να λύσουμε ένα πρόβλημα. Σε ένα πείραμα Μόντε Κάρλο χρησιμοποιείται προσομοίωση με μια γεννήτρια τυχαίων αριθμών. Το όνομα Μόντε Κάρλο προέρχεται από την ομώνυμη πόλη του Μονακό όπου εκεί υπάρχει ένα διάσημο καζίνο. Η μέθοδος Μόντε Κάρλο παρουσιάστηκε το 1949 με την δημοσίευση των Νίκολας Μετρόπολις και Στάνισλαβ Ούλαμ «Η μέθοδος Μόντε Κάρλο» στο περιοδικό Journal of the American Statistical Association.^[1] Η ιδέα αυτή ήταν γνωστή και νωρίτερα όπου κάποια προβλήματα στατιστικής λυνόντουσαν με τυχαία δειγματοληψία.^[2][3]

Ένα παράδειγμα πειράματος Μόντε Κάρλο είναι το πρόβλημα του μεθυσμένου ναύτη. Στο πρόβλημα αυτό έχουμε ένα ναύτη μεθυσμένο σε μια πόλη όπου θέλει να βρει την έξοδο. Σε κάθε σταυροδρόμι έχει ίση πιθανότητα να επιλέξει ένα από τους 4 δρόμους. Θέλουμε να βρούμε την πιθανότητα που έχει ο ναύτης να εξέλθει σε κάθε μια από τις εξόδους της πόλης. Αν έχουμε λίγα οικοδομικά τετράγωνα (π.χ. 3x2 οικοδομικά τετράγωνα) η πιθανότητα μπορεί να υπολογιστεί εύκολα με μαθηματικούς υπολογισμούς. Στην περίπτωση μια πόλης το πρόβλημα γίνεται πολύ δύσκολο να λυθεί με μαθηματικές πράξεις αλλά λύνεται με ένα πείραμα Μόντε Κάρλο και τη χρήση ενός ηλεκτρονικού υπολογιστή. Χρησιμοποιώντας μια μηχανή τυχαίων αριθμών σε ένα υπολογιστή προσομοιώνουμε την κίνηση του ναύτη μέχρι να εξέλθει από την πόλη. Το πείραμα το τρέχουμε πάρα πολλές φορές και στο τέλος υπολογίζουμε (κατά προσέγγιση) την κάθε πιθανότητα να βγει από κάθε έξοδο της πόλης.^[4]

Τα πειράματα Monte Carlo χρησιμοποιούνται για ανάλυση παιχνιδιών όπως το σκάκι ή το Γκο (ασιατικό παιχνίδι στρατηγικής όπως το σκάκι). Χρησιμοποιούμε γεννήτριες τυχαίων αριθμών και βάζουμε δύο εικονικούς παίχτες (υπολογιστές) να παίζουν στην "τύχη". Επαναλαμβάνοντας το πείραμα Μόντε Κάρλο πάρα πολλές φορές είμαστε σε θέση να εκτιμήσουμε ποια επόμενη κίνηση είναι στατιστικά καλή για να κερδίσει το παιχνίδι ένα παίκτης.^[5][6][7]

Εξωτερικοί σύνδεσμοι

• Eric Grimson· John Guttag. «Lecture 20: Monte Carlo Simulations, Estimating pi». Introduction to Computer Science and Programming stimating pi. MIT Open Courseware. Ανακτήθηκε στις 4 Φεβρουαρίου 2015.

Παραπομπές

1. Metropolis, Nicholas; Ulam, S. (1949). «The Monte Carlo Method». Journal of the American Statistical Association 44 (247): 335–341. doi:10.1080/01621459.1949.10483310. PMID 18139350. https://archive.org/details/sim_journal-of-the-american-statistical-association_1949-09_44_247/page/335.
2. Καλαμαράς, ∆ημήτρης (2001–2002). Αριθμητική Ανάλυση (PDF). σελ. 2.
3. Eckhardt, Roger (1987). «Stan Ulam, John von Neumann, and the Monte Carlo method». Los Alamos Science, Special Issue (15): 131–137. Αρχειοθετήθηκε από το πρωτότυπο στις 2014-09-09. https://web.archive.org/web/20140909230946/http://library.lanl.gov/cgi-bin/getfile?15-13.pdf. Ανακτήθηκε στις 2015-01-28.
4. Ευσταθίου, Κωνσταντίνο. «Πειράματα Monte Carlo: Ο τυχαίος περίπατος του "μεθυσμένου ναύτη"». Χημικό Πανεπιστήμιου Αθηνών. Αρχειοθετήθηκε από το πρωτότυπο στις 14 Απριλίου 2015. Ανακτήθηκε στις 28 Ιανουαρίου 2015.
5. Keim, Brandon (3 Οκτωβρίου 2009). «Humans No Match for Go Bot Overlords». Wired. http://www.wired.com/2009/03/gobrain/. Ανακτήθηκε στις 28 Ιανουαρίου 2015.
6. Σχεδίαση επιλογής κινήσεων με αναγνώριση προτύπων για παίκτη Go βασισμένο σε αναδιατασσόμενη λογική. Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών Ηρακλείου Κρήτης. 2014.
7. Susan Polgar· Douglas Goldstein (2014). Rich As A King: How the Wisdom of Chess Can Make You a Grandmaster of Investing. Morgan James Publishing. σελ. 65. ISBN 978-1-63047-099-9.