Section outline

  • Συζητήσαμε

    (1) για το πρόβλημα της αναζήτησης μίας "στατηγικής" σε παίγνια δύο αντιπάλων. Δηλαδή πέρνουμε το μέρος του ενός παίκτη και ζητάμε να βρούμε μία στρατηγική (ακολουθία κινήσεων στο παιχνίδι) που θα τον οδηγήσει στην νίκη. Το πρόβλημα είναι πάρα πολύ δύσκολο! (ανήκει σε γενικές γραμμές στην κλάση P-SPACE-hard!).
    Είδαμε τους αλγόριθμους Minimax και Alpa-Beta.

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

    Υλικό σχετικό με την συζήτηση υπάρχει
    στο [1] στα κεφάλαια 5 και 6,
    στο [2] στα κεφάλαια 5 και 6

    Παρακίνηση & συντονισμός συζήτησης: Μάντης Ανδρέας