Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
221 lines (199 sloc) 12.1 KB
''' άσκηση από το http://pythonies.mysch.gr/chapters/nim.pdf
Στο παιχνίδι «Τα Ζυγά Κερδίζουν» οι δύο παίκτες ξεκινούν με μια σειρά
από αντικείμενα. Το αρχικό πλήθος των αντικειμένων πρέπει να είναι
περιττός αριθμός. Κάθε ένας από τους δύο παίκτες αφαιρεί με τη σειρά
του από ένα μέχρι και τέσσερα αντικείμενα, μέχρι ν’ αφαιρεθούν όλα.
Νικητής είναι ο παίκτης που στο τέλος του παιχνιδιού απομένει με άρτιο
(ζυγό) πλήθος αντικειμένων. Να αναπτύξετε ένα πρόγραμμα που θα δια-
βάζει σε κάθε γύρο τον αριθμό των σπίρτων που αφαιρεί ο παίκτης που
έχει σειρά και στο τέλος ανακοινώνει το νικητή.
Στο παιχνίδι «Τα Ζυγά Κερδίζουν» υπάρχουν επίσης ανεπιθύμητες νη-
σίδες, δηλαδή καταστάσεις από τις οποίες ένας παίκτης δεν μπορεί ν’
αποφύγει την ήττα, εφόσον ο αντίπαλός του παίξει σωστά. Αν ένας παί-
κτης δεν βρίσκεται σε ανεπιθύμητη νησίδα τότε μπορεί να οδηγήσει τον
αντίπαλό του σε μία και να κερδίσει. Προσπαθήστε να καταγράψετε τις
πιθανές καταστάσεις του παιχνιδιού όταν απομένουν λίγα σπίρτα (π.χ.
από 1 μέχρι και 6) και ποια είναι η καλύτερη κίνηση σε κάθε μία απ’
αυτές. Το εγχείρημα είναι δυσκολότερο απ’ ότι στο Παιχνίδι της Αφαίρε-
σης γιατί εδώ η καλύτερη κίνηση δεν εξαρτάται μόνο από το πλήθος των
σπίρτων που απομένουν. Πρέπει να λάβετε υπόψη αν ο καθένας από τους
δύο παίκτες έχει συγκεντρώσει άρτιο ή περιττό πλήθος σπίρτων. Τελι-
κός σας σκοπός είναι να τροποποιήσετε το πρόγραμμα της προηγούμενης
άσκησης έτσι ώστε να παίζει με αντίπαλο το χρήστη.
(Δείτε μετά το τέλος του κύριου προγράμματος για μια ανάλυση των θέσεων που κερδίζουν.)
'''
import random
def next(p):
""" Επιστρέφει τον αριθμό του παίκτη
που παίζει μετά τον παίκτη p.
p: αριθμός παίκτη (1 ή 2)
"""
if p == 1:
return 2
else:
return 1
def maxMatches(m):
""" Επιστρέφει το μέγιστο πλήθος σπίρτων
που επιτρέπεται να αφαιρεθούν.
m: πλήθος σπίρτων που απομένουν
"""
# το πολύ 4 σπίρτα
if m > 4:
return 4
else:
return m
def readMatches(p,m):
""" Διαβάζει από το χρήστη κι επιστρέφει
το πλήθος σπίρτων που θα αφαιρεθούν.
Εξασφαλίζει ότι η τιμή είναι έγκυρη.
p: αριθμός παίκτη που παίζει
m: πλήθος σπίρτων που απομένουν
"""
# μέγιστο πλήθος σπίρτων προς αφαίρεση
limit = maxMatches(m)
# ανάγνωση σπίρτων που θα πάρει ο παίκτης
print("Παίκτη", p, "πόσα σπίρτα θέλεις;")
num = int(input())
# έλεγχος και επανάληψη (σε περίπτωση λάθους)
while num < 1 or num > limit:
# μήνυμα λάθους
print("Πάρε από 1 μέχρι και",limit,"σπίρτα.")
# ανάγνωση σπίρτων που θα πάρει ο παίκτης
print("Παίκτη", p, "πόσα σπίρτα θέλεις;")
num = int(input())
# επιστροφή τιμής
return num
def randomMatches(m):
""" Επιλέγει κι επιστρέφει ένα τυχαίο
αλλά έγκυρο πλήθος σπίρτων που θα αφαιρεθούν.
m: πλήθος σπίρτων που απομένουν
"""
return random.randint(1,maxMatches(m))
def computeMatches(op,m):
""" Επιλέγει κι επιστρέφει το βέλτιστο
πλήθος σπίρτων που θα πρέπει να αφαιρεθούν.
Αν δεν υπάρχει, επιστρέφει μια τυχαία τιμή.
οp: πλήθος σπίρτων του αντιπάλου
m: πλήθος σπίρτων που απομένουν
"""
# αν ο αντίπαλος έχει πάρει ζυγό αριθμό σπίρτων
if op%2 == 0:
# θέλουμε να δούμε πόσο απέχουμε από τις θέσεις 1, 7, 13, ...
mod = (m-1)%6
if mod == 0 or mod == 5:
# αν απέχουμε 0 ή 5 είμαστε σε ανεπιθύμητη νησίδα
return randomMatches(m)
else:
# αλλιώς αφαιρούμε τα σπίρτα που χρειάζεται
# για να βρεθεί ο αντίπαλος στις θέσεις 1, 7, 13, ...
return mod
elif m < 5:
# ο αντίπαλος έχει μονό αριθμό σπίρτων και
# απομένουν λιγότερα από 5 σπίρτα: τα παίρνουμε όλα και κερδίζουμε
return m
else:
# θέλουμε να δούμε πόσο απέχουμε από τις θέσεις 5, 11, 17, ...
mod = (m-5)%6
if mod == 0:
# αν απέχουμε 0 είμαστε σε ανεπιθύμητη νησίδα
return randomMatches(m)
elif mod < 5:
# αλλιώς αφαιρούμε τα σπίρτα που χρειάζεται
# για να βρεθεί ο αντίπαλος στις θέσεις 1, 7, 13, ...
return mod
else:
# αλλιώς απέχουμε 5 και αφαιρούμε ακριβώς 4 σπίρτα
# για να βρεθεί ο αντίπαλος στις θέσεις 6, 12, 18, ...
return 4
# αρχικό πλήθος σπίρτων
matches = 27
# εμφάνιση αρχικού πλήθους σπίρτων
print("Αρχικό πλήθος σπίρτων:", matches)
# τα σπίρτα που έχει συγκεντρώσει κάθε παίκτης
mPlayer = 0
mComputer = 0
# επιλογή παίκτη-υπολογιστή
computer = random.randint(1,2)
# ορισμός παίκτη που θα παίξει πρώτος
player = 1
# επανάληψη: συνεχίζεται μέχρι να εξαντληθούν τα σπίρτα
while matches > 0:
# επιλογή κίνησης, ανάλογα με τον παίκτη
if player == computer:
# σπίρτα που θα πάρει ο υπολογιστής
removed = computeMatches(mPlayer,matches)
print("Ο υπολογιστής παίρνει", removed)
# τα σπίρτα του υπολογιστή αυξάνονται
mComputer = mComputer + removed
else:
# ανάγνωση σπίρτων που θα πάρει ο παίκτης
removed = readMatches(player, matches)
# τα σπίρτα του παίκτη αυξάνονται
mPlayer = mPlayer + removed
# μείωση σπίρτων
matches = matches - removed
# εμφάνιση πλήθους σπίρτων που απομένουν
print(20*"-")
print("Σπίρτα που έχεις πάρει:", mPlayer)
print("Ο υπολογιστής έχει πάρει:", mComputer)
print("Σπίρτα που απομένουν:", matches)
print(20*"-")
# εναλλαγή παίκτη
player = next(player)
# εμφάνιση αποτελέσματος παιχνιδιού
if mPlayer % 2 == 0:
print("Κέρδισες!")
print("Πήρες", mPlayer, "σπίρτα.")
else:
print("Κέρδισε ο υπολογιστής.")
print("Πήρε", mComputer, "σπίρτα.")
"""
Στον πίνακα που ακολουθεί απαριθμούνται οι πιθανές καταστάσεις προς το τέλος του παιχνιδιού.
Στην πρώτη στήλη εμφανίζεται το πλήθος των σπίρτων που απομένουν, τα σπίρτα που έχει
ο παίκτης που έχει σειρά να παίξει (Μονά/Ζυγά) και τα σπίρτα του αντιπάλου του (Μονά/Ζυγά).
Στη συνέχεια, εμφανίζεται η καλύτερη κίνηση που έχει να κάνει ο παίκτης και σε ποια κατάσταση αυτή
οδηγεί τον αντίπαλό του.
Πρώτα απαριθμούμε τις καταστάσεις που προκύπτουν όταν ο αντίπαλος έχει πάρει ζυγό πλήθος σπίρτων:
1 Ζ Ζ ήττα
2 Μ Ζ παίρνει 1 » 1 Z Ζ » νίκη
3 Ζ Ζ παίρνει 2 » 1 Z Ζ » νίκη
4 Μ Ζ παίρνει 3 » 1 Z Ζ » νίκη
5 Ζ Ζ παίρνει 4 » 1 Z Ζ » νίκη
6 Μ Ζ ήττα
7 Ζ Ζ ήττα
8 Μ Ζ παίρνει 1 » 7 Z Ζ » νίκη
9 Ζ Ζ παίρνει 2 » 7 Z Ζ » νίκη
10 Μ Ζ παίρνει 3 » 7 Z Ζ » νίκη
11 Ζ Ζ παίρνει 4 » 7 Z Ζ » νίκη
12 Μ Ζ ήττα
13 Z Z ήττα
...
Οι καταστάσεις επαναλαμβάνονται με περιοδικότητα. Φαίνεται λοιπόν πως όταν ο αντίπαλος έχει ζυγό πλήθος σπίρτων,
ο παίκτης που παίζει:
(i) χάνει αν έχει 1, 6, 7, 12, 13... σπίρτα και
(ii) κερδίζει αν πάρει τόσα σπίρτα ώστε να απομένουν 1, 7, 13,... σπίρτα όταν έχει σειρά να παίξει ο αντίπαλος.
Στη συνέχεια, απαριθμούμε τις καταστάσεις που προκύπτουν όταν ο αντίπαλος έχει πάρει μονό πλήθος σπίρτων:
1 Μ Μ παίρνει 1 » 0 M Ζ » νίκη
2 Ζ Μ παίρνει 2 » 0 M Ζ » νίκη
3 Μ Μ παίρνει 3 » 0 M Ζ » νίκη
4 Ζ Μ παίρνει 4 » 0 M Ζ » νίκη
5 Μ Μ ήττα
6 Ζ Μ παίρνει 1 » 5 M Μ » νίκη
7 Μ Μ παίρνει 2 » 5 M Μ » νίκη
8 Ζ Μ παίρνει 3 » 5 M Μ » νίκη
9 Μ Μ παίρνει 4 » 5 M Μ » νίκη
10 Ζ Μ παίρνει 4 » 6 M Z » νίκη
11 Μ Μ ήττα
12 Ζ Μ παίρνει 1 » 11 M M » νίκη
13 M M παίρνει 2 » 11 M M » νίκη
14 Z M παίρνει 3 » 11 M M » νίκη
15 M M παίρνει 4 » 11 M M » νίκη
16 Z M παίρνει 4 » 12 M Z » νίκη
17 M M ήττα
Οι καταστάσεις επαναλαμβάνονται με περιοδικότητα. Φαίνεται λοιπόν πως όταν ο αντίπαλος έχει μονό πλήθος σπίρτων,
ο παίκτης που παίζει:
(i) χάνει αν έχει 5, 11, 17,... σπίρτα και
(ii) κερδίζει αν πάρει τόσα σπίρτα ώστε να απομένουν 5, 11, 17,... σπίρτα όταν έχει σειρά να παίξει ο αντίπαλος.
(iii) κερδίζει αν πάρει 4 σπίρτα ώστε να απομένουν 6, 12, 18, ... σπίρτα όταν έχει σειρά να παίξει ο αντίπαλος.
Αυτή είναι η στρατηγική που υλοποιεί η συνάρτηση computeMatches.
"""