Αποστολέας Θέμα: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ  (Αναγνώστηκε 1150 φορές)

Κωστας τζιαννης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 201
ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« στις: 25 Μάι 2018, 04:38:49 πμ »
Το παιχνιδι νιμ παιζεται με 2 παιχτες χρησιμοποιωντας  σπιρτα ως εξης:υπαρχουν  4 γραμμες και αρχικα στην πρωτη γραμμη εχουμε 1 σπιρτο στη δευτερη 3 στην τριτη 5 και στην τεταρτη 7 σπιρτα. καθε παιχτης οταν ερθει η σειρα του μπορει να αφαιρεσει απο μια γραμμη της επιλογης του απο 1 μεχρι ολα τα σπιρτα αυτης της γραμμης που διαλεξε.απαγορευεται να αφαιρει σπιρτα απο διαφορετικες γραμμες στον ιδιο γυρο ή να επιλεξει γραμμη που δεν εχει τουλαχιστον 1 σπιρτο.ο παιχτης που θα παρει το τελευταιο σπιρτο ειναι ο ΗΤΤΗΜΕΝΟΣ.να φτιαξετε προγραμμα σε γλωσσα που θα προσομειωνει το παιχνιδι αυτο μεταξυ υπολογιστη και παιχτη με τον υπολογιστη να παιζει παντα δευτερος.να κανετε τον υπολογιστη να νικαει παντα

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 917
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #1 στις: 14 Ιούν 2018, 12:50:45 μμ »
Είχα φτιάξει μια λύση την περασμένη βδομάδα ....
Πέρασα πολύ ωραία ψάχνοντάς το, και βρήκα ότι υπάρχουν κάποια "σκαλοπάτια" καταστάσεων, που αν καταφέρεις να πασάρεις στον αντίπαλο αυτές τις καταστάσεις, δεν μπορεί να κερδίσει. πχ, αν του δώσω 3 γραμμές με 1, 2, 3 σπίρτα αντίστοιχα, ότι και να κάνει κερδίζω. Ένα τέτοιο "σκαλοπάτι" είναι και η αρχική κατάσταση, και αφού παίζει εκείνος πρώτος, αν κάνεις τις σωστές κινήσεις θα κερδίσεις.

Η ιδέα στη λύση μου περίπου είναι η εξής :
Φτιάχνω έναν πίνακα Winner. Αυτός αντιστοιχίζει κάθε πιθανή κατάσταση σπίρτων που μπορεί να "πάρω"  με την κατάσταση που πρέπει να "δώσω" για να κερδίσω
Οι καταστάσεις παριστώνται με τετραψήφιους αριθμούς xyzw όπου τα ψηφία αυξάνουν προς τα δεξιά
πχ  αν έχω  1, 3, 1, 5 σπίρτα στην 1η, 2η 3η και 4η σειρά αντίστοιχα, αυτό αντιστοιχεί στην κατάσταση  1135
μιας κι είναι αδιάφορο σε ποιες γραμμές έχω ποια σπίρτα αλλά το ότι έχω 2 γραμμές με 1, μία με 3 και μία με 5
Κάθε κατάσταση αντιστοιχεί σε ένα κελί του Winner στο οποίο περιέχεται η επόμενη κατάσταση που θα με φέρει στη νίκη.
Αν μία κατάσταση δεν μπορεί να με πάει σε νίκη, είναι 'loser' και περιέχει το 0
Φυσικά σπαταλιώνται θέσεις στον Winner αλλά ήταν μια εύκολη λύση, για αρχή, και σε επόμενη φάση θα κοίταζα πώς μπορεί να γίνει πιο αποδοτικά

Φιλικά,
Γιώργος Θαλασσινός

Κωστας τζιαννης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 201
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #2 στις: 14 Ιούν 2018, 07:57:57 μμ »
Είχα φτιάξει μια λύση την περασμένη βδομάδα ....
Πέρασα πολύ ωραία ψάχνοντάς το, και βρήκα ότι υπάρχουν κάποια "σκαλοπάτια" καταστάσεων, που αν καταφέρεις να πασάρεις στον αντίπαλο αυτές τις καταστάσεις, δεν μπορεί να κερδίσει. πχ, αν του δώσω 3 γραμμές με 1, 2, 3 σπίρτα αντίστοιχα, ότι και να κάνει κερδίζω. Ένα τέτοιο "σκαλοπάτι" είναι και η αρχική κατάσταση, και αφού παίζει εκείνος πρώτος, αν κάνεις τις σωστές κινήσεις θα κερδίσεις.

Η ιδέα στη λύση μου περίπου είναι η εξής :
Φτιάχνω έναν πίνακα Winner. Αυτός αντιστοιχίζει κάθε πιθανή κατάσταση σπίρτων που μπορεί να "πάρω"  με την κατάσταση που πρέπει να "δώσω" για να κερδίσω
Οι καταστάσεις παριστώνται με τετραψήφιους αριθμούς xyzw όπου τα ψηφία αυξάνουν προς τα δεξιά
πχ  αν έχω  1, 3, 1, 5 σπίρτα στην 1η, 2η 3η και 4η σειρά αντίστοιχα, αυτό αντιστοιχεί στην κατάσταση  1135
μιας κι είναι αδιάφορο σε ποιες γραμμές έχω ποια σπίρτα αλλά το ότι έχω 2 γραμμές με 1, μία με 3 και μία με 5
Κάθε κατάσταση αντιστοιχεί σε ένα κελί του Winner στο οποίο περιέχεται η επόμενη κατάσταση που θα με φέρει στη νίκη.
Αν μία κατάσταση δεν μπορεί να με πάει σε νίκη, είναι 'loser' και περιέχει το 0
Φυσικά σπαταλιώνται θέσεις στον Winner αλλά ήταν μια εύκολη λύση, για αρχή, και σε επόμενη φάση θα κοίταζα πώς μπορεί να γίνει πιο αποδοτικά

μπραβο ωραιος!!μου αρεσε και η σχεδιαστικη αναπαρασταση με τις παυλες που συμβολιζουν σπιρτα.ουσιαστικα η συντομη λυση ειναι να σπας καθε γραμμη σε 4-2-1 σπιρτα.αυτος που παιζει δευτερος πρεπει να αφαιρει τοσα σπιρτα και απο την καταλληλη γραμμη ωστε να αφηνει στον αλλον ζυγο αριθμο απο 4 ,ζυγο αριθμο απο 2,ζυγο αριθμο 1 συνολικα.οταν υπαρχει μονο μια γραμμη με περισσοτερα απο ενα σπιρτα τοτε παρτα ολα απο αυτη τη γραμμη ωστε να αφησεις το 1,1,1.

https://www.youtube.com/watch?v=niMjxNtiuu8

Κωστας τζιαννης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 201
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #3 στις: 15 Ιούν 2018, 05:43:44 πμ »
η λυση του ΝΙΜ με τις δυναμεις του 2

lalibi

  • Νέος
  • *
  • Μηνύματα: 5
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #4 στις: 17 Απρ 2020, 04:13:06 μμ »
Το έπαιζα αυτό το παιχνίδι στο φροντιστήριο, Γ' Λυκείου, δεν ήξερα ότι είναι γνωστό!

Ορίστε και η δικιά μου εκδοχή.

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3386
  • to Iterate is human to Recurse divine
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #5 στις: 17 Απρ 2020, 04:35:09 μμ »
Στις Pythonies έχει εξαιρετικό υλικό για το παιχνίδι NIM σε Python.

http://pythonies.mysch.gr/chapters/nim.pdf
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 455
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #6 στις: 17 Απρ 2020, 05:18:35 μμ »
Διάβασα λίγο το κώδικα στο pdf παραπάνω. Ο επόμενος παίκτης βγαίνει με ένα τύπο που δηλώνει αμέσως πως αυτός που το έγραψε δεν είχε εμπειρία.
Όταν μας ενδιαφέρει να εναλλάσσονται δύο τιμές πχ η 3 και η 5 τότε αρκεί ο τύπος 8-Χ όπου αν το Χ είναι 3 δίνει το 5 και όταν είναι το 5 δίνει 3. Ομοίως για 1 και 2 ο τύπος είναι 3-Χ οπότε ή θα έχουμε 3-1 ή 3-2 που δίνουν αντίστοιχα τα 2 και 1.
Τι έκανε ο μέγιστος στο pdf....  βγάζει το υπόλοιπο ακέραιας διαίρεσης με το 2 και πρόσθετει το 1, οπότε για 2 υπόλοιπο 2 δίνει 0 και μετά συν ένα δίνει 1, ενώ για 1 υπόλοιπο 2 δίνει 1 και προσθέτει συν ένα άρα δίνει 2. Το οποίο είναι σωστό αλλά γενικά ο καλύτερος τύπος είναι ο πιο απλός αυτός με την αφαίρεση.

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3386
  • to Iterate is human to Recurse divine
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #7 στις: 17 Απρ 2020, 05:44:11 μμ »
Το παρουσιάζει ως εναλλακτικό τρόπο. Δεν είναι ο προτεινόμενος.
Δεν ξέρω πως σκέφτηκαν αλλά σε κάποιες περιπτώσεις το υπόλοιπο έχει έννοια γιατί μπορεί να το συνδέσεις με το ότι κάποιος παίκτης παίζει πάντα σε ζυγό γύρο ενώ ο άλλος σε μόνο.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

lalibi

  • Νέος
  • *
  • Μηνύματα: 5
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #8 στις: 26 Απρ 2020, 10:01:18 πμ »
Διάβασα λίγο το κώδικα στο pdf παραπάνω. Ο επόμενος παίκτης βγαίνει με ένα τύπο που δηλώνει αμέσως πως αυτός που το έγραψε δεν είχε εμπειρία.
Όταν μας ενδιαφέρει να εναλλάσσονται δύο τιμές πχ η 3 και η 5 τότε αρκεί ο τύπος 8-Χ όπου αν το Χ είναι 3 δίνει το 5 και όταν είναι το 5 δίνει 3. Ομοίως για 1 και 2 ο τύπος είναι 3-Χ οπότε ή θα έχουμε 3-1 ή 3-2 που δίνουν αντίστοιχα τα 2 και 1.
Τι έκανε ο μέγιστος στο pdf....  βγάζει το υπόλοιπο ακέραιας διαίρεσης με το 2 και πρόσθετει το 1, οπότε για 2 υπόλοιπο 2 δίνει 0 και μετά συν ένα δίνει 1, ενώ για 1 υπόλοιπο 2 δίνει 1 και προσθέτει συν ένα άρα δίνει 2. Το οποίο είναι σωστό αλλά γενικά ο καλύτερος τύπος είναι ο πιο απλός αυτός με την αφαίρεση.

Η χρήση της αριθμητικής modulo για σειρές στοιχείων που επαναλαμβάνονται είναι συνηθισμένη, αν είχαμε ένα παιχνίδι με 4 παίχτες τότε η έκφραση "γύρος % 4 + 1" (ή παρόμοιες) μας δίνει ποιος είναι ο επόμενος παίχτης. Δε νομίζω ότι είναι και τόσο τραβηγμένη, ίσα ίσα είναι μια αρκετά γενικευμένη λύση για τέτοιες περιπτώσεις.

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 455
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: ΑΣΚΗΣΗ ΦΤΙΑΞΕ ΤΟ ΠΑΙΧΝΙΔΙ ΝΙΜ
« Απάντηση #9 στις: 26 Απρ 2020, 10:40:58 πμ »
 Στα πολλά άτομα-παίκτες γίνονται ένα από τα δύο:
Αν όλοι οι παίκτες συμμετέχουν μέχρι το τέλος του παιχνιδιού έχουμε μια ΓΙΑ ΑΠΟ ΜΕΧΡΙ....
Αν έχουμε έξοδο παίκτη σταδιακά τότε έχουμε μια ουρά, όπου ο πρώτος που μπαίνει βγαίνει πρώτος, για να παίξει το γύρο και ή συνεχίζει, ξανά μπαίνει στην ουρά ή βγαίνει εκτός παιχνιδιού (πχ τερμάτισε), δεν μπαίνει, και το παιχνίδι τελειώνει όταν ξεκινάει γύρος με άδεια ούρα.
Με τις κυκλικές ουρές σε πίνακες ασφαλώς η modulo θα χρησιμοποιηθεί, ως μέρος της κατασκευής της. Τυγχάνει βέβαια το μέγεθος της ουράς να είναι μην είναι ο αριθμός των παικτών που συνεχίζουν, αλλά ο μέγιστος αριθμός παικτών. Ο αριθμός των στοιχείων στην ουρά είναι ο αριθμός των παικτών στο παιχνίδι, σε φάση παιξίματος παίκτη μείον ένα. Οπότε υπάρχει περίπτωση να αδειάσει η ουρά αλλά επειδή συνεχίζει ο παίκτης στον επόμενο γύρο στην αρχή θα είναι πάλι ευντός ουράς!
« Τελευταία τροποποίηση: 26 Απρ 2020, 10:53:43 πμ από bugman »