Εφαρμογές της συνάρτησης Grundy στη θεωρία παιγνίων

Abstract

Η παρούσα διπλωματική εργασία ασχολείται με την εφαρμογή της συνάρτησης Grundy στην θεωρία παιγνίων. Στο πρώτο κεφάλαιο παρουσιάζονται βασικές έννοιες του θέματος. Εν συνεχεία, στο δεύτερο κεφάλαιο παρουσιάζεται η συνάρτηση Grundy - Sprague ενός γραφήματος καθώς και ο τρόπος υπολογισμού της. Στο τρίτο κεφάλαιο παρουσιάζονται τα παίγνια καταστάσεων και γίνεται συγκεκριμένη επεξήγηση του Nim. Στη συνέχεια γίνεται εφαρμογή της συνάρτησης Grundy στα παίγνια καταστάσεων και στο παίγνιο Nim. Στο τέταρτο κεφάλαιο εφαρμόζεται η συνάρτηση Grundy στο παίγνιο του Welter, ενώ στο πέμπτο και στο έκτο κεφάλαιο εφαρμόζεται η εν λόγω συνάρτηση στο παίγνιο του Welter χωρίς προσπέραση και στο παίγνιο του Welter με 3 πιόνια, αντίστοιχα. Όμοια, στο έβδομο κεφάλαιο γίνεται εφαρμογή της συνάρτησης Grundy σε ένα παίγνιο σε πλέγμα. Στο όγδοο κεφάλαιο παρουσιάζεται η δίτιμη συνάρτηση Grundy – Sprague ενός γραφήματος, ενώ στο ένατο κεφάλαιο εξετάζεται το παίγνιο του Welter υπό το πρίσμα της δίτιμης συνάρτησης Grundy.