Vier gewinnt - auf "gewinnt" überprüfen

[Kantholy]

Moinmoin Leute, ich hab mal wieder ein "Problem" der etwas anderen Art, und zwar will ich ein vier gewinnt programmieren, das funktioniert soweit schonmal ganz gut dass ich Steine usw. setzen kann, nur was mir bisjetzt fehlt ist ganz einfach ein "Gewinnmechanismus", will heißen, ich muss meinen 2 dimensionalen Array ja irgentwie überprüfen ob 4 steine der selben Farbe zusammenhängen...

Im Moment ist mein 2 dimensionaler Array so aufgebaut, das "0,1,2" drinsteht, 0 für ein leeres Feld, bzw. 1 oder 2 für eben Spieler 1/2, das heißt man müsste ja per Schleife 2 mal den kompletten Array durchgehen und auf 4 "aneinanderhängende" gleiche Zahlen überprüfen, solange diese waagerecht bzw. senkrecht stehen sollte das ja kein Problem sein, das müsste ich hinbekommen, ABER:

Wie zur Hölle kann ich in diesem 7x6 Feld auf 4 diagonal zusammenhängende Zahlen überprüfen, und das sowohl von links nach rechts als auch von rechts nach links...

Irgentwie fehlt mit da das Konzept wie ich das machen soll, hat jemand irgentwelche Vorschläge?

 

[Darii]

Diagonalelemente kriegst du mit (x±1, y±1) bzw mit (x±1, y∓1). Das Vorgehen ist sonst genauso wie bei Waagerechten.

 

[Kantholy]

oha, kannst du das mal für noobs erklären? Check ich grad übelst nicht..

 

[Darii]

Ohne mich zu weit aus dem Fenster lehnen zu wollen. Geraden sind Mathe 7. Klasse? Und nichts anderes sind deine Diagonalen: Geraden der Steigung ±1.

 

[joe67]

Ich würde an deiner Stelle gar nicht das gesamte Array durchprüfen, sondern lediglich, ob der zuletzt gespielte Stein eine Vierergruppe bildet.

j o e

 

[Kantholy]

naja, ich habs dann doch bissl anders gelöst, alter falter, das war ein Aufwand...

hier mal meine Version, für all diejenigen unter euch die es vllt. interessiert

while(player < 2 && !winner)
{
	player++;
	//Vertikal Überprüfen
	//Reihen
	for(startX = 0; startX < 7; startX++)
	{
		//Spalten
		for(startY  = 0; startY < 3; startY++)
		{
			
			if(	spielfeld[startX][startY][0] == player &&
				spielfeld[startX][startY+1][0] == player &&
				spielfeld[startX][startY+2][0] == player &&
				spielfeld[startX][startY+3][0] == player)
			{
				winner = player;
			}
		}
	}
	
	//wenn kein Gewinner vertikal gefunden wurde, mach weiter
	if(!winner)
	{	//Reihen
		for(startX = 0; startX < 4; startX++)
		{
			//Spalten
			for(startY  = 0; startY < 6; startY++)
			{
				
				if(	spielfeld[startX][startY][0] == player &&
					spielfeld[startX+1][startY][0] == player &&
					spielfeld[startX+2][startY][0] == player &&
					spielfeld[startX+3][startY][0] == player)
				{
					winner = player;
				}
			}
		}
	}
	//wenn weder vertikal noch horizontal ein Gewinner gefunden wurde...
	//probiers kompliziert - diagonal, ioda!
	if(!winner)
	{	
		//von unten nach oben
		for(startX = 0; startX < 4; startX++)
		{
			//Spalten
			for(startY  = 0; startY < 3; startY++)
			{
				
				if(	spielfeld[startX][startY][0] == player &&
					spielfeld[startX+1][startY+1][0] == player &&
					spielfeld[startX+2][startY+2][0] == player &&
					spielfeld[startX+3][startY+3][0] == player)
				{
					winner = player;
				}
			}
		}
		
		//von oben nach unten
		for(startX = 0; startX < 4; startX++)
		{
			//Spalten
			for(startY  = 3; startY < 6; startY++)
			{
				if(	spielfeld[startX][startY][0] == player &&
					spielfeld[startX+1][startY-1][0] == player &&
					spielfeld[startX+2][startY-2][0] == player &&
					spielfeld[startX+3][startY-3][0] == player)
				{
					winner = player;
				}
			}
		}
	}
}

 

[efcoyote]

