Chess Engines Algorithms

Γενικά θέματα για τις γλώσσες προγραμματισμού που δεν καλύπτονται από τις άλλες περιοχές της κατηγορίας.

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
tommai
Δημοσιεύσεις: 73
Εγγραφή: 18 Ιαν 2008 03:46

Chess Engines Algorithms

Δημοσίευση από tommai » 11 Σεπ 2010 01:27

Θα ήθελα να προγραμματίσω μια τέτοια μηχανή ...
ξέρει κάποιος σε τι αλγόριθμους πρέπει να δουλέψω...?
έχω βρει του Shannon type A και B... με brute force και minimax...
ξέρει κανείς να μου πει...? επίσης όποιος έχει κάνει κάτι ανάλογο θα χαρώ πολύ να με βοηθήσει να αρχίσω....:-)

billiaswhs
Δημοσιεύσεις: 346
Εγγραφή: 11 Νοέμ 2004 00:29
Επικοινωνία:

Chess Engines Algorithms

Δημοσίευση από billiaswhs » 11 Σεπ 2010 02:12

Γεια σου φίλε, για τη brute force δεν ξέρω το minimax είναι
θεώρημα απο τη θεωρία παιγνίων όπου έχει ο σκοπό την εύρεση στρατιγικής
η οποία έχει την ελαχιστή απώλεια για το μεγιστο δυνιτικό κέρδος

δες και το παρακάτω link

people.csail.mit.edu/plaat/mtdf.html

tommai
Δημοσιεύσεις: 73
Εγγραφή: 18 Ιαν 2008 03:46

Chess Engines Algorithms

Δημοσίευση από tommai » 11 Σεπ 2010 02:49

billiaswhs έγραψε:Γεια σου φίλε, για τη brute force δεν ξέρω το minimax είναι
θεώρημα απο τη θεωρία παιγνίων όπου έχει ο σκοπό την εύρεση στρατιγικής
η οποία έχει την ελαχιστή απώλεια για το μεγιστο δυνιτικό κέρδος

δες και το παρακάτω link

people.csail.mit.edu/plaat/mtdf.html
γειά σου και σε σένα φίλε και ευχαριστώ για την απάντηση σου...
εκτός του minimax βρήκα και τον Αlpha-beta που είναι καλύτερος απο τον minimax και οι δύο λειτουργούν με δέντρα σωστά..?

λέω να την γράφω σε C ξέρει κανένας κάποιο πρόγραμμα σκάκι που να μου δείνει έτοιμο το γραφικό περιβάλλον και να τρέξω εγώ την μηχανή....? απο το exe που θα κάνω εγώ στην C...?
υπάρχουν πουθενά κώδικες απο έτοιμες μηχανές να δώ και να πάρω μία ματιά...?
κανένας που να έχει κάνει κάτι παρώμιο....?

Άβαταρ μέλους
Kainourios
Ruby Moderator
Δημοσιεύσεις: 504
Εγγραφή: 18 Μάιος 2005 16:20
Τοποθεσία: Κορυδαλλός
Επικοινωνία:

Chess Engines Algorithms

Δημοσίευση από Kainourios » 11 Σεπ 2010 12:48

Θα σου πω τι ξέρω σε θεωρητικό επίπεδο σαν σκακιστής που το έχω ψάξει λίγο (και είναι συμπεράσματα δικά μου οπότε ίσως κάπου να είναι λάθος).


Υπάρχουν πολλές μηχανές για σκάκι, αυτές που ξεχωρίζουν σε δυναμικότητα είναι ο fritz, η rybka, ο shredder και ο junior με διαφορές στον τρόπο παιξίματος ανάλογα με το μέτρημα - στρατηγικό τρόπο παιξίματος. Π.χ. η rybka που αυτή τη στιγμή είναι η πιο δυνατή μηχανή, παίζει πιο στρατηγικά από όλες τις άλλες μηχανές μετρώντας τις λιγότερες κινήσεις ενώ ο junior είναι η πιο brute force μηχανή.


Ο Junior ξεκίνησε ερασιτεχνικά και άρχισε να βρίσκει ματ σε μια, έπειτα ματ σε δύο κλπ. μέχρι που έφτασε εδώ που έφτασε και θεωρείται ο πιο κομπιουτερίστικος τρόπος παιξίματος καθώς μετράει τις περισσότερες κινήσεις από όλες τις άλλες μηχανές (και παίζει πιο τακτικά από όλες). Ο υπολογιστής στην ουσία αυτό κάνει όπως φαντάζομαι θα ξέρεις αφού έχεις ασχοληθεί, μετράει παρακάτω όλες τις πιθανές κινήσεις με brute force.


Οπότε αν θες να φτιάξεις μια μηχανή, ξεκίνα από το να φτιάχνεις να βρίσκει ματ σε μια για αρχή (ήθελα να το κάνω πτυχιακή κάποτε). Οι παραπάνω μηχανές είναι κλειστού κώδικα, υπάρχει μια πολύ δυνατή ανοιχτού κώδικα, ο Crafty όπου μπορείς να διαβάσεις τον κώδικα του και στη wikipedia λέει επίσης αλγορίθμους και τεχνικές για το τι χρησιμοποιεί.


Επίσης όλες οι μηχανές χρησιμοποιούν ένα βιβλίο ανοιγμάτων γιατί στην αρχή του παιχνιδιού δε μπορούν να προβλέψουν - καταλάβουν τίποτα και παίζουν ότι να 'ναι, τους φαίνονται όλα ίδια (είναι πολύ χαοτικό το παιχνίδι όσο υπάρχουν πολλά κομμάτια, όσο προχωράει η παρτίδα αρχίζει να ξεκαθαρίζει). Αντίθετα όσο μειώνονται και φτάνουμε στο φινάλε τόσο καλύτερα παίζουν, μάλιστα το παιχνίδι έχει λυθεί για όλες τις πιθανές θέσεις μέχρι 7 κομμάτια αν δεν κάνω λάθος και μπορείς να κατεβάσεις την βάση όπου είναι 4TB. Οπότε όταν υπάρχουν λίγα κομμάτια ο υπολογιστής δε χρειάζεται να υπολογίζει αλλά απλά κοιτά τη βάση και καταλαβαίνει πώς κερδίζει κλπ.


Έχω ένα φίλο που έχει κατεβάσει όλες τις πιθανές θέσεις για 6 κομμάτια και είναι 60GB η βάση (βλέπεις τη διαφορά; Προσθέτεις ένα κομμάτι επιπλέον και από 60GB πάμε στα 4TB, ανεβαίνουμε εκθετικά σε αριθμό θέσεων όσο προσθέτουμε κομμάτια όπου χάνεται η μπάλα κάποια στιγμή).


Η ντάμα ας πούμε με αυτόν τον τρόπο έχει λυθεί (βλέπε chinook), ξέρουμε σε κάθε θέση όλες τις δυνατές θέσεις που προκύπτουν, οπότε ξέρουμε ποια είναι η καλύτερη κίνηση που κερδίζει. Το σκάκι όμως μάλλον δε γίνεται να λυθεί έτσι αν δεν υπάρξει κάποιο πολύ μεγάλο τεχνολογικό άλμα οπότε χρειάζεται να υπολογίζουμε τις καλύτερες κινήσεις.


Όσο για τη σύνδεση της μηχανής με ένα UI, χρησιμοποιείται ένα stadar πρωτόκολλο, αλλά προσωπικά είχα διαβάσει τα specs και δεν το είχα, αν και έχω φτιάξει GUI να παίζεις σκάκι μόνος σου. Υπάρχουν έτοιμα open source UIs πάντως, το arena είναι το γνωστότερο αλλά έχει σταματήσει να αναπτύσσεται πλέον. Επίσης υπάρχει και το FICS, όπου μπορείς να φτιάξεις μια μηχανή και να την βάλεις να παίζει online είτε με πραγματικούς άλλους παίχτες είτε με μηχανές.


Γενικότερα μετράει πολύ και το hardware, π.χ. o deep blue της IBM (που νίκησε και καλά τον Kasparov) ήταν υπερυπολογιστής που δε στηριζόταν τόσο στη μήχανή όσο στο hardware.


Είχε φτιαχτεί ένας άλλος υπερυπολογιστής, η hydra όπου απ' ότι ξέρω ήταν ότι πιο δυνατό υπήρξε ποτέ (την έβαζαν σε τουρνουά και όποτε έχανε, της διπλασίαζαν το hardware, έτσι έφτασε σε ένα σημείο που δεν ξανάχασε, έκανε μόνο ισοπαλίες... εξού και το όνομα hydra, τις έκοβες το ένα κεφάλι και φύτρωναν 2 :)).


Μέτραγε ας πούμε όμως 18 κινήσεις παρακάτω σε μια θέση σε ένα φυσιολογικό χρονικό περιθώριο, για να φτάσει να μετράει 19, έπρεπε το hardware να γίνει 100 φορές πιο δυνατό μετά από κάποια στιγμή και η διαφορά θα ηταν μια κίνηση που ίσως να μην πρόσθετε κάτι σημαντικό... αυτό το "κακό" έχει το παιχνίδι :D, μεγαλώνει εκθετικά ο αριθμός όσο αυξάνονται τα κομμάτια ή οι παρακάτω κινήσεις που πρέπει να μετρήσεις παρακάτω.


Γενικά αν ήταν οpen source οι μηχανές θα είχαμε φτάσει σε πολύ καλύτερο επίπεδο σκακιστικών προγραμμάτων, πρόσφατα υπήρξε μια μηχανή που ήταν open source (goldfish νομίζω λέγεται) και έλεγε ότι είχε κάνει με reverse engineering αντιγραφή τη μηχανή της rybka... παίξανε όμως σε ένα τουρνουά και έχασε. Αυτά, σταματάω εδώ γιατί όλο μεγάλα άρθρα γράφω και δεν τα διαβαζει κανείς! Ελπίζω να βοήθησα :)

LightForce
WebDev Moderator
Δημοσιεύσεις: 3812
Εγγραφή: 13 Απρ 2003 23:49

Chess Engines Algorithms

Δημοσίευση από LightForce » 11 Σεπ 2010 12:55

Θεωρία για αλγόριθμους που ίσως χρειαστείς μπορείς να διαβάσεις εδώ
Προτείνω να ξεκινήσεις από ένα project όπως tic-tac-toe η reversi. Ο minimax και ο negamax είναι αλγόριθμοi που χρησιμοποιούνται σε παρόμοια 2P παιχνίδα. Αlpha-Beta pruning είναι μία μόνο από τις πολλές τεχνικές που εφαρμόζεται πάνω σε αυτούς τους αλγόριθμους για να μειωθεί το δέντρο ψαξίματος το οποίο σε ένα παιχνίδι όπως το σκάκι τείνει στο..άπειρο.

Άβαταρ μέλους
soteres2002
S. & H. Moderator
Δημοσιεύσεις: 1524
Εγγραφή: 05 Μαρ 2004 22:17
Τοποθεσία: Ιωάννινα

Chess Engines Algorithms

Δημοσίευση από soteres2002 » 11 Σεπ 2010 15:04

Des kai Simulated Annealing. Einai algorithmos efious veltistopoiisis pou kanei minimization se mia sinartisi kostous psaxnontas ston xwro katastasewn ton skakieron, kai sou vriskei topika i olika veltistes liseis... Poli klassikos AI algorithmos, vriskei ti lisi se tetarstious xwrous se mono 1-2 seconds!! Mas to evalan kai ws askisi se project texnitis noimosinis sto panepistimio. isws kratisa ton kwdika - an ton vrw tha sou stilw..

Kati allo poli kalo pou boreis na dokimaseis einai o A* algorithmos...

Iparxoun kai pio eksidikevmena pragmata pou gia na ta kaneis prepei na psaxeis se bibliographia... San klassikes liseis padws o A* kai i prosomioumeni anwptisi (simulated annealing) einai poli apotelesmatikes....

o A* opws kai o simulated annealing apaitei na oriseis mia sinartisi heuristic me basei tin opia tha apofasizei pio monopati liseis na akolouthisei.. An boreis na vreis polles apodektes evretikes sinartiseis, tote lambanontas to max tous boreis na ftiaxeis mia global heuristic function pou einai kaliteri apo oles tis alles... Ayto tha sou eksasfalisei oti oxi aplws tha vriskeis ti lisi alla tha einai kai veltisti!

tommai
Δημοσιεύσεις: 73
Εγγραφή: 18 Ιαν 2008 03:46

Chess Engines Algorithms

Δημοσίευση από tommai » 11 Σεπ 2010 15:17

LightForce έγραψε:Θεωρία για αλγόριθμους που ίσως χρειαστείς μπορείς να διαβάσεις εδώ
Προτείνω να ξεκινήσεις από ένα project όπως tic-tac-toe η reversi. Ο minimax και ο negamax είναι αλγόριθμοi που χρησιμοποιούνται σε παρόμοια 2P παιχνίδα. Αlpha-Beta pruning είναι μία μόνο από τις πολλές τεχνικές που εφαρμόζεται πάνω σε αυτούς τους αλγόριθμους για να μειωθεί το δέντρο ψαξίματος το οποίο σε ένα παιχνίδι όπως το σκάκι τείνει στο..άπειρο.
φίλε μπορείς να μου πείς που θα βρώ άλλες τεχνικές όπως και το Αlpha-Beta ας πούμε....?
να ψαχτώ λίγο πάνω σε αυτό πρώτα και μετά να προχωρίσω να γράψω κώδικα....
κατέβασα το αρένα που είπε ο φίλος παρα πάνω και όντως κάνει αυτήν την δουλειά.... :)
αλλα δεν ξέρω σε ποιούς αλγόριθμουσ να βασιστό πρώτα και γιατί να επιλέξω αυτούς...
π.χ σπο ψάξιμο που έκανα βρήκα οτι πρέπει να ασχολιθώ και με πράγματα της Ασαφούς λογικής (Fuzzy logic systems)....

LightForce
WebDev Moderator
Δημοσιεύσεις: 3812
Εγγραφή: 13 Απρ 2003 23:49

Chess Engines Algorithms

Δημοσίευση από LightForce » 11 Σεπ 2010 16:13

Δες το Chess Programming Wiki, όπου θα βρείς τις πληροφορίες για την υλοποίηση ενός Chess game.
Τελευταία επεξεργασία από το μέλος LightForce την 11 Σεπ 2010 16:15, έχει επεξεργασθεί 1 φορά συνολικά.

Άβαταρ μέλους
soteres2002
S. & H. Moderator
Δημοσιεύσεις: 1524
Εγγραφή: 05 Μαρ 2004 22:17
Τοποθεσία: Ιωάννινα

Chess Engines Algorithms

Δημοσίευση από soteres2002 » 11 Σεπ 2010 16:13

tommai έγραψε: σπο ψάξιμο που έκανα βρήκα οτι πρέπει να ασχολιθώ και με πράγματα της Ασαφούς λογικής (Fuzzy logic systems)....
με τα ασαφή συστήματα δεν πρόκειται να βγάλεις άκρη... Πρέπει να διαβάσεις πολύ. Έχει τόνους θεωρίας, τα ασαφή σύνολα - fuzzy sets, και δύσκολα θα τα εφαρμόσεις στο πρόβλημα του σκακιού γιατί πρέπει να έχεις την εμπειρία ώστε να ορίσεις τα κατάλληλα ασαφή σύνολα για το πρόβλημα! Εκτός κι αν εχεις δει κάποια λύση δημοσιευμένη κάπου, οπότε και τότε θα έχεις φόρτο σε coding.

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

Γενικά το πρόβλημα που θέτεις έχει πολλές λύσεις και με διαφορετικούς αλγορίθμους. Ακόμα και με τους απλούς αλγορίθμους θέλει πολύ καλό planning πριν φτιάξεις κάτι καλό! Δεν ειναι τόσο απλό το ζήτημα...

LightForce
WebDev Moderator
Δημοσιεύσεις: 3812
Εγγραφή: 13 Απρ 2003 23:49

Chess Engines Algorithms

Δημοσίευση από LightForce » 11 Σεπ 2010 16:28

soteres2002 έγραψε:Γενικά το πρόβλημα που θέτεις έχει πολλές λύσεις και με διαφορετικούς αλγορίθμους. Ακόμα και με τους απλούς αλγορίθμους θέλει πολύ καλό planning πριν φτιάξεις κάτι καλό! Δεν ειναι τόσο απλό το ζήτημα...
Ακριβώς έτσι, ένα παιχνίδι σκάκι στον υπολογιστή είναι επιστήμη.

Γι'αυτό και γενικά *προτείνω tommai να ξεκινήσεις να δουλεύεις με έναν τύπου minimax αλγόριθμο.
Να τον κατανοήσεις και να τον εφαρμόσεις σε παιχνίδια 2P προτού ξεκινήσεις να μελετάς κώδικα από δυνατές μηχανές όπως ο open source Crafty που ανέφερθηκε και περιλαμβάνει μεταξύ άλλων:

..negascout search, the killer move heuristic, static exchange evaluation, quiescence search, alpha-beta pruning, a transposition table, a refutation table, an evaluation cache, selective extensions, recursive null-move search, and many other features


*Χωρίς να γνωρίζω το επίπεδο σου στην γλώσσα που προγραμματίζεις.

tommai
Δημοσιεύσεις: 73
Εγγραφή: 18 Ιαν 2008 03:46

Chess Engines Algorithms

Δημοσίευση από tommai » 11 Σεπ 2010 17:01

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

billiaswhs
Δημοσιεύσεις: 346
Εγγραφή: 11 Νοέμ 2004 00:29
Επικοινωνία:

Chess Engines Algorithms

Δημοσίευση από billiaswhs » 11 Σεπ 2010 23:30

Για το minimax δοκίμασε το gabit για να βλέπεις αποτελέσματα των δέντρων
Gambit: Software Tools for Game Theory

tommai
Δημοσιεύσεις: 73
Εγγραφή: 18 Ιαν 2008 03:46

Chess Engines Algorithms

Δημοσίευση από tommai » 12 Σεπ 2010 15:16

υπάρχει κάποιο βιβλίο που να λέει πώς να αρχίσω...? δηλ για τον προγραμματισμό τέτοιον παιχνιδιών...? σε C++ η C#
βήμα βήμα δηλαδή τι πρέπει να κάνω τη αλγόριθμους να χρισοιμοποιησω...?

billiaswhs
Δημοσιεύσεις: 346
Εγγραφή: 11 Νοέμ 2004 00:29
Επικοινωνία:

Chess Engines Algorithms

Δημοσίευση από billiaswhs » 12 Σεπ 2010 17:54

μάλλον θα πρέπει αρχικά να στήσεις παρτίδα για δύο παίχτες σε ένα βιβλίο τη
php το PHP Game Programming δες το κεφάλαιο 7 που λέγεται
playing Chess and Database για να δεις πως γίνεται και στη συνέχεια
το εμπλουτίζεις στη θέση του ενός παίχτη να δουλευει ο αλγόριθμος

tommai
Δημοσιεύσεις: 73
Εγγραφή: 18 Ιαν 2008 03:46

Chess Engines Algorithms

Δημοσίευση από tommai » 12 Σεπ 2010 23:22

γιατί να μπλέκω και με php...?? μια μηχανή θα ήθελα να κάνω να τρέχει με το ARENA δεν με νιάζει αυτήν την στιγμή πόσο δυνατή θα είναι η μηχανή αλλα μόνο να τρέχει... ίσως κάποιος να ξέρει κάποια μηχανή open source σε C++ να πάρω κάποια γεύση το τί γίνεται και πώς εφαρμόζεται ο αλγόριθμος πάνω εκεί...???

Απάντηση

Επιστροφή στο “γλώσσες προγραμματισμού - γενικά”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες