Vier Gewinnt

Dummie

Hallo,
ich hab eben schonmal im IRC Channel gefragt,
jedoch bin ich mir sicher das es eine viel effektivere Lösung gibt...

Das Problem ist: Ich möchte gerne überprüfen, ob jemand das Spiel Gewonnen hat ( 4 in einer Reihe ) und zwar entweder Senkrecht, Waagerecht oder Diagonal.

Daher suche ich nun nach einer effektiven Lösung dafür folgendes habe ich probiert:

//HatSpielerGewonnen( FeldTyp Spieler )
	bool GleicherStein = false;

		for (int i = 1; i < 5; i++)
		{
			if ( LetzerZug.Spalte+i > SPIELFELD_SPALTEN || LetzerZug.Spalte+i > SPIELFELD_ZEILEN && LetzerZug.Spalte-i < 0 || LetzerZug.Spalte-i < 0 )
				break;

			if ( SpielFeld[LetzerZug.Spalte+i][LetzerZug.Zeile].Typ == Spieler )
				GleicherStein = true;
			else if ( SpielFeld[LetzerZug.Spalte][LetzerZug.Zeile+i].Typ == Spieler )
				GleicherStein = true;
			else if ( SpielFeld[LetzerZug.Spalte+i][LetzerZug.Zeile+i].Typ == Spieler )
				GleicherStein = true;

			if ( SpielFeld[LetzerZug.Spalte-i][LetzerZug.Zeile].Typ == Spieler )
				GleicherStein = true;
			else if ( SpielFeld[LetzerZug.Spalte][LetzerZug.Zeile-i].Typ == Spieler )
				GleicherStein = true;
			else if ( SpielFeld[LetzerZug.Spalte-i][LetzerZug.Zeile-i].Typ == Spieler )
				GleicherStein = true;
			if (!GleicherStein)
				break;
		}
	if (GleicherStein)
		return true;

Das klappt jedoch nicht so gut Waagerecht klappt, aber Diagonal nicht und den Rest habe ich erst garnicht mehr probieren wollen...
Es macht mir extreme Probleme einen Algro dafür zu schreiben

Hat jemand sowas vielleicht schonmal gemacht?

Und gleich nochwas: Wenn ich bei der KI bin würde ich gerne eine besiegbare, aber dennoch nicht so schlecht spielende KI programmieren wie könnte man das so programmieren das der PC jemand garkeine Chance lässt zu gewinnen ich hab gegen den PC mit glück gerade mal ein Unentschieden geschafft ( in einem anderen PC ) das wurde wohl mit dem Alpha-Beta Algro gemacht.

Hoffe jemand liest sich das alles durch

Gruß

EDIT: Ich hab das Forum Design geschrottet oO

volkard

geh von x/y des letzten zugs aus und merke dir die steinfarbe. von da aus geh in eine himmelsrichtung solange die steinfarbe gleich bleibt. dann geh in die gegenhimmelsrichtung solange die steinfarbe gleich bleibt. haste zusammen mehr als 2 schritte machen dürfen, hat der letze zug gewonnen. mach das mit den himmelrichtungspaaren O-W, NO-SW, NW-SO und mit der solo-himmelrichtung S.
im kern steht dann ne leckere "schleife"

//alles ungetestet
int wieWeitNoch(int aktuelleFarbe,int x,int y,int dx,int dy){
   //oh, gar keine schleife, irgendwie war es mir danach, das mal so zu machen. 
   x+=dx;
   y+=dy;
   if(feld[y][x]!=aktuelleFarbe) return 0;
   x+=dx;
   y+=dy;
   if(feld[y][x]!=aktuelleFarbe) return 1;
   x+=dx;
   y+=dy;
   if(feld[y][x]!=aktuelleFarbe) return 2;
   return 3;
}

aufrufen muss man das noch klug.

bool hatGewonnenNOSW(int aktuelleFarbe,int x,int y){
   return wieWeitNoch(aktuelleFarbe,x,y,1,1)+wieWeitNoch(aktuelleFarbe,x,y,-1,-1)>2;
}
bool hatGewonnenNWSO(int aktuelleFarbe,int x,int y){
   return wieWeitNoch(aktuelleFarbe,x,y,1,-1)+wieWeitNoch(aktuelleFarbe,x,y,-1,1)>2;
}
bool hatGewonnenOW(int aktuelleFarbe,int x,int y){
   return wieWeitNoch(aktuelleFarbe,x,y,1,0)+wieWeitNoch(aktuelleFarbe,x,y,-1,0)>2;
}
bool hatGewonnenS(int aktuelleFarbe,int x,int y){
   return wieWeitNoch(aktuelleFarbe,x,y,0,-1)>2;
}

und zusammen

bool hatGewonnen(int aktuelleFarbe,int x,int y){
   if(hatGwonnenOW(aktuelleFarbe,x,y)) return true;
   if(hatGwonnenNOSW(aktuelleFarbe,x,y)) return true;
   if(hatGwonnenNWSO(aktuelleFarbe,x,y)) return true;
   if(hatGwonnenS(aktuelleFarbe,x,y)) return true;
   return false;
}

dazu mach noch nen "todesrand", also mach dein array größer, als es eigentlich sein müßte, mach drumherum einen rand und leg auf den rand blaue spielsteine. dadurch terminiert die "schleife" sicher, sobald sie auf den rand läuft, und dur brauchst nicht das dauernde überprüfen, ob du noch drin bist (weil das schrecklich viel zeit kostet).

Es macht mir extreme Probleme einen Algro dafür zu schreiben

bitte schreib "algo".

wie könnte man das so programmieren das der PC jemand garkeine Chance lässt zu gewinnen

mit minmax-algo (klar, abwandlungen wie negamax). braucht aber viel rechenzeit. mußt ihn schon ne stunde oder so rechnen lassen, damit er was nicht extrem-dummes macht. stark wird er dann erst, weil du ihm tricks einbaust.
zunächst mal die bewertungsfunktion. bei sieg gibste 1000 punkte bei nix-wissen 0. kannst aber auch fummeln und bei nichtwissen sagen wir mal für jeden zentrumsstein 3 punkte und für jeden fast-zentrumsstein 2 punkte geben. oder gleich für jeden stein gibste so viele punkte, wie er möglichkeiten hat, teil einer vierer-reihe zu sein. nur weiß kein mensch, ob das sinnvoll ist. hier liegt es an die, rumzuprobieren und eine gute heuristik zu finden.
seine klugheit kann mit einer datei gespeichert werden, in der er stellungen speichert, von denen er mit minmax festgestellt hat, welchen genauen wert sie haben. wenn er innerhalb von minmax dann nicht nur deine lustige heuristik nimmt, sondern manchmal auch in die datei gucken darf, kann er in spärteren spielen fallen früher erkennen. aber obacht, auch hart gepackt wäre so eine datei 40M groß und es dauert vielleicht jahre, bis sie voll ist (aber dann spiel der kumpel optimal).
suchwörter:

"expert play in connect 4"
sollte dich zu 4-gewinnt-strategie führen (ist aber nur für menschen, dem rechner das beizubringen, ist wohl eher was für größenwahnsinnige).

und

"killer-heuristik"
sollte zu seiten über schach-programmierung führen, da kannste enorm viel abgucken.

Dummie

Vielen Dank volkard...

Deine gute und ausführliche Hilfestellung hat mir sehr bei dem oben genannten Problem geholfen...

Allerdings habe ich durch meine extrem schlechte Satzstellung und Zeichensetzung ( War gerade im Stress ) ein Missverständnis erzeugt.

Und zwar bei der KI: Ich wollte einen gut spielenden PC, jedoch sollte dieser noch besiegbar sein und ab und zu Chancen offen lassen...

Das ist aber erstmal nur Nebensächlich

Auf Jedenfall, hat mir das sehr geholfen!

Gruß

Konfusius

hach! das vier-gewinnt-programm erinnert mich an meine anfängerzeit.

Dummie schrieb:

Ich wollte einen gut spielenden PC, jedoch sollte dieser noch besiegbar sein und ab und zu Chancen offen lassen...

du kannst zb jeden vierten oder sechsten zug zufällig wählen.

das hauptproblem ist aber die bekannte vier-gewinnt-eröffnungsfalle, bei der der erste stein in die mitte gesetzt wird. setzt der gegner seinen stein nicht unmittelbar daneben, dann hat er schon verloren. damit der computer das erkennt, braucht er eine suchtiefe von mindestens sechs halbzügen. das ist aber schon ziemlich stark. also entweder spielt das programm ziemlich stark oder es versagt bereits zu beginn des spiels kläglich.

die lösung ist eine "eröffnungsbibliothek", die diese eröffnungsfalle erkennt und darauf reagiert. dann braucht es keine so hohe suchtiefe mehr.

volkard

Dummie schrieb:

Allerdings habe ich durch meine extrem schlechte Satzstellung und Zeichensetzung ( War gerade im Stress ) ein Missverständnis erzeugt.

Und zwar bei der KI: Ich wollte einen gut spielenden PC, jedoch sollte dieser noch besiegbar sein und ab und zu Chancen offen lassen...

hatte ich erwähnt, daß es sauschwierig wird, einen bot zu bauen, der dich schlägt, und du durchaus auch damit rechnen darfst, das nicht zu schaffen? falls nicht, sei es hiermit geschehen. aber das macht die aufgabe nur umso spannender.