Print Page - [Δομές Δεδομένων] Τουρνουά Blokus

Title: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: Wade on February 06, 2009, 01:42:11 am

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

Λοιπόν, σ' αυτό το τόπικ μπορείτε να ποστάρετε τους αλγόριθμούς σας! :)

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: Wade on February 06, 2009, 01:44:54 am

Παρακάτω δίνουμε τον full κατάλογο των τεχνικών μας. Παρακαλούνται και οι υπόλοιπες ομάδες να "καρφώσουν" τις μεθόδους τους ;)

Ομάδα Α5 (Ομάδα 16 δηλώσεων):
Καράς Δημήτριος
Κουφογιάννης Φραγκίσκος

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

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

Το βάθος της ανάλυσης μεταβάλλεται ανάλογα με την κίνηση στην οποία βρισκόμαστε, έτσι ώστε να αξιοποιείται ο διαθέσιμος χρόνος των 15 δευτερολέπτων ανά κίνηση. Συγκεκριμένα (όπου βάθος 1 σημαίνει την ανάλυση μόνο του χρώματος που παίζει, χωρίς να ψάχνει άλλα χρώματα):
4η κίνηση: Βάθος 1
5η – 10η κίνηση: Βάθος 2
11η – 15η κίνηση: Βάθος 3
16η – 21η κίνηση: Βάθος 2

Οι συναρτήσεις αξιολόγησης που χρησιμοποιήθηκαν είναι οι εξής:
evaluate: Επιστρέφει μια γραμμική σχέση μεταξύ των διαθέσιμων γωνιών της ομάδας του παίκτη και της ομάδας του αντιπάλου. Για την 6η ως την 11η κίνηση, ο παίκτης γίνεται αρκετά επιθετικός: ο αριθμός των γωνιών του αντιπάλου πολλαπλασιάζεται επί 2 έτσι ώστε να δοθεί μεγαλύτερη βαρύτητα στο κλείσιμο των γωνιών του αντιπάλου. Για τις υπόλοιπες κινήσεις, η συνάρτηση επιστρέφει τη διαφορά των γωνιών των δύο αντίπαλων ομάδων.

DangerousCorners: Μία δευτερεύουσα συνάρτηση αξιολόγησης που περιφέρει ένα τετράγωνο 3x3 στο ταμπλό και ψάχνει γωνίες του αντιπάλου που αποτελούν άμεση απειλή για μία ή περισσότερες από τις δικές μας γωνίες.

Οι παραπάνω δύο στρατηγικές μπορούν να ιδωθούν από μια γενικότερη σκοπιά. Το γενικό πρόβλημα έχει ως εξής: «Δοθείσας μιας σκακιέρας με κάποια κομμάτια τοποθετημένα να εξαχθούν κάποια χρήσιμα συμπεράσματα». Έτσι, χρησιμοποιούνται διάφορα φίλτρα που σαρώνουν τη σκακιέρα. Αν το φίλτρο αυτό είναι ένα τετράγωνο 2x2 εντοπίζεται το είδος της γωνίας. Για 3x3 υπολογίζεται ο κίνδυνος για κάποια γωνία. Μήπως για 4x4 μπορεί να εξαχθεί κάποιο ανάλογο συμπέρασμα;

Τέλος, από τον αλγόριθμο minimax μπορεί να προκύψουν πολλές κινήσεις με την ίδια αξία. Μεταξύ των κινήσεων με τη μεγαλύτερη αξία, επιλέγεται αυτή που έχει τη μεγαλύτερη απόσταση από τη γωνία εκκίνησης, στα πλαίσια της επιθετικής στρατηγικής που εφαρμόζεται.

Σ’ αυτό το σημείο μπορούμε να παρουσιάσουμε τον αλγόριθμο σε μορφή φυσικής γλώσσας:

Αν είναι η 1η, 2η ή 3η κίνηση:
   Τοποθέτησε την κατάλληλη προκαθορισμένη κίνηση
Αλλιώς:
   Προσδιόρισε το βάθος ανάλογα με τον αριθμό της κίνησης
   Κάλεσε την αναδρομική συνάρτηση του αλγορίθμου minimax μ’ αυτό το βάθος
      Εφάρμοσε τις συναρτήσεις αξιολόγησης evaluate και DangerousCorners
      Βρες τη μέγιστη αξία κίνησης και τις αντίστοιχες κινήσεις
      Μεταξύ αυτών, διάλεξε αυτήν που είναι μακρύτερα από τη γωνία εκκίνησης
   Παίξε την κίνηση που επιστρέφει η αρχική κλήση της αναδρομικής συνάρτησης

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: miltiadis on February 06, 2009, 11:03:28 am

Εμείς στην Ομάδα 2 (Α2) ο κώδικάς μας έτρεχε ως εξής:

Αν είναι κάποια από τις 1ες τρεις κινήσεις, παίξε ένα κομμάτι σε προκαθορισμένη θέση
Αλλιώς Βρες όλα τα πιθανά κομμάτια
Για κάθε κομμάτι στα πιθανά κομμάτια
Δημιούργησε ένα νέο board και παίξε αυτή την κίνηση.
Αξιολόγησε την κίνηση αυτή, αναδρομικά μεσω της συνάρτησης alphabetaPruning.
Αν είναι καλύτερη από τις προηγούμενες αποθήκευσέ.

Παίξε την καλύτερη κίνηση

alphabetaPruning()
Αν το βάθος αναζήτησης είναι 0 ή δεν υπάρχουν επόμενες κινήσεις επέστρεψε το evalute (board)
Βρές όλες τις πιθανές κινήσεις για το καινούριο board
Για κάθε κίνηση
Αξιολόγησέ την
Αν έχει βρεθεί άλλη κίνηση που να συμφέρει τον προηγούμενο παίκτη περισσότερο σταμάτα (κλάδεμα)
Αν η αξιολόγηση της κίνησης είναι καλύτερη από τις προηγούμενες αποθήκευσέ την.
Επέστρεψε την καλύτερη αξιολόγηση για τον παίκτη που παίζει τώρα

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

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

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: cyberwizard on February 06, 2009, 14:06:41 pm

Ομάδα Α1
Σπανουδάκης Εμμανουήλ
Σκαλίδης Εμμανουήλ

Ο δικός μας αλγόριθμος, έτρεχε με μάλλον απλό τρόπο, σε σχέση τουλάχιστον με τους προλαλήσαντες :) .

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

2.Έκανε έλεγχο ώστε, αν έστω και ένα από αυτά τα κομμάτια χωρούσε στο ταμπλώ, έδινε το Οκ για συνέχιση του αλγορίθμου. Ειδαλλώς, επέστρεφε στο βήμα 1, για αριθμό τετραγώνων μειωμένο κατά 1. Αν τελειώναν οι επαναλήψεις και δεν είχε βρεθεί ούτε μια πιθανή κίνηση, ο αλγόριθμος έθετε τον παίχτη μας σε κατάσταση Dead.

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

4.Για κάθε κίνηση του παίχτη μας, εφαρμόζαμε τα βήματα 1 και 2, για τον επόμενο αντίπαλο μας.

5.Εφόσον ο αντίπαλος είχε κινήσεις να παίξει, δημιουργούμε ένα δεύτερο ταμπλώ κλώνο, κλώνο του προηγούμενου κλώνου (κλώνοι παντού!).Παίζουμε σε αυτό το ταμπλώ την κίνηση του αντιπάλου.

6.Καλούμε την evaluate(clone2), για αξιολόγηση του ταμπλώ. Η αξιολόγηση του ταμπλώ γινόταν μόνο με την χρήση της διαφοράς : Τρέχουσες γωνίες παιχτών μας - Τρέχουσες γωνίες αντιπάλων μας.

7.Επαναλαμβάνουμε τα βήματα 5,6 για όλες τις κινήσεις του αντιπάλου μας.
8.επιστρέφουμε στο βήμα 3, για τα επόμενα πιθανά κομμάτια του παίχτη μας.

9.Με γεμάτο πλέον το δέντρο μας, εφαρμόζαμε τον αλγόριθμο minimax, και επιλέγαμε την καλύτερη κίνηση.
10.Παίζαμε την κίνηση.

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: SolidSNK on February 06, 2009, 14:20:52 pm

grz wade :)

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

Έκανα 4 (ουσιαστικά 3) evaluation functions, που βασίστηκαν στο μοντέλο με τη διαφορά γωνιών , αλλά επεκτάθηκα αρκετά καθώς εισήγαγα δυναμική αξιολόγηση της αξίας κάθες γωνίας, ανάλογα με πόσα κ ποια κομμάτια μπορούν να παιχτούν και αν καλύπτεται πλάγια από κάποιο αντίπαλο χρώμα. Μια ξεχωριστή function δημιουργήθηκε για την αξιολόγηση της επεκτασιμότητας της κίνησης. Επίσης , έκανα διάφορα trick για να νικήσω το χρόνο, όπως ίδιες 3 πρώτες κινήσεις , αλλά και περιορισμό της scan the board στο κέντρο του ταμπλό για μικρότερες δυνατές κινήσεις (στην αρχή του παιχνιδιού). Θα ποσταριστούν σήμερα αν δε βαριέμαι. Σόρρυ , αλλά ξενέρωσα πάρα πολύ άγρια.

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: Matzika on February 06, 2009, 23:54:21 pm

Quote from: cyberwizard on February 06, 2009, 14:06:41 pm

ακριβώς τον ίδιο αλγόριθμο γράψαμε!! :P

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: edenaxas on February 07, 2009, 01:51:01 am

Quote from: SolidSNK on February 06, 2009, 14:20:52 pm

μηπως αργουσε πολυ να δωσει αποτελεσμα?

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: SolidSNK on February 07, 2009, 06:37:53 am

noez, η δομή του δέντρου αργούσε , το evaluation παραδοσιακά δεν είναι το χρονοβόρο κομμάτι.

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: edenaxas on February 07, 2009, 13:43:23 pm

Quote from: SolidSNK on February 07, 2009, 06:37:53 am

noez, η δομή του δέντρου αργούσε , το evaluation παραδοσιακά δεν είναι το χρονοβόρο κομμάτι.

σε αυτο αναφερομαι. συνηθως αν δεν κανεις μια αποδοτικη recursive παιρνει πολυ. απο την αλλη αν εχεις κανει recursive που εξεταζει καθε κλαδο μεχρι ενα συγκεκριμενο βαθος και πισω, αν εχεις βαλει πολυ βαθος, θα σου αργησει. απλα και περυσι που ειχαν τουρνουα mancala, ο junior ειχε κανει ενα καλο, σωστο αλγοριθμο depth first, αλλα ειχε βαλει να ψαχνει μεχρι βαθος 13. Ομως κριτιριο ηταν να εχεις αποτελεσμα σε 15sec, αν θυμαμαι καλα. γι'αυτο σου λεω, μηπως σου αργησε το tree searching?

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: SolidSNK on February 07, 2009, 14:10:54 pm

χεχ νόμιζα αναφερόσουν μόνο στα evaluation. Ναι η δημιουργία του δέντρου αργούσε πολύ. Το να κάνεις evaluate είναι , σου λέω, ελάχιστα μιλιδευτερόλεπτα. Την ερώτηση γενικά δεν την καταλαβαίνω (αυτό το "tree searching" :???:)... επαναλαμβάνω αργούσε η δημιουργία του δέντρου από βάθος 2 και άνω. Γι αυτό και παράτησα τελείως τη φάση δέντρο.
Για ταχύτητα αυτό που έκανα ήταν να φτιάξω τη CentreScanTheBoard που ήταν μια πετσοκομμένα scantheboard για το κέντρο του ταμπλό στην αρχή του παιχνιδιού.

Code:

public MySet_6478_6501 CentreScanTheBoard(Board B , Color c)
	{
		MySet_6478_6501 moves = new MySet_6478_6501();
		for ( int i = 6 ; i < B.getDimensions()[0] - 6 ; i++ )
		{
			for (int j = 6 ; j < B.getDimensions()[1] - 6 ; j++ )
			{
				if (B.getBoard()[i][j].getColor() == c)
				{
					if ( B.getBoard()[i-1][j].getColor() != c && B.getBoard()[i][j-1].getColor() != c && B.getBoard()[i-1][j-1].getColor() == null)
					{
						//Add an element to the array
						moves.add(new SetElement(null , i , j , 1));
					}
					if ( B.getBoard()[i-1][j].getColor() != c && B.getBoard()[i][j+1].getColor() != c && B.getBoard()[i-1][j+1].getColor() == null)
					{
						//Add an element to the array
						moves.add(new SetElement(null , i , j , 2));
					}
					if ( B.getBoard()[i+1][j].getColor() != c && B.getBoard()[i][j-1].getColor() != c && B.getBoard()[i+1][j-1].getColor() == null)
					{
						//Add an element to the array
						moves.add(new SetElement(null , i , j , 3));
					}
					if ( B.getBoard()[i+1][j].getColor() != c && B.getBoard()[i][j+1].getColor() != c && B.getBoard()[i+1][j+1].getColor() == null)
					{
						//Add an element to the array
						moves.add(new SetElement(null , i , j , 4));
					}
				}	
			}
		}
		return moves;
	}

Να τα evaluations:

Η power rating βασίζεται στο ότι μια γωνία στην οποία μπορούν να παιχτούν κομμάτια είναι ισχυρή. Όρισμα έπαιρνε ένα μόνο set element , και καλλούσε τι where it fits για το mini αυτό myset.

Code:

int cornerPowerRating(Board b , Color c , gr.auth.ee.dsproject.blokus.set.SetElement move )
	{
		int rating = 0;
		MySet_6478_6501 testmove = new MySet_6478_6501();
		testmove.add(move);
		for (int i = 0 ; i < b.getPlayerForColor(c).getInventory().size() ; i++)
		{
			Piece testpiece = b.getPlayerForColor(c).getInventory().elementAt(i);
			MySet_6478_6501 moves = findWhereItFits(b , testpiece.clone() , testmove);
			if ( !moves.isEmpty() )
			{
				rating += getboxnum(testpiece);
			}
		}
		return rating;
	}

Η βασική evaluation function usablecornerseval, που βασιζόταν στο κλασσικό γωνίες μου μείων γωνιες τους. Εδώ τέσταρε πρώτα αν χωράει το μονόμινο στη γωνία, και αν όχι τότε δεν υπολογιζόταν καθόλου. Αν μπορούσε να μπει , προσθέταμε στο γενικό αποτέλεσμα τη βαρύτητα της γωνίας , που επηρρεαζόταν από 2 πράγματα. Το ένα , αν περικλείται από 1 ή 2 χρώματα του αντιπάλου , όπου αντί για 1 είχε βαρύτητα 2 , 3 αντίστοιχα (ή 3 , 5 δεν είχα καταλήξει τελείως σε αυτό) διότι η γωνία θεωρούταν δεδομένη , και το 1 , 2 ,3 επί το powerRating της γωνίας. Ε μετά αφαιρούσαμε το σύνολο για όλα τα χρώματα, ανάλογα ποιος ήταν φίλος και ποιος εχθρός για το τελικό evaluation. There you go

Code:

ωπ περιμένετε λίγο γιατί είμαι σε windows και την έχω στο linux, να της κάνω λίγο calibration και θα τη ποστάρω!

Αν το τελικό eval ήταν ίδιο μεταξύ των κινήσεων, υπήρχε μια απλή function για να ελέγχει την επεκτατικότητα κάθε κίνησης!

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: Matzika on February 07, 2009, 14:33:38 pm

Μεχρι πότε μπορούμε να ανεβάσουμε στο eTHMMY την αναφορά για την εργασία μας?Ειπε τίποτα ο κ Μήτκας?ή το άφησε στο αόριστο?

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: SolidSNK on February 07, 2009, 14:35:41 pm

Ουσιαστικά δλδ προέτρεπα στον αλγόριθμο μου να φτιάχνει "τουνελάκια" με τα αντίπαλα χρώματα, που δίνουν standard κινήσεις, μια στρατηγική που ακολουθώ και γω όταν πάιζω ;)

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: Wade on February 07, 2009, 14:38:04 pm

Quote from: Matzika on February 07, 2009, 14:33:38 pm

Αυτή για τον αλγόριθμο σε φυσική γλώσσα για τους συμμετέχοντες του τουρνουά; Αν είναι αυτό, πρέπει να το ποστάρεις σ' αυτό το τόπικ (ο κ. Μήτκας ανέφερε ότι πρέπει να γίνει ένα thread στο thmmy.gr όπου θα ποστάρουμε τους αλγορίθμους μας). Συγκεκριμένη ημερομηνία δε θυμάμαι να είπε...

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

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: Matzika on February 07, 2009, 20:28:03 pm

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

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: tiger on February 09, 2009, 21:42:42 pm

ο σιφουνας :D
ομαδα...β4??? δεν θυμαμαι ,δεν εβγαλαν κ τα αποτελεσματα του τουρνουα...
Στεφανου Γιωργος Τικοπουλου Πηνελοπη

Και ο δικος μου αλγοριθμος αρχικα εξεταζε αν υπαρχουν εγκυρες κινησεις για 5μινα κ αν υπηρχαν τοτε προχωρουσα μονο γι αυτα,αν δεν υπηρχαν ελεγχα αντιστοιχα τα 4μινα κτλ
Για καθε εγκυρη κινηση τοποθετουσα το κομματι σε ενα ταμπλω κλωνο του τρεχοντος.
Στην συνεχεια το ιδιο γινοταν κ τις πιθανες κινησεις του επομενου στην σειρα,αντιπαλου παιχτη. Για καθε εγκυρη κινηση του αντιπαλου τοποθετουσα το κοματι σε νεο κλωνο-οπως ολοι φανταζομαι ¨)
Τοτε εκανα την αξιολογιση της τρεχουσας κινησης με μετρηση των δικων μας γωνιων μειον τις γωνιες τοθ αντιπαλου και αν ηταν καλυτερη της προηγουμενης ,την κρατουσα. Οπως κ ο miltiadhs χρησιμοποιησα αλφα βητα κλαδεμα ,δηλαδη
αν έχει εντοπιστει άλλη κίνηση που να συμφέρει τον προηγούμενο παίκτη περισσότερο σταμάτα (κλάδεμα), ενω αν η αξιολόγηση της κίνησης είναι καλύτερη από τις προηγούμενες την κρατουσα.
Η καλυτερη κινηση αποθηκευονταν σε μια τριαδα μεταβλητων-αν θυμαμαι καλα-κ λεω αν θυμαμαι καλα γιατι αναπτυξα τουλαχιστον 3 ειδη δομων αποθηκευσης αλλα τελικα δεν μπορουσα να σιγουρευτω πως λειτουργουν σωστα ,οποτε εστειλα μια πιο απλοικη προσεγκιση της δομης. Ενδεικτικα να αναφερω πως μια απο τις δομες μου που εν τελει δεν εστειλα ,ηταν περιπου η εξης.. . για καθε εγκυρη κινηση του τρεχοντος παιχτη απο θηκευα σε μια δομη Μyset ενα setelement με ορισματα ¨΄null στο σχημα, αυξων αριθμο=ονομα στο χ , ονομα γονιου του φυλλου στο y και την τιμη της αξιολογησης στο corner. Για τον αντιπαλο τα ιδια κ σε μια δευτερη δομη κ επιπλεον μια τριτη δομη οπου για καθε στοιχειο την δευτερης δομης εβαζα κ ενα σ αυτην με ορισματα τετοια ωστε να μπορω να ξερω απο ποιο φυλλο του πρωτου παιχτη προηλθαν.
Αυτα πανω κατω,
Συγχωρηστε με 1) για την λακωνικοτητα αλλα δινω 4 μαθηματα αυτη τη βδομαδα..κ
Μετα δινω κ αλλα 2) για τον ενικο...αλλα πιστευω καταλαβαμε ολοι απο τον κοσμο στο τουρνουα γιατι πολλες ομαδες ειχαν ενα μονο εκπροσωπο- μαλον θα εκανε αυτος την περισσοτερη δουλεια ; )

Δεν τα πηγε κ πολυ καλα ο παιχτης μ καθως δεν προλαβα να εντοπισω καποια λογικα λαθη ομως ηταν μαλον ο ταχυτερος ολων-τι μαλον....σιγουρα, εκ του αποτελεσματος αλλα οκ..;P - κ ηταν πραγματικα ευχαριστο να βλεπεις ενα παιχνιδι να τελειωνει σε δευτερολεπτα-οσοι ηταν στο τουρνουα πιστευω καταλαβαινουν : )

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: SolidSNK on February 09, 2009, 22:46:53 pm

Απ' όσο βλέπω οι περισσότεροι αρκεστήκατε στη διαφορά γωνιών δλδ.

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: BLV on February 10, 2009, 23:07:13 pm

Ομάδα Β3 (Ομάδα 8)
Πλατή Παρασκευή
Χατζοπούλου Γεωργία

Έχουμε δημιουργήσει ένα πρόγραμμα στο οποίο ακολουθούμε την παρακάτω στρατηγική:
Αρχικά,από τα κομμάτια που έχουμε στη διάθεση μας και ξεκινώντας από αυτό με τον μεγαλύτερο αριθμό τετραγώνων βρίσκουμε τις πιθανές κινήσεις του παίκτη μας.Στην περίπτωση όμως, που για το συγκεκριμένο κομμάτι δεν υπάρχουν κινήσεις δοκιμάζουμε το αμέσως επόμενο.Στόχος μας είναι να "ξεφορτωθούμε" όσο το δυνατόν νωρίτερα τα μεγάλα κομμάτια.Εφόσον έχουμε βρει το κομμάτι που θέλουμε να τοποθετήσουμε καθώς και όλες τις διαθέσιμες κινήσεις του παίκτη καλούμε μία συνάρτηση minimax.
H συνάρτηση αυτή επιστρέφει τον αριθμό της καλύτερης δυνατής θέσης, ώστε να εχουμε τη λιγότερη δυνατή ζημιά. Πιο συγκεκριμένα η minimax τοποθετεί το κομμάτι σ' ένα εικονικό ταμπλό και κατόπιν ακολουθεί την ίδια διαδικασία για τις πιθανες κινήσεις του αντιπάλου.Κρίνεται αναγκαίο να επισημανθεί ότι η minimax κοιτάει τρεις κινήσεις:μία για εμάς, μία για τον αντίπαλό μας και μία ακόμη για εμάς (βάθος 3). Για την υλοποίηση της χρησιμοποιήσαμε άλλες τρεις συναρτήσεις:
την putpiece,την possiblemoves και την nextcolor.
Η nextcolor δέχεται το χρώμα του παίκτη που παίζει και επιστρέφει το χρώμα του επόμενου παίκτη.
Η putpiece δέχεται ένα ταμπλό, το χρώμα του παίκτη που παίζει, το σχήμα του κομματιού και τη θέση. Με δύο for σαρώνουμε το κομμάτι και το τοποθετούμε χρωματίζοντας το ταμπλό με το χρώμα του παίκτη που παίζει.
Η possiblemoves δέχεται ένα ταμπλό και το χρώμα του κομματιού και επιστρέφει έναν αντικείμενο places με τις πιθανές κινήσεις του παίκτη που παίζει. Δημιουργούμε ένα αντικείμενο κομμάτια το οποίο περιέχει τα κομμάτια που έχουν απομείνει για τον παίκτη που παίζει. Αν είναι άδεια τότε επιστρέφει ένα άδειο αντικείμενο. Ενώ αν δεν είναι άδεια τότε δημιουργεί ένα αντικείμενο τύπου piece και βρίσκει την πιθανή κίνηση με τη βοήθεια των συναρτήσεων scanTheBoard και findWhereItFits , για το μεγαλύτερο κομμάτι. Αν δεν υπάρχει πιθανή θέση για το μεγαλύτερο κομμάτι, τότε παίρνει το αμέσως επόμενο.
Στο τέλος του βάθους της minimax αξιολογούνται οι κινήσεις με την evaluate.Η evaluate είναι αυτή που δινόταν απο την εκφώνηση της άσκησης. Η evaluate λαμβάνει ένα ταμπλό και επιστρέφει τον αριθμό των ελεύθερων γωνιών του παίκτη μας - τον αριθμό των ελεύθερων γωνιών του αντιπάλου μας.Όταν, λοιπόν, καλούμε την evaluate αυτη επιστρέφει έναν αριθμό ο οποίος αξιολογεί την κίνηση. Όσο μεγαλύτερος είναι αυτός ο αριθμός τόσο καλύτερη θεωρείται η κίνηση.

τέλος

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: Matzika on February 11, 2009, 00:40:42 am

Quote from: tiger on February 09, 2009, 21:42:42 pm

αλλα πιστευω καταλαβαμε ολοι απο τον κοσμο στο τουρνουα γιατι πολλες ομαδες ειχαν ενα μονο εκπροσωπο- μαλον θα εκανε αυτος την περισσοτερη δουλεια ; )

τώρα θίχτηκα :P
δεν ξέρω τι συμβαίνει γενικά αλλα εγώ που δεν ήμουν στο τουρνουα σε πληροφορώ ότι έριξα περισσότερη δουλειά απο την κοπέλα που ήμασταν μαζί στην ομάδα...ελπίζω όσοι λείπαμε να μη δώσαμε αυτή την εντύπωση στους διδάσκοντες...
Η απουσία μου οφειλόταν:
1)Στο γεγονός ότι η συμμετοχή μας στο τουρνουά αποφασίστηκε περίπου 1 ώρα πριν τη διεξαγωγή του καθώς δεν είχαμε φτιάξει έξτρα κώδικα αλλα ρισκάραμε αυτόν της τρίτης εργασίας
2)Εδινα 2 εργαστήρια +2 εργασίες εκεινη την βδομάδα και τη Δευτέρα έγραφα οπότε όπως καταλαβαίνεις δεν είχα και πολυτέλεια χρόνου... :)

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: ThemisMP on February 12, 2009, 03:10:06 am

ΟΜΑΔΑ Α3 (6354_6466)
Διαμαντόπουλος Θεμιστοκλής
Τακούδης Χρήστος

Φτιάξαμε έναν παίκτη που αρχικά υπολόγιζε και αποθήκευε σε μια δομή τύπου MySet0 όλες τις δυνατές κινήσεις του παίκτη για το τελευταίο κομμάτι. Εν συνεχεία, καλούσε τη συνάρτηση Minimax η οποία επέλεγε ποιο κομμάτι θα τοποθετηθεί, όπως θα εξηγηθεί παρακάτω.

Η Συνάρτηση Minimax:
Έπαιζε κάθε δυνατή κίνηση του παίκτη μας σε ένα εικονικό ταμπλό. Κατόπιν ξανακαλούσε τον εαυτό της οπότε και έπαιζε τις κινήσεις του αντιπάλου. Έκανε την παραπάνω διαδικασία για 2 δικές μας κινήσεις και δύο του αντιπάλου, είχε δηλαδή βάθος 4. Χρησιμοποιούσε το κλάδεμα άλφα-βήτα, κάτι που περιόριζε σημαντικά το χρόνο εκτέλεσης. Μετά το τέλος της τελευταίας κίνησης, καλούσε την evaluate με την οποία αξιολογούσε το ταμπλό.

Η Συνάρτηση Evaluate
Δεχόταν ως όρισμα ένα ταμπλό και επέστρεφε τη διαφορά των πιθανών γωνιών μας μείον τις γωνίες του αντιπάλου. Εκτός αυτού είχε κώδικα ο οποίος τσέκαρε ποιο κομμάτι του παίκτη μας παίζεται (με το this.getInventory()) και εάν ήταν από την 3η εώς την 6η κίνηση έστελνε μια πολύ θετική αξιολόγηση για τα τοποθετημένα στο κέντρο κομμάτια.

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

Ως γενικότερο σχόλιο, το τουρνουά ήταν καλή φάση, και θα άξιζε να υπήρχε μεγαλύτερη προσέλευση!!!

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: manos88 on February 14, 2009, 00:20:27 am

ΟΜΑΔΑ 22(δηλώσεων)

Πλατανάκης Εμμανουήλ(6442)
Ναί Νικόλαος(6417)

Βήμα 1:

Σκανάρεται το inventory του computer-player από το τέλος προς την αρχή μέχρις ότου βρεθεί
ένα κομμάτι για το οποίο ο παίκτης έχει διαθέσιμη κίνηση. Μόλις βρεθεί αυτό το κομμάτι
προσμετράται ο αριθμός των χρωματισμένων τετραγώνων του .Στη συνέχεια βρίσκουμε και
τα άλλα κομμάτια που έχουν τον ίδιο αριθμό χρωματισμένων τετραγώνων και που έχουν
βέβαια έγκυρη κίνηση.

Βήμα 2:

Για κάθε έγκυρο κομμάτι που βρίσκουμε με την παραπάνω μεθοδολογία δημιουργούμε ένα
virtual δέντρο. Το virtual αυτό δέντρο υλοποιείται με τη βοήθεια της αναδρομής. Δηλαδή
τοποθετείται το συγκεκριμένο κομμάτι σε ένα κλώνο του board και για τον κλώνο αυτό
βρίσκονται όλες οι έγκυρες κινήσεις του αντιπάλου. Τώρα κάθε κίνηση του αντιπάλου
τοποθετείται στον αρχικό κλώνο και η μελέτη συνεχίζει για καθένα από τα board που
προκύπτουν ανάλογα με την κίνηση του αντιπάλου. Και ούτω κάθε εξής μέχρις ότου φτάσω
στο επιθυμητό βάθος.

Βήμα 3:

Μόλις γίνει αυτό εφαρμόζουμε τον αλγόριθμο minmax από κάτω προς τα πάνω στο
προκύπτον δέντρο. Δηλαδή στα επίπεδα που παίζω εγώ βρίσκω ποια κίνηση μεγιστοποιεί τη
συνάρτηση κέρδους και στα επίπεδα που παίζει ο αντίπαλος ποια κίνηση την ελαχιστοποιεί.
Σε κάθε επίπεδο θα έχω ξεχωριστά σύνολα από αδέρφια. Το κάθε σύνολο θα έχει
διαφορετικό πατέρα. Με αυτόν τον τρόπο θα επιλέγω ένα αδέρφο από κάθε σύνολο και θα το
οδηγώ στον πατέρα. Έτσι θα καταλήξω στο αρχικό επίπεδο και θα έχω βρει το κατά εμένα
επακολουθούμενο σύνολο κινήσεων. Έτσι θα έχω βρεί ποια θα είναι η κατάλληλη κίνηση που
πρέπει να κάνω και την κάνω.

Title: Re: [Δομές Δεδομένων] Τουρνουά Blokus - αλγόριθμοι
Post by: vasso on February 14, 2009, 15:53:43 pm

ομάδα Β5
Ηλιακοπούλου 6364 - Καλαϊτζίδου 6369

ο κώδικάς μας ήταν αυτός που ζητήθηκε στην τρίτη εργασία χωρίς προσθήκες (με μία απώλεια για να είναι ταχύτερος)

παρουσιάζουμε αναλυτικά τον αλγόριθμο με τις προσθήκες του:

Εργασία 3η:

Στην τρίτη και τελευταία εργασία (την οποία θα περιγράψουμε αναλυτικά) αναλάβαμε να δημιουργήσουμε έναν ολοκληρωμένο παίκτη blokus (Computer) ο οποίος θα μπορεί να “βλέπει” τις πιθανές κινήσεις του αντιπάλου και να διαλέγει να κάνει την καλύτερη διαθέσιμη από τις κινήσεις του, σε συνάρτηση και με την κίνηση του αντίπαλου παίκτη. Ο παίκτης μας θα είναι σε θέση να νικάει άνετα την τρίτη μορφή παίκτη που εμφανίζεται στην εργασία, τον παίκτη Random ο οποίος διαλέγει και παίζει μια οποιαδήποτε τυχαία κίνηση ενός οποιουδήποτε τυχαίου κομματιού του χωρίς καμία στρατηγική. Χρησιμοποιούμε τον αλγόριθμο min-max ο οποίος είναι ιδιαίτερα διαδεδομένος για ανάλυση παιχνιδιών παρόμοιας φύσης με του blokus. Ιδανικό θα ήταν να μπορούσε ο υπολογιστής μας να αναλύσει όλες τις επόμενες δυνατές κινήσεις, -του αντιπάλου και δικές του- να δημιουργήσει ένα δέντρο παιχνιδιού για αυτές και να διαλέγει την κίνηση η οποία θα τον οδηγήσει είτε σε σίγουρη νίκη, είτε (παίζοντας ενδεχομένως με τον εαυτό του) σε ισοπαλία. Δυστυχώς, οι απαιτήσεις σε μνήμη και χρόνο της παραπάνω στρατηγικής συναγωνίζονται αυτές της ανάλυσης του σκακιού και οι υπολογιστές του σπιτιού μας είναι πολύ... ερασιτέχνες για να κάνουν μια τέτοια δουλειά.

Για τη δημιουργία του δέντρου παιχνιδιού, επιλέξαμε να κάνουμε δύο δικές μας κλάσεις, την Tree και την Node οι οποίες έχουν την εξής δομή:
   η Tree περιέχει μόνο έναν vector από Nodes και τις κατάλληλες συναρτήσεις για προσθήκη στοιχείων, αναζήτηση, έλεγχο αν ο vector είναι άδειος και τέλος μια συνάρτηση που επιστρέφει το μέγεθος του vector.
   η Node περιγράφει έναν κόμβο του δέντρου παιχνιδιού και περιλαμβάνει τις εξής μεταβλητές:
   int Value η οποία θα κρατάει τις τιμές min-max
   boolean [][] Shape η οποία θα περιγράφει το σχήμα του κομματιού της συγκεκριμένης κίνησης
   int x, int y που περιέχουν τις συντεταγμένες του board
   Piece NodePiece που θα κρατάει όλο το κομμάτι και τέλος θα περιλαμβάνει και ένα Tree, το newNode, στο οποίο θα αποθηκεύονται τα παιδιά του κόμβου αυτου.

Επίσης, στην Node περιλαμβάνονται οι κατάλληλες συναρτήσεις για καταχώρηση και επιστροφή    των παραπάνω μεταβλητών, καθώς και οι συναρτήσεις addNode(Node e) για προσθήκη παιδιού    στον κόμβο Node, η size( ) που επιστρέφει το μέγεθος του newNode και η elementAt(int i) που μας δίνει το Node που βρίσκεται στη θέση i του tree newNode.

Ο αλγόριθμος που ζητήθηκε για να υπολογίζει την value κάθε κίνησης είναι ο υπολογισμός της παράστασης

(Τρέχουσες γωνίες μου – Τρέχουσες γωνίες αντιπάλου) – (Αρχικές γωνίες μου – Αρχικές γωνίες αντιπάλου)

Η βασική υλοποίηση του συγκεκριμένου αλγορίθμου γίνεται με τη συνάρτηση evaluate η οποία παίρνοντας σαν όρισμα έναν board, υπολογίζει τη διαφορά: (Διαθέσιμες γωνίες μου – Διαθέσιμες γωνίες Αντιπάλου). Αυτό υλοποιείται σε ένα loop για κάθε παίκτη ξεχωριστά και αν αυτός είναι δικός μας παίκτης προσθέτει το αποτέλεσμα της scanTheBoard(Board,Color) στη μεταβλητή evaluation ενώ αν είναι ο αντίπαλος το αφαιρεί.
Το μεγαλύτερο και δυσκολότερο κομμάτι της τρίτης εργασίας ήταν η τροποποίηση της συνάρτησης getNextMove η οποία για δοσμένο πίνακα, παίζει την επόμενη κίνηση του παίκτη. Για να απλοποιήσουμε τον κώδικά της, γράψαμε μερικές επιπλέον βοηθητικές συναρτήσεις, τις CalculateBoxes( ), ClonePlaceEvaluate( ), findRoot( ), getNextColor( ) και την getFirstMove( ).
Συγκεκριμένα:
Η CalculateBoxes, δίνοντάς της ένα piece υπολογίζει πόσα τετραγωνάκια του έχουν χρώμα (τη χρησιμοποιούμε στον έλεγχο όταν θέλουμε πχ να πάρουμε όλα τα κομμάτια με 5 τετραγωνάκια).
H ClonePlaceEvaluate( ) έχει διπλή λειτουργία. Αν την καλούμε για τον δικό μας παίκτη, κλωνοποιεί τον πίνακα που της δίνουμε, τοποθετεί το κομμάτι στην θέση που της δίνουμε και καλεί την evaluate( ) και επιστρέφει το αποτέλεσμά της.. Αν πάλι την καλούμε για το επόμενο επίπεδο του δέντρου, για την κίνηση δηλαδή του αντιπάλου, κλωνοποιεί πάλι τον πίνακα, τοποθετεί και το δικό μας κομμάτι και του αντιπάλου και καλεί πάλι την evaluate( ) και επιστρέφει το αποτέλεσμά της.
Η findRoot( ) είναι αυτή που υλοποιεί τον max αλγόριθμο και βρίσκει την ρίζα του δέντρου.H συνάρτηση δημιουργεί κάθε φορά ένα καινούρια αντικείμενο Node max το οποίο σαν default τιμή παίρνει τα στοιχεία του πρώτου Node του Myside. Στη συνέχεια για κάθε ένα απο τα Nodes του Myside ελέγχει αν η Value του max είναι μικρότερη της Value του συγκεκριμένου Node και αν ναι,τοποθετεί τα στοιχεία του Νοde στο max.Αφου τελειώσει τον έλεγχο επιστρέφει το max που βρήκε.
H getNextColor( )επιστρέφει μια ακέραια τιμή η οποία αν χρησιμοποιηθεί ως δείκτης στην εντολή players.elementAt(index) μας δίνει τον αντίπαλο παίκτη, δίνοντας προσοχή στην περίπτωση που ο αμέσως επόμενος παίκτης είναι dead. Τότε, η getNextColor( ) επιστρέφει το άλλο χρώμα του αντίπαλου.
Τέλος, η getFirstMove( ), παίζει τις πρώτες 4 κινήσεις του παίκτη μας, καθώς έτσι αποφασίσαμε να λύσουμε το πρόβλημα που προέκυψε στην αρχή, οπότε και κάθε μια από τις πρώτες κινήσεις του παίκτη μας χρειαζόταν υπερβολικό χρόνο για να υπολογιστεί και να παιχτεί. Οι κινήσεις αυτές είναι προεπιλεγμένες από εμάς και τοποθετούνται συγκεκριμένα κομμάτια αυτόματα σε συγκεκριμένες θέσεις. Έτσι, όταν ο υπολογιστής κληθεί να αναλύσει τις διαθέσιμες κινήσεις των μεγαλύτερων κομματιών του, θα μειωθεί ο αριθμός κομματιών που θα επεξεργαστούν οι συναρτήσεις μας και προφανώς θα μειωθεί και ο χρόνος και η απαίτηση σε μνήμη του προγράμματος. Επίσης, με βάση την εμπειρία μας ως παίκτες του συγκεκριμένου παιχνιδιού πιστεύουμε ότι οι πρώτες κινήσεις που επιβάλλουμε στον παίκτη μας είναι στρατηγικά ορθές και τον οδηγούν σε ευκολότερη νίκη.

Πέραν των βοηθητικών συναρτήσεων, ένα μεγάλο τμήμα κώδικα βρίσκεται μέσα στην ίδια την getNextMove( ). Αγνοήσαμε το κομμάτι που δεν αναφερόταν σε παίκτη τύπου Computer και στη συνέχεια, ακολουθώντας τον ψευδοκώδικα που δόθηκε στην εκφώνηση της εργασίας ακολουθήσαμε τα εξής βήματα:
-Δημιουργούμε το δέντρο του παιχνιδιού με το όνομα MySide και τη ρίζα του (ως Node) με όνομα root.
-Yπολογίσαμε τις αρχικές γωνίες μας και του αντιπάλου χρησιμοποιώντας ως όρισμα το χρώμα του activePlayer. Συκεκριμένα, αν το χρώμα του είναι blue ή red, προσθέτει το μέγεθος των scanTheBoard() αν κληθούν για τα δύο αυτά χρώματα και το αποθηκεύει στη μεταβλητή arxikesMoy και αντίστοιχα τις καλεί για τα άλλα δύο, τις προσθέτει και αποθηκεύει το αποτέλεσμα στη μεταβλητή arxikesToy. Αντίστοιχα, αν τα δίκά μου χρώματα είναι το yellow και το green, τα καλεί και τα αποθηκεύει ανάποδα. Τέλος, αποθηκεύουμε τη διαφορά τους σε μία μεταβλητή arxikes.
-Επιλέγουμε από το inventory ένα από τα μεγαλύτερα κομμάτια. Όπως προείπαμε, για τις 4 πρώτες κινήσεις, δεν θα τρέξει ο κανονικός κώδικας επιλογής κίνησης αλλά ένας ειδικός κώδικας που περιγράφεται στην getFirstMove( ). Αν βρισκόμαστε σε μια από τις επόμενες κινήσεις, μπαίνουμε σε μία επανάληψη τύπου do... while για να καλύψουμε την περίπτωση που τα μεγαλύτερα κομμάτια μας δεν έχουν κινήσεις και θελήσουμε να διαλέξουμε κάποιο κομμάτι με λιγότερα κουτάκια. Τότε, δημιουργούμε ένα κομμάτι temp, στο οποίο περνάμε το τελευταίο κομμάτι του inventory. Με την CalculateBoxes( ) υπολογίζουμε τον αριθμό τετραγώνων του και μέσα σε ένα while βρίσκουμε το πρώτο σε σειρά κομμάτι του inventory που έχει ίδιο ή μεγαλύτερο αριθμό τετραγώνων με το κομμάτι temp. Τη θέση του κομματιού αυτού στο inventory την κρατάω στην μεταβλητή LastSameSize.
-Βρίσκουμε όλες τις δυνατές κινήσεις για καθένα από τα κομμάτια του inventory που βρίσκονται από τη θέση LastSameSize ως το τέλος. Δημιουργούμε ένα MySet6364_6369 Moves και του δίνουμε το αποτέλεσμα της scanTheBoard. Στη συνέχεια, αν το LastSameSize δείχνει στο τέλος του inventory, δηλαδή έχουμε μόνο 1 μεγάλο κομμάτι για τοποθέτηση, φτιάχνουμε ακόμη ένα MySet6364_6369 Places αυτή τη φορά, του δίνουμε το αποτέλεσμα της findwhereItFits. Υπολογίζουμε για κάθε στοιχείο της places μέσω της ClonePlaceEvaluate τις τρέχουσες γωνίες, και τη διαφορά τους με τις αρχικές. Το αποτέλεσμα, μαζί με τα στοιχεία της κάθε κίνησης (Shape, Piece, Χ, Υ) τα αποθηκεύουμε σε ένα καινούριο Node που δημιουργούμε, το οποίο προσθέτουμε στο MySide.
Αν όμως, τα μεγάλα κομμάτια είναι περισσότερα από ένα, φτίαχνουμε έναν Vector, τον SelectedPiece στον οποίο περνάμε όλα τα κομμάτια που βρίσκονται στο inventory από τη θέση LastSameSize μέχρι και το τέλος του και έχουν δυνατές κινήσεις
(findWhereItFits(b,inventory.elementAt(LastSameSize+i).clone( ),Moves)!=null)

Για την places του κάθε κομματιού ξεχωριστά, φτιάξαμε ένα loop που κάνει ακριβώς το ίδιο με την προηγούμενη περίπτωση που είχαμε ένα μόνο κομμάτι, δηλαδή υπολογίζουμε για κάθε στοιχείο της places μέσω της ClonePlaceEvaluate τις τρέχουσες γωνίες, και τη διαφορά τους με τις αρχικές. Το αποτέλεσμα, μαζί με τα στοιχεία της κάθε κίνησης (Shape, Piece, Χ, Υ) τα αποθηκεύουμε σε ένα καινούριο Node που δημιουργούμε, το οποίο προσθέτουμε στο MySide.
Στο σημείο αυτό αυξάνουμε τη βοηθητική μεταβλητή abc και κλείνουμε το do βάζοντας στο while τον έλεγχο while(Myside.size( )==0). Αν δηλαδή, δεν έχω κινήσεις με τα μεγαλύτερα κομμάτια, θα ξαναγυρίσω στην αρχή και θα πάρω την ομάδα κομματιών με ένα λιγότερο box (αυτό το επιτυγχάνω αφαιρώντας από τα κουτάκια του μεγαλύτερου κομματιού την abc).

Αν η MySide έχει κινήσεις, προχωράμε σε αναζήτηση των κινήσεων του αντιπάλου. Καλώντας την getNextColor() παίρνουμε τον αντίπαλο παίκτη-αν η συνάρτηση επιστρέψει 4 (default τιμή της int color ) σημαίνει πως και οι δύο αντίπαλοι είναι dead.
-Αν κάτι τέτοιο δεν συμβαίνει ,όπως και για τον δικό μας παίκτη ,βρίσκουμε την ομάδα των μεγαλύτερων κομματιών (πεντάρια,τεσσαρια....κτλ )χρησιμοποιώντας το δείκτη LastSameSize και τη συνάρτηση CalculateBoxes( ) με αντίστοιχο τρόπο που εφαρμόσαμε για τον δικό μας παίκτη. Στη συνέχεια για κάθε ένα απο τα κομμάτια του δικού μου παίκτη που έχω καταχωρήσει στο δέντρο Myside κάνω την επανάληψη do..while ώστε σε περίπτωση που η ομάδα των κομματιών του inventory του αντιπάλου μου δεν έχει κινήσεις να προβλέψω τις πιθανές κινήσεις των κομματιών της αμέσως μικρότερης ομάδας.(Γιαυτό και στο while η συνθήκη έιναι Myside.elementAt(index).size( )==0 αυξάνοντας το abc_2 καθε φορά).
-Όμοια με πάνω (δικός μας παίκτης) είτε έχει μείνει μονο ένα μεγαλο κομμάτι είτε πολλά μπαίνουμε στο αντίστοιχο loop και αν η findWhereItFits δεν επιστρέφει null δημιουργούμε ένα αντικείμενο Myset6364_6369 places όπου αποθηκεύουμε τις δυνατες κινήσεις του κάθε κομματιού του αντιπάλου.Θετουμε στην Value του δικού μας κομματιού μία default τιμή 1000.Για κάθε μία απο τις κινήσεις της places καλούμε την ClonePlaceEvaluate και αν βρει result με μικρότερη τιμή απο την Value τοποθετει την Value, το Piece,το Shape και τα X, Y του κομματιού στο Myside.elementAt(index).Με τον τρόπο αυτό βρίσκουμε την κίνηση min από τις κινήσεις του αντιπάλου.
-Εχοντας συμπληρώσει πλέον το δέντρο καλούμε τη συνάρτηση findroot(Tree) με την οποία βρίσκουμε τη ρίζα του.Για το Piece που αντιστοιχεί στη ρίζα και για την συγκεκριμένη κίνηση του παίρνω τα x,y και το shape του και με τη συνάρτηση place(Piece,Shape,int) του Board τοποθετώ το κομμάτι στο ταμπλώ.
-Σε περίπτωση που και οι δύο αντίπαλοι είναι dead παρακάμπτει όλο το παραπάνω κομμάτι που αντιστοιχεί στον αντίπαλο και μπαίνουμε σε ένα else το οποίο καλεί τη findroot(Tree) με κόμβους μόνο για τον δικό μου παίκτη και επειτα με το αποτέλεσμα που επιστρέφει τοποθετεί το κομμάτι στο ταμπλώ .Τέλος και στις δύο περιπτώσεις μετα την τοποθέτηση με την place(Piece,Shape,int) θέτουμε movePlayed=true ώστε να δηλώσουμε πως έχουμε κάνει την κινησή μας.

THMMY.gr

Μαθήματα Βασικού Κύκλου => Δομές Δεδομένων => Topic started by: Wade on February 06, 2009, 01:42:11 am