Die Aufgabe hat mich interessiert und ich hatte etwas Zeit daher mal meine Lösung. Sie faßt den Ansatz von joe67 auf und funktioniert rekursiv. Geprüft wird, ob der zuletzt gesetzte Stein (an Stelle x, y) einen Viererkette bildet. Ohne Kommentare sind es 9 Zeilen.

    static bool checkWin(int x, int y, int player) {

      // Addieren in horizontaler, vertikaler, diagonal (links-oben, rechts-unten), diagonal (links-unten, rechts-oben) Richtung
      // wenn Summe >= 3 (+ aktuelles Kästchen = 4) dann Sieg

      return countCells(x - 1, y, -1, 0, player) + countCells(x + 1, y, 1, 0, player) >= 3 ||
        countCells(x, y - 1, 0, -1, player) + countCells(x, y + 1, 0, 1, player) >= 3 ||
        countCells(x - 1, y - 1, -1, -1, player) + countCells(x + 1, y + 1, 1, 1, player) >= 3 ||
        countCells(x - 1, y + 1, -1, 1, player) + countCells(x + 1, y - 1, 1, -1, player) >= 3;
    }


    // aktuelle x,y-Position, x,y-Richtung in die gesucht wird, Spielernummer
    static int countCells(int x, int y, int xdir, int ydir, int player) {

      // noch innerhalb des Feldes?
      if (x >= 0 && x < maxx && y >= 0 && y < maxy) {

        // wenn gleiche Farbe wie Spieler, dann eins addieren und in gleiche Richtung weitersuchen
        if (field[x, y] == player) return countCells(x + xdir, y + ydir, xdir, ydir, player) + 1;
      }

      // außerhalb oder andere Farbe
      return 0;
    }

 

[Gluehwurm]

Die wahrscheinlich schnellste Methode ist für jedes Feld 4 Zähler, horizontal, vertikal und 2*diagonal mitzuführen, und bei einem neuen Stein alle Zähler des Feldes anhand der Nachbar-Felder zu erhöhen. Siegbedingung ist dann erfüllt, wenn ein Zähler gleich 4 ist.

Nachteil: Zusätzlicher Speicher für 4 Zähler
Vorteil: Einfach, leicht erweiterbar für ein "N gewinnt"

Interessant könnte dann auch eine effiziente Umsetzung sein, denn man muss nicht für alle Felder 4 Zähler mitschleppen...

[edit]
2*Diagonal
[/edit]

 

[Kantholy]

möglich wäre es, aber das würde ja noch mehr Rechenaufwand ergeben als ich jetzt schon hab



PS: meine Variante is Javascript für all denen die es noch nicht aufgefallen ist - clientseitiges rechnen ftw

 

[msschubi]

Hi,
auch wenn der Thread hier schon echt alt ist, so habe ich ihn doch über Google gefunden und er hat mir weitergeholfen. Deswegen ergänze ich ihn um meine Lösung.

@pvc-junkie
Mir hat deine Lösung echt gut gefallen, total elegant und leicht verständlich. Ich dachte zunächst, dass meine Lösung schneller ist als deine, was ja zumindest dann notwendig ist, wenn man eine KI mit Alpha-Beta Cutoff bauen möchte... musste dann aber feststellen, dass beide Lösungen ungefähr gleichschnell sind.

Hier zunächst mal meine Lösung (geschrieben in Swift):

    enum Chip {
        case blue
        case white
        case empty
    }
    
    enum Direction{
        case column
        case row
        case diagonalTopLeftBottomRight
        case diagonalBottomLeftTopRight
    }
    
    //spielfeld[row][column] = spielfeld[y][x]
    var playingField : [[Chip]]

/*
... weiterer Code ...
*/
func isTurnAWin(player: Chip, x: Int, y: Int) -> Bool {
        //check in all directions
        if(isBinaryPrintAWin(binaryPrintOfRow(Direction.row, x: x, y: y, player: player))) {
            return true
        }
        if(isBinaryPrintAWin(binaryPrintOfRow(Direction.column, x: x, y: y, player: player))) {
            return true
        }
        if(isBinaryPrintAWin(binaryPrintOfRow(Direction.diagonalBottomLeftTopRight, x: x, y: y, player: player))) {
            return true
        }
        if(isBinaryPrintAWin(binaryPrintOfRow(Direction.diagonalTopLeftBottomRight, x: x, y: y, player: player))) {
            return true
        }
        return false
    }
    

    func binaryPrintOfRow(direction: Direction, x: Int, y: Int, player: Chip)->Int {
        var binary: Int = 0
        if(direction == Direction.row) {
            for var pot=0; pot<=6; pot+=1 {
                if(playingField[y][pot] == player) {
                    binary += 1 << pot
                }
            }
        } else if(direction == Direction.column) {
            for var pot=0; pot<=5; pot+=1 {
                if(playingField[pot][x] == player) {
                    binary += 1 << pot
                }
            }
        } else if(direction == Direction.diagonalBottomLeftTopRight) {
            //bottom-left point (either min(x) = 0 or max(y) = 5)
            let minGradient = min(x,y)
            let minX = x - minGradient
            let minY = y - minGradient
            
            var currentX = minX
            var currentY = minY
            
            //counting cells from bottom-left to top-right
            for var pot = 0; (currentX <= 6) && (currentY <= 5); pot+=1 {
                if(playingField[currentY][currentX] == player) {
                    binary += 1 << pot
                }
                currentX += 1
                currentY += 1
            }
            
        } else if(direction == Direction.diagonalTopLeftBottomRight) {
            //bottom-right point (either max(x) = 6 or min(y) = 0)
            let minGradient = min(6-x,y)
            let maxX = x + minGradient
            let minY = y - minGradient
            
            var currentX = maxX
            var currentY = minY
            
            //counting cells from bottom-right to top-left
            for var pot = 0; (currentX >= 0) && (currentY <= 5); pot+=1 {
                if(playingField[currentY][currentX] == player) {
                    binary += 1 << pot
                }
                currentY += 1
                currentX -= 1
            }
        }
        return binary
    }
    
    func isBinaryPrintAWin(binary: Int) -> Bool {
        
        if(binary & 15 == 15 || binary & 30 == 30 || binary & 60 == 60 || binary & 120 == 120) {
            return true
        }
        return false
    }

Idee dahinter: aktuelle Zeile, Spalte, Diagonalen der Position des Chips durchgehen.
Trifft man bei einem Durchgang auf einen Spielstein des aktuellen Spielers, wird die Position des Spielsteins als Potenz der Zahl 2 genutzt und zu der Variable "binary" addiert. Später kann dann diese Variable mittels logischem Operator "gesiebt" werden und geschaut werden, ob eine Zahl zustande kommt, die 4 nebeneinanderstehende 1en in der Binärdarstellung der Variable "binary" entsprechen.

Beispiel:

Reihe: blue blue blue blue empty empty empty
Für jedes Blue (Big Endian, Little Endian ... spielt keine Rolle) wird eine 1 in Binärdarstellung gesichert, also sieht die Variable "binary" in Binärdarstellung z.B. so aus:
binary_2 = 1111000
binary_10 = 120

für die Reihe: blue blue blue blue empty empty blue
ergibt sich
binary_2 = 1111001
binary_10 = 121

Anschließend wird gesiebt bzw. ein Pattern drüber gelegt (Methode: isBinaryAWin):

120 & 120 = 120
121 & 120 = 120

Danach wird geschaut, ob die Zahl entweder 15, 30, 60, 120 ist. Ist dies der Fall, so hat man 4 nebeneinanderliegende Spielsteine gefunden und kann true zurückgeben.

Einzige Schwierigkeit: Die Diagonalen brauchen etwas mehr aufwand ... Man muss die Grenzen herausfinden. Ansonsten musste ich, wie gesagt, leider feststellen, dass die Rekursive Lösung übersichtlicher, eleganter und gleich schnell ist

Eventuell findet ja wer noch 2-3 Verbesserungen an meiner Lösung und kann sie verbessern?

Grüße

 

[Ruffyg]

Hey, das Thema ist sehr alt jedoch benötige ich Hilfe bei meinem Spiel. Ich programmiere 4Gewinnt in React und habe es so gut wie fertig. Ich benötige nur noch die diagonale Gewinnprüfung. Diese funktioniert auch bereits in eine Richtung, jedoch finde ich den Fehler für die andere Richtung nicht. Es wäre toll wenn mir jemand helfen kann.

ermittleGewinnerDiagonal() {
    let startX = 0;
    let startY = 0;
        
        //von oben nach unten
        for(startX = 0; startX < this.props.Zeilen; startX++)
        {
            //Spalten
            for(startY  = 3; startY < this.props.Spalten; startY++)
            {
        let aktuWert = this.state.grossesArray[startX][startY];
                if(aktuWert != null && (
        (
          startX + 3 < this.props.Spalten &&    startY - 3 < this.props.Zeilen &&
          this.state.grossesArray[startX][startY] === aktuWert &&
                    this.state.grossesArray[startX+1][startY-1] === aktuWert &&
                    this.state.grossesArray[startX+2][startY-2] === aktuWert &&
          this.state.grossesArray[startX+3][startY-3] === aktuWert
        ) || (
          startX + 3 < this.props.Spalten &&    startY + 3 > this.props.Zeilen &&
          this.state.grossesArray[startX][startY] === aktuWert &&
                  this.state.grossesArray[startX+1][startY+1] === aktuWert &&
                    this.state.grossesArray[startX+2][startY+2] === aktuWert &&
          this.state.grossesArray[startX+3][startY+3] === aktuWert
        ))
        ) {
          return 'Der Gewinner ist ' + (aktuWert ? this.state.name1 : this.state.name2) + '!';
                }
      }
    }
    return null;
  }

"Der Gewinner ist" wird ausgegeben wenn eine vierer Kette von links unten nach rechts oben ensteht. Aber nicht wenn man von links oben nach rechts unten eine vierer Kette bildet.

 

[efcoyote]

Eventuell:
startX + 3 < this.props.Spalten && startY + 3 < this.props.Zeilen &&

 

[GustlPC]

Schau mal hier, ist zwar in c, aber vielleicht hilft es ja

https://trainyourprogrammer.de/c-A30-L1-4-gewinnt-fuer-die-konsole.html