Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α9.15 · Συνεργασία (Prisoner's Dilemma)

Εργασία 2 (2023-24), Άσκηση 3 · Δυσκολία ★★☆ · programming · Κεφάλαια: 9, 8

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

Ένας τρόπος να μοντελοποιήσουμε τέτοια παιχνίδια με πολλούς γύρους όπου οι παίκτες συνεργάζονται ή όχι είναι το Prisoner’s Dilemma. Σε κάθε γύρο αυτού του παιχνιδιού, δύο παίκτες Α και Β αποφασίζουν αν θα συνεργαστούν (cooperate) ή όχι (defect). Αν και οι δύο συνεργαστούν τότε αποκομίζουν κάποιους πόντους (έστω Reward (R) = 3). Αν και οι δύο δεν συνεργαστούν τότε παίρνουν λιγότερους πόντους (έστω Payoff (P) = 1). Αν ο ένας (έστω ο Α) αποφασίσει να συνεργαστεί και ο Β τον “προδώσει” χωρίς να συνεργαστεί τότε ο Β θα αποκομίσει περισσότερους πόντους (έστω Temptation (T) = 5) ενώ ο Α δεν θα πάρει καθόλου πόντους (έστω Sucker (S) = 0). Ένας τρόπος να συνοψίσουμε το παραπάνω παιχνίδι πόντων είναι με έναν πίνακα (payoff matrix):

A / B B συνεργάζεται B δεν συνεργάζεται
A συνεργάζεται A: 3, B: 3 A: 0, B: 5
A δεν συνεργάζεται A: 5, B: 0 A: 1, B: 1

Όμως τα περισσότερα παιχνίδια δεν τελειώνουν στον πρώτο γύρο! Για παράδειγμα, αν στον πρώτο γύρο είδε ο Α ότι ο Β δεν συνεργάστηκε, ο Α μπορεί να αποφασίσει ότι δεν θα συνεργαστεί στον δεύτερο γύρο και θα περιμένει να δει πως θα “συμπεριφερθεί” ο Β στον δεύτερο γύρο. Αντίστοιχες αποφάσεις μπορεί να έχει στο μυαλό του και ο Β.

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

Τεχνικές Προδιαγραφές

Ας προσπαθήσουμε να παίξουμε με μια ενδεικτική λύση (όχι η καλύτερη):

$ gcc -Os -Wall -Wextra -Werror -pedantic -o coop coop.c -lm
$ ./coop
C

Παρατηρούμε ότι το πρόγραμμα έπαιξε “C” (Cooperate). Σε απάντηση μπορούμε να απαντήσουμε D και μετά Enter:

$ gcc -Os -Wall -Wextra -Werror -pedantic -o coop coop.c -lm
$ ./coop
C
D
D

Παρατηρούμε ότι αφού γράψαμε “D” (Defect) το πρόγραμμα μας απάντησε με “D” για τον επόμενο γύρο. Έστω ότι απαντάμε D σε αυτόν τον γύρο και εμείς. Σύνολο σε αυτούς τους δύο γύρους επομένως εμείς (που γράφουμε από το stdin) συλλέξαμε 5 + 1 = 6 πόντους ενώ η ενδεικτική μας λύση (coop) μάζεψε 0 + 1 = 1 πόντους.

Έστω ότι θέλουμε να δούμε πως συμπεριφέρεται μια ενδεικτική (όχι η καλύτερη) λύση όταν παίζει με έναν “εκδικητικό” παίκτη που πάντα δεν συνεργάζεται:

$ echo > input; for i in `seq 1 1000`; do echo D >> input; done
$ ./coop < input | head -n -1 > output
$ grep -c D output
42
$ grep -c C output
958

Επομένως παρατηρούμε ότι το πρόγραμμά μας συνεργάστηκε 958 φορές και 42 δεν συνεργάστηκε, επομένως συγκέντρωσε 958 · 0 + 42 = 42 πόντους. Αντίστοιχα μπορούμε να ελέγξουμε πως συμπεριφέρεται με έναν “συνεργατικό” παίκτη:

$ echo > input; for i in `seq 1 1000`; do echo C >> input; done
$ ./coop < input | head -n -1 > output
$ grep -c D output
3
$ grep -c C output
997

Επομένως παρατηρούμε ότι το πρόγραμμά μας συνεργάστηκε 997 φορές και 3 δεν συνεργάστηκε, επομένως συγκέντρωσε 997 · 3 + 3 · 5 = 3006 πόντους. Αν θέλετε να δοκιμάσετε διαφορετικές στρατηγικές και να δείτε πως θα “έπαιζε” με διαφορετικούς παίκτες παραθέτουμε ένα ενδεικτικό (όχι το τελικό!) script “διαιτητή” στο ακόλουθο URL: https://github.com/progintro/data/blob/main/scripts/referee.py που μπορεί να τρέξει διαφορετικές εκδοχές του προγράμματός σας για έναν αριθμό γύρων και να σας δώσει το score του πρώτου παίκτη. Για παράδειγμα:

# Download referee
$ curl -O https://raw.githubusercontent.com/progintro/data/main/scripts/referee.py
# Check what's my score against the `coop` implementation
$ python3 referee.py ./smart_coop ./coop 1000
3016

Στο αρχείο README.md πρέπει να προσθέσετε οποιεσδήποτε παρατηρήσεις σας κατά την διεκπεραίωση της άσκησης. Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της βαθμολόγησης. Για τις υποβολές με την καλύτερη απόδοση (αυτές που θα συγκεντρώσουν τους περισσότερους βαθμούς σε παιχνίδια με όλες τις άλλες υποβολές) θα υπάρχει bonus βαθμολογία: η πρώτη υποβολή θα λάβει +100%, η δεύτερη +70% και η τρίτη +40%.

Υπόδειξη

Η δομή είναι ένας βρόχος «τύπωσε κίνηση, fflush, διάβασε την κίνηση του αντιπάλου με getchar αγνοώντας ό,τι δεν είναι ‘C’ ή ‘D’, μέχρι το EOF». Η στρατηγική μπορεί να κρατά λίγες μεταβλητές κατάστασης (π.χ. την τελευταία κίνηση του αντιπάλου ή μετρητές). Ελέγξτε ότι η στρατηγική σας ικανοποιεί και τους τρεις ελάχιστους όρους (εκδικητικός, συνεργατικός παίκτης, τουλάχιστον ένα C και ένα D ανά 1000 γύρους), και διαβάστε για κλασικές στρατηγικές όπως το tit-for-tat.

Δείτε επίσης

Αριθμός στον οδηγό: Α9.15 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: hw-2023-hw2-coop · Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2023-hw2-coop.html · Markdown (GitHub)