Νέα Μηχανή Σκακιού (chess engine - 100 Μονάδες)
Η εργασία είναι προαιρετικά ομαδική με ομάδες μέχρι 2 άτομα. Για να είναι ξεκάθαρο ποια άτομα συνεργάστηκαν, κάθε repository πρέπει να έχει ένα AUTHORS αρχείο με μία γραμμή για κάθε άτομο, με πρώτο το sdi σας, μετά το github username και τέλος το όνομά σας:
$ cat AUTHORS
sdi2400998,mourmourakis-2006,ΘΑΝΟΣ ΜΟΥΡΜΟΥΡΑΚΗΣ
sdi2400999,xifias-2006,ΚΩΣΤΑΣ ΞΙΦΙΑΣ
Υποβολές χωρίς σωστό AUTHORS αρχείο δεν θα εξεταστούν. Αυτό ισχύει και για ατομικές υποβολές.
Τα περισσότερα παιχνίδια έχουν παρεμφερή δομή: (1) το παιχνίδι ξεκινάει σε μια αρχική κατάσταση, (2) ένας από τους παίκτες παίζει πρώτος επιλέγοντας μια από τις δυνατές κινήσεις που έχει στην διάθεσή του αλλάζοντας την κατάσταση του παιχνιδιού και (3) στην συνέχεια δίνει την σειρά του στον επόμενο παίκτη. Ο χώρος καταστάσεων ενός παιχνιδιού μπορεί να φανταστεί σαν ένα m-αδικό δέντρο βάθους n (m οι επιλογές σε κάθε θέση, n οι γύροι), με περίπου \(m^n\) καταστάσεις. Η τρίλιζα και η ντάμα έχουν “λυθεί” (διατρέξαμε όλον τον χώρο καταστάσεών τους), αλλά το σκάκι όχι: ο Claude Shannon εκτίμησε τις δυνατές παρτίδες στο \(10^{120}\) και τις θέσεις της σκακιέρας στο \(10^{40}\). Οι μηχανές σκακιού εξερευνούν αυτόν τον χώρο με τεχνικές αναζήτησης / ευριστικές (minimax, negamax) και με ιδιαίτερα αποδοτικές υλοποιήσεις, συνήθως σε C και C++.
Πόσο εύκολο είναι να φτιάξουμε μια μηχανή σκακιού σήμερα; Μπορεί να κερδίσει σχετικά απλούς αντιπάλους που απλά παίζουν τυχαίες κινήσεις; Αυτό θα είναι και το αντικείμενο αυτής της άσκησης, όπου καλείστε να υλοποιήσετε τον πυρήνα μιας μηχανής σκακιού. Ευτυχώς, δεν χρειάζεται να ξεκινήσετε από το μηδέν, μπορείτε να βρείτε στο διαδίκτυο πολλές πληροφορίες για το πως δομούνται σκακιστικές μηχανές καθώς και ποιες βελτιστοποιήσεις είναι δημοφιλείς (Chess Programming Wiki).
src.Το αρχείο C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη
και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας
πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με την ακόλουθη εντολή σε ένα από τα
μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr): make
Στο repository της άσκησης σας δίνεται μια πιθανή οργάνωση κώδικα μαζί με ένα
Makefile. Μπορείτε να αλλάξετε τα πάντα στο project σας, αλλά θέλουμε να
επιβεβαιώσετε πως η εντολή make συνεχίζει να δουλεύει και να παράγει εκτελέσιμα από
την μηχανή σκακιού σας.
int choose_move(char * fen, char * moves, int timeout)
η οποία θα δέχεται ορίσματα με σημασιολογία όμοια με παραπάνω και θα επιστρέφει
το index της κίνησης που επιλέγει. Όταν γίνεται compile σε Web Assembly, το
πρόγραμμά σας θα πρέπει να αποφεύγει να τυπώνει στο stdout/stderr καθώς αυτά δεν
είναι επιτρεπτά σε αυτό το περιβάλλον.Παρακάτω παραθέτουμε την αλληλεπίδραση με μια ενδεικτική λύση:
$ make TARGET=engine
$ ./engine "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" \
"a3 a4 b3 b4 c3 c4 d3 d4 e3 e4 f3 f4 g3 g4 h3 h4 Na3 Nc3 Nf3 Nh3" \
3
9
Παρατηρούμε ότι δώσαμε στο πρόγραμμά μας (το οποίο ονομάσαμε engine) 3 ορίσματα: (1) την αρχική μας σκακιέρα σε FEN format, (2) τις κινήσεις που μπορεί να παίξει χωρισμένες με κενό (20 στον αριθμό) και (3) 3 δευτερόλεπτα για να αποφασίσει ποια κίνηση επιθυμεί να παίξει. Το πρόγραμμά μας αποφάσισε να παίξει την κίνηση στην θέση 9 (προσοχή οι κινήσεις ξεκινάνε από το 0) και επομένως επέλεξε την κίνηση e4 (να κινήσει επομένως το λευκό πιόνι κατά δύο τετράγωνα μπροστά). Αυτό ήταν! Αν το πρόγραμμά σας υποστηρίζει την παραπάνω δυνατότητα (να τυπώνει τον σωστό ακέραιο), είναι σε θέση να χρησιμοποιηθεί ως μηχανή σκακιού. Το πόσο καλά θα τα πάει εξαρτάται από τις επιλογές που θα κάνει.
Στο αρχείο README.md πρέπει να προσθέσετε την περιγραφή του project σας καθώς και ποιες πηγές χρησιμοποιήσατε κατά την υλοποίηση. Περιμένουμε να δούμε write ups υψηλής ποιότητας, καθώς αυτό είναι ένα project που θα μπορούσατε να δημοσιεύσετε μετά το πέρας της άσκησης και να το βάλετε στο portfolio σας. Σκακιστικές μηχανές που επιτυγχάνουν υψηλότερες επιδόσεις, θα πάρουν bonus μονάδες με μετρική που θα ανακοινωθεί στην συνέχεια, (πιθανώς να χρησιμοποιήσουμε την μετρική ELO).
Χωρίστε το project σε ενότητες (αναπαράσταση σκακιέρας από FEN, παραγωγή και εκτέλεση
κινήσεων, αξιολόγηση θέσης, αναζήτηση) με δικό του .c/.h η καθεμία. Ακόμη και μια
απλή αξιολόγηση με το υλικό (άθροισμα αξιών κομματιών) μαζί με minimax/negamax λίγων
κινήσεων βάθους αρκεί για να κερδίζει μια τυχαία μηχανή· το alpha-beta pruning και η
επαναληπτική εκβάθυνση (iterative deepening) σας επιτρέπουν να σέβεστε το timeout.
Προσοχή: οι δοσμένες κινήσεις είναι σε SAN, οπότε πρέπει να τις αντιστοιχίσετε στις
δικές σας, και η choose_move δεν πρέπει να τυπώνει τίποτα.
Αριθμός στον οδηγό: Α22.16
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: hw-2024-hw3-chess ·
Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2024-hw3-chess.html ·
Markdown (GitHub)