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

Α22.17 · Νέα Μηχανή Go (goteam)

Εργασία 3 (2025-26), Άσκηση 1 · Δυσκολία ★★★ · programming · Κεφάλαια: 22, 23, 26

Η τρίτη και τελευταία εργασία είναι προαιρετικά ομαδική, με ομάδες μέχρι 2 άτομα. Αν δουλέψετε ως ομάδα, ένας/μία από εσάς αποδέχεται την πρόσκληση και δημιουργεί την ομάδα με συγκεκριμένο όνομα και ο/η συνεργάτης επιλέγει να προστεθεί σε αυτήν (προσοχή: μην επιλέξετε λάθος ομάδα)· το repository είναι κοινό, οπότε προσοχή στα conflicts! Κάθε repository πρέπει να έχει ένα αρχείο AUTHORS με μία γραμμή για κάθε άτομο, με πρώτο το sdi σας, μετά το github username και τέλος το όνομά σας:

$ cat AUTHORS
sdi2500998,mourmourakis-2007,ΘΑΝΟΣ ΜΟΥΡΜΟΥΡΑΚΗΣ
sdi2500999,lavrakis-2007,ΤΑΚΗΣ ΛΑΒΡΑΚΗΣ

Υποβολές χωρίς σωστό AUTHORS αρχείο δεν θα εξεταστούν. Αυτό ισχύει και για ατομικές υποβολές.

Τα περισσότερα παιχνίδια ξεκινούν από μια αρχική κατάσταση και οι παίκτες εναλλάσσονται επιλέγοντας κινήσεις μέχρι κάποιο κριτήριο να δείξει νίκη, ισοπαλία ή ήττα· ο χώρος καταστάσεων μοιάζει με ένα \(m\)-αδικό δέντρο βάθους \(n\) με περίπου \(m^n\) καταστάσεις. Η τρίλιζα λύνεται εξαντλητικά σε κλάσματα δευτερολέπτου και η ντάμα λύθηκε το 2007, όμως το Go, σε ταμπλό 19x19 με περίπου \(10^{170}\) θέσεις, θεωρούνταν άφταστο για την τεχνητή νοημοσύνη μέχρι που ο AlphaGo της DeepMind κέρδισε 4–1 τον Lee Sedol το 2016. Σε αυτήν την άσκηση καλείστε να υλοποιήσετε τον πυρήνα μιας μηχανής Go ικανό να παίζει με αντίπαλο είτε έναν άνθρωπο, τον χρήστη του προγράμματος, είτε ένα άλλο πρόγραμμα, μέσω ενός ελεγκτή/διαιτητή. Μπορείτε να βρείτε στο διαδίκτυο πολλές πληροφορίες για το πως δομούνται μηχανές Go.

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

• Repository Name: progintro/hw3-<YourTeamName>
• README Filepath: README.md
• Όλα τα αρχεία κώδικα (.c και .h) που θα υλοποιήσετε πρέπει να τοποθετηθούν μέσα σε έναν φάκελο src.

• Το project C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με την εντολή make σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr).

  Στο repository της άσκησης σας δίνεται μια πιθανή οργάνωση κώδικα μαζί με ένα Makefile το οποίο μπορείτε να συμπληρώσετε όπως θέλετε. Μπορείτε να αλλάξετε τα πάντα στο project σας, αλλά θέλουμε να επιβεβαιώσετε πως η εντολή make συνεχίζει να δουλεύει και να παράγει εκτελέσιμα για την Go μηχανή σας. Το εκτελέσιμό σας πρέπει να λέγεται “goteam”—άλλα ονόματα δεν θα γίνουν δεκτά. Ακολουθήστε τις συμβάσεις που δίνονται στο αρχικό Makefile.

• Το πρόγραμμά σας πρέπει να υποστηρίζει τις εντολές του πρωτοκόλλου Go Text Protocol (GTP) προκειμένου να επικοινωνεί με τον χρήστη ή το πρόγραμμα διαιτητή. Δείτε τις ενδεικτικές εκτελέσεις στην συνέχεια για τις βασικές δυνατότητες που πρέπει να υποστηρίζει.
• Υπάρχουν διαφορετικές εκδοχές κανόνων για το Go, στα πλαίσια της άσκησης θα ακολουθήσουμε την πιο δημοφιλή εκδοχή, δηλαδή τους κινέζικους κανόνες.

• Προκειμένου να συμμετέχετε στον διαγωνισμό Go που θα γίνει στο τέλος του εξαμήνου, οι εντολές του πρωτοκόλλου GTP που θα υλοποιήσετε πρέπει να είναι επαρκείς για να είναι σε θέση το πρόγραμμά σας να συνεργάζεται με τους ελεγκτές/διαιτητές που θα βρείτε στην διεύθυνση https://github.com/progintro/goref. Προκειμένου να κατεβάσετε την τελευταία έκδοση του goref τοπικά (προσοχή: θα υπάρξουν αρκετές ανανεώσεις του goref μέχρι το τέλος του διαγωνισμού προκειμένου να διαχειριστούμε την όποια … εφευρετικότητα έχουν οι λύσεις σας), μπορείτε να τρέξετε τις ακόλουθες εντολές:

  curl -O https://raw.githubusercontent.com/progintro/goref/main/goref.py
  chmod +x goref.py
  

Μία ενδεικτική εκτέλεση του προγράμματος (έστω ότι το εκτελέσιμο ονομάζεται goteam) είναι η εξής:

$ ./goteam
boardsize 5
=

komi 0.5
=

clear_board
=

showboard
=
   A B C D E
 5 . . . . . 5
 4 . . . . . 4
 3 . . . . . 3
 2 . . . . . 2
 1 . . . . . 1
   A B C D E

genmove black
= C3

showboard
=
   A B C D E
 5 . . . . . 5
 4 . . . . . 4
 3 . . X . . 3
 2 . . . . . 2
 1 . . . . . 1
   A B C D E

play white C4
=

genmove black
= B4

showboard
=
   A B C D E
 5 . . . . . 5
 4 . X O . . 4
 3 . . X . . 3
 2 . . . . . 2
 1 . . . . . 1
   A B C D E

play white B3
=

genmove black
= B2

showboard
=
   A B C D E
 5 . . . . . 5
 4 . X O . . 4
 3 . O X . . 3
 2 . X . . . 2
 1 . . . . . 1
   A B C D E

play white D3
=

genmove black
= A3

showboard
=
   A B C D E
 5 . . . . . 5
 4 . X O . . 4
 3 X . X O . 3
 2 . X . . . 2
 1 . . . . . 1
   A B C D E

play white D5
=

genmove black
= E4

showboard
=
   A B C D E
 5 . . . O . 5
 4 . X O . X 4
 3 X . X O . 3
 2 . X . . . 2
 1 . . . . . 1
   A B C D E

play white C2
=

genmove black
= B3

showboard
=
   A B C D E
 5 . . . O . 5
 4 . X O . X 4
 3 X X X O . 3
 2 . X O . . 2
 1 . . . . . 1
   A B C D E

play white D1
=

genmove black
= D4

showboard
=
   A B C D E
 5 . . . O . 5
 4 . X O X X 4
 3 X X X O . 3
 2 . X O . . 2
 1 . . . O . 1
   A B C D E

play white E3
=

genmove black
= C5

showboard
=
   A B C D E
 5 . . X O . 5
 4 . X . X X 4
 3 X X X O O 3
 2 . X O . . 2
 1 . . . O . 1
   A B C D E

play white E2
=

genmove black
= B1

showboard
=
   A B C D E
 5 . . X O . 5
 4 . X . X X 4
 3 X X X O O 3
 2 . X O . O 2
 1 . X . O . 1
   A B C D E

play white C1
=

genmove black
= PASS

showboard
=
   A B C D E
 5 . . X O . 5
 4 . X . X X 4
 3 X X X O O 3
 2 . X O . O 2
 1 . X O O . 1
   A B C D E

play white pass
=

final_score
= B+8.5

quit
=

$

Κύπελλο Go (BONUS βαθμολογία). Οι μηχανές που θα υποβληθούν θα συμμετάσχουν σε κύπελλο Go που θα διεξαχθεί μετά το τέλος της προθεσμίας. Για τις τρεις καλύτερες υλοποιήσεις, θα υπάρξει επιβράβευση στη βαθμολογία τους κατά 100%, 70% και 40%, κατά σειρά. Μπορείτε να δοκιμάσετε τις δυνατότητες της υλοποίησής σας χρησιμοποιώντας προγράμματα διαιτητές όπως το goref παραπάνω ως εξής:

$ ./goref.py --black "gnugo --mode gtp --chinese-rules" \
    --white "./goteam" --games 10 --main-time 60 --verbose
[blackcmd:B >>] name
[blackcmd:B <<] = GNU Go
[blackcmd:B <<]
...
[whitecmd:W >>] name
[whitecmd:W <<] = Go Team
[whitecmd:W <<]
[whitecmd:W(Go Team) >>] version
[whitecmd:W(Go Team) <<] = 1.0
[whitecmd:W(Go Team) <<]
...
[whitecmd:W(Go Team) v1.0 >>] time_settings 60 0 0
[whitecmd:W(Go Team) v1.0 <<] =
[whitecmd:W(Go Team) v1.0 <<]
...
[whitecmd:W(Go Team) v1.0 >>] time_left B 60 0
[whitecmd:W(Go Team) v1.0 <<] =
[whitecmd:W(Go Team) v1.0 <<]
[blackcmd:B(GNU Go) v3.8 >>] genmove B
[blackcmd:B(GNU Go) v3.8 <<] = Q16
[blackcmd:B(GNU Go) v3.8 <<]
[whitecmd:W(Go Team) v1.0 >>] play B Q16
[whitecmd:W(Go Team) v1.0 <<] =
[whitecmd:W(Go Team) v1.0 <<]
...
[whitecmd:W(Go Team) v1.0 >>] time_left W 60 0
[whitecmd:W(Go Team) v1.0 <<] =
[whitecmd:W(Go Team) v1.0 <<]
...
[whitecmd:W(Go Team) v1.0 >>] genmove W
[whitecmd:W(Go Team) v1.0 <<] = D4
[whitecmd:W(Go Team) v1.0 <<]
...
Games: 10
Overall (by command slot):
  black_cmd: 8
  white_cmd: 2
  draws: 0
...

Η παραπάνω εκτέλεση ελέγχει την υλοποίησή μας με λευκά ενάντια στην μηχανή GNU Go με μαύρα (apt install gnugo σε σύστημα Ubuntu) και μας επιτρέπει να ελέγξουμε την πληρότητα αλλά και την αποδοτικότητα της υλοποίησής μας. Αν θέλετε να οπτικοποιήσετε τα αποτελέσματα της μηχανής σας (ή να παίξετε ένα παιχνίδι με graphical user interface) υπάρχουν αρκετές υλοποιήσεις ανοιχτού κώδικα που μπορείτε να χρησιμοποιήσετε, π.χ. το gogui.

Επίλογος

Πριν την υποβολή της εργασίας, μην ξεχάσετε το README.md, μέσα στο οποίο πρέπει να συμπεριλάβετε τις όποιες παρατηρήσεις σας κατά την διεκπεραίωση της άσκησης! Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της βαθμολόγησης.

Υπόδειξη

Χώρισε το project σε επίπεδα: ανάγνωση και απάντηση εντολών GTP (γραμμή-γραμμή από το stdin, απάντηση = ή ? και κενή γραμμή), αναπαράσταση ταμπλό, κανόνες, και τέλος επιλογή κίνησης. Ο πυρήνας των κανόνων είναι η εύρεση μιας ομάδας συνδεδεμένων πετρών και των ελευθεριών της με BFS/DFS σε πλέγμα· με αυτήν υλοποιείς αιχμαλωσίες, απαγόρευση αυτοκτονίας, ko και την καταμέτρηση περιοχής των κινέζικων κανόνων. Ξεκίνα με μια μηχανή που παίζει απλώς νόμιμες κινήσεις (και ξέρει να κάνει pass) και βελτίωσέ την μετά, π.χ. με προσομοιώσεις τυχαίων παρτίδων, προσέχοντας τον χρόνο που δίνει το time_left.

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