Schachbrett

[Mister Fabulous]

Hallo,

folgende Ausgangslage: Ich möchte einen Schachcomputer proggen. Das Problem bezieht sich hier erstal nur auf das Brett. Ich habe eine Klasse Spiel und eine Klasse Feld. Die Klasse Feld hat die Instanzdatenfelder xKoordinate, yKoordinate und (boolean) belegt (belegt gibt an, ob eine Figur draufsteht). Ein Schachbrett hat bekanntermaßen 8x8 = 64 Felder. Nun liegt es nahe, eine Sammlung in Spiel anzulegen, um dort die Felder zur speichern. Doch was für eine Sammlung? Schlicht und einfach ein Array mit 64 Datenfeldern? Würde das nicht den Zugriff erschweren und die eigentliche Kood des Feldes in den Hintergrund rücken? Allerdings wüsste ich keine Möglichkeit, die besser wäre.

Wisst ihr eine?

MfG Mister Fabulous

 

[mvitz]

2 Dimensionals Array

 

[Mister Fabulous]

Oha,

der Java-Standard müsste mal wieder erweitert werden, ne?

Noch ernste Vorschläge?

 

[Marco13]

Die Frage nach ernst gemeinten Vorschlägen wirkt ein bißchen grotesk, wenn eine Frage nach einer ernst gemeinten Frage eher gerechtfertigt wäre. Was bringt eine Collection mit booleans? Abgesehen davon, dass es schrecklich ineffizient und unhandlich und ein totaler Overkill ist (weil sich die Größe eines Schachbrettes während des Spiels nun mal so schrecklich selten ändert).

Wie für viele 2-Spieler-Spiele (für die man eine Engine schreiben will) muss ein Schachbrett nicht viel können:

interface Board
{
    int getWidth();
    int getHeight();
    Piece get(int x, int y);
    void applyMove(Move move);
    void undoMove(Move move);
}

Intern kann das ganze dann mit einem
private Piece pieces[][] = new Piece[8][8];
gemacht werden (ja, ein 2D-Array!)
oder meinetwegen, wenn du das für richtig hältst, auch mit einem
public boolean pieces[][] = new boolean[8][8];
oder, wenn du eine effiziente Engine implementieren willst, sowas wie
private int pieces[][] = new int[12][12]; // Ja, 12x12

Wie auch immer.

 

[Mister Fabulous]

Ok, danke für die Hilfe.

Ich dachte, das mit zweidimensionalen Arrays wäre scherzhaft gemeint und das es sowas garnicht gibt. Das mit Piece[][] hatte ich mir auch schon überlegt, aber wieder verworfen, weil mir die Schreibweise ziemlich suspekt vorkam. Dass das wirklich funktioniert, hatte ich nicht gedacht.

Naja, danke, ich werds damit mal versuchen.

 

[marasek]

Array[64] ist theoretisch auch eine Möglichkeit. Wenn man das Schachbrett speichert, gibt das ein wundervoll einfaches Datenformat: 64 Bytes die entweder NUL enthalten oder einen Wert, der einer Figur entspricht.

 

[0x7F800000]

Nna, das ist schon eine andere Frage. Wenn er das unbedingt irgendwie serealisieren will, kann er das später machen wie er will, aber zum programmieren wäre es ein krampf die koordinaten zum index und zurück ständig hinundherzurechnen. Und ein klein wenig ineffizienter wäre das auch.

 

[Marco13]

Nicht unbedingt: Zumindest unter C/C++ wird ein Arrayzugriff intern durch eine Addition (auf eine Speicheradresse) und ein "2D"-Arrayzugriff zwangsläufig durch eine Multiplikation+Addition geregelt. Man könnte jetzt nachsehen, wie es in Java ist. Bezüglich der Performance wäre das vielleicht(!) saog besser: Man braucht bei einem 8x8-Brett ja keine Multiplikation. Und wenn das ganze dann noch hübsch hinter einem Interface versteckt ist, kann man EINmal die passende Implementierung schreiben

class ArrayBoard implements Board
{
    private int array[] = new int[64];

    public int get(int x, int y)
    {
        int index = (y << 3) + x;
        return array[index];
    }

und hat damit genauso bequemen Zugriff, wie bei jeder anderen Implementierung.

(Das hatte mich sogar KURZ dazu bewogen, als Möglichkeit in den Raum zu stellen, dass man das
int board[][] = new int[12][12];
vielleicht am effizientesten durch ein
int board[] = new int[16*16];
ersetzen könnte, aber ... das war nur Spekulation...)

 

[0x7F800000]

und ein 12x12-Brett wird wo genau benötigt?

 

[Marco13]

Um sich das Testen der Größe zu sparen. Egal, wo ein Springer steht - bei einem 12x12-Feld kann man umständliche uns zeitraubende Tests wie
if (x>=0 && x<8 && y>=0 && y<8 && isFree(x,y)) { ... }
runterkondensieren auf
if (isFree(x,y)) { ... }

 

[andre111]

Aber trotzdem musst du irgendwann irgendwo wieder überprüfen ob man auch auf das jeweilige Feld ziehen darf.

 

[Marco13]

Ja... äh ... in der Methode "isFree" halt ?!

 

[andre111]

Das kannste ja bei nem 8x8 Feld genauso machen mit ner Methode "isFree".

 

[Marco13]

Ja... darum ging's ja auch nicht - nur darum, dass man sich viele, viele >= und <=-Tests spart. Wenn man mit einem Springer von einem Feld wegziehen will, muss man für die 8 erreichbaren Felder (x,y) jeweils testen

if (x>=0 && x<8 && y>=0 && y<8 && isFree(x,y))
{
    validMoves.add(x,y);
}

(und ob die Abfragen nun dort oder in der isFree-Methode gemacht werden, ändert ja nichts daran, dass sie gemacht werden müssen..)

Dann muss man prüfen, ob der König von einem Springer geschlagen werden könnte - also die 8 Felder um den König rum genauso abfragen.

Für jede Figur, wie z.B. eine Dame, die von (x,y) nach
(x+1,y)
(x,y+1)
(x+1,y+1)
(x-1,y)
(x,y-1)
(x-1,y-1)
(x+1,y-1)
(x-1,y+1)
ziehen will, muss man bei jedem dieser 9 Felder erstmal prüfen, ob
if (x>=0 && x<8 && y>=0 && y<8 && ...
und erst DANN kann man testen, ob das Feld überhaupt frei ist. Bei einem 12x12-Feld braucht man NUR zu prüfen, ob es Frei ist (weil die Felder <0 und >=8 natürlich als "belegt" bzw. "ungültig" markiert sind)

Computer sind zwar schnell, aber dumm. Und Deep Blue hätte Kasparov vielleicht nicht geschlagen, wenn er seine Zeit mit überflüssigen bounds-Tests verschwendet hätte :wink:

 

[didjitalist]

wenn man ein eindimensionales array verwendet, reicht für den ansatz eine größe von 10x12.

 

[Landei]

wenn man ein eindimensionales array verwendet, reicht für den ansatz eine größe von 10x12.

Nee, dann muss man ja aufpassen, dass der Springer nicht rechts raushüpft und links ankommt

 

[Quaxli]

Nee, dann muss man ja aufpassen, dass der Springer nicht rechts raushüpft und links ankommt

Das würde doch strategische Möglichkeiten eröffnen.

@Marco13
Das mit dem 12x12-Feld ist eine tolle Idee. Muß ich mir merken.

Da hat das Lesen dieses Problems doch was gebracht, auch wenn ich vermute, daß das mit dem Schachprogramm nix wird, wenn der TO schon nicht weiß, daß es 2-dimensionale Arrays gibt.

 

[0x7F800000]

@Marco13
Das mit dem 12x12-Feld ist eine tolle Idee. Muß ich mir merken.

Achso. Ja, durchaus elegante Idee, aus dem selben Grund habe ich bei allen Simulationen mit einem Gitter aus Quadern immer den "Rand" unbenutzt gelassen, um sich die blöden Tests zu ersparen (in 3D ist es nicht nur ineffizient, sondern einfach nur nervig zu tippen)

Aber konkret auf Schach übertragen: ihr optimiert hier O(0.023) zu O(0.017) bei einem absolut nicht zeitkritischen Problem, kommt schon^^

 

[Marco13]

Da die Stärke von Schachprogrammen zum allergrößten Teil darin liegt, dass sie - auf stupideste Art und Weise, aber brutalst schnell - viele, viele, viele Zustände durchprobieren, macht es ggf. schon Sinn, ihnen die Überprüfung der Gültigkeit dieser Zustände möglichst leicht zu machen. Wenn man durch das Weglassen dieser Bounds-Tests erreicht, dass ein Zug, für den der Computer vorher 5 Minuten nachgedacht hat, er dann nurnoch 4 Minuten nachdenken muss, ist das doch schon was...

 

[didjitalist]

Nee, dann muss man ja aufpassen, dass der Springer nicht rechts raushüpft und links ankommt

macht doch nichts. wenn der springer auf einem ungültigen feld landet, ist der zug nicht gültig. wo das ungültige feld nun ist, spielt keine rolle. also warum nicht 24 unnötige felder sparen?

 

[0x7F800000]

wie "sparen"? Wie willst du denn sonst feststellen, dass ein zug ungültig ist, ohne die ganzen <= >= Abfragen? Nene, Marco13's Vorschlag macht mit jeder Minute mehr und mehr Sinn

 

[Leroy42]

Toll!

Und wenn dann isFree(x,y) true liefert aber die Koordinaten <x,y> doch außerhalb
der erlaubten Grenzen sind, was soll dir dann das Ganze bringen?

 

[0x7F800000]

in diesem streifen kann man am anfang ja alles auf "voll" setzen, und nie wieder ändern.

 

[Marco13]

Bei einem 12x12-Feld braucht man NUR zu prüfen, ob es Frei ist (weil die Felder <0 und >=8 natürlich als "belegt" bzw. "ungültig" markiert sind)

Genau

Zitat von didjitalist wenn man ein eindimensionales array verwendet, reicht für den ansatz eine größe von 10x12.
Zitat von Landei: Nee, dann muss man ja aufpassen, dass der Springer nicht rechts raushüpft und links ankommt

Nee... hab' gerade nochmal überlegt: Das Feld, wo man dann links reinkommen würde, wäre ja das linkeste Feld, das ja auch ein (ungültiges) Randfeld ist - es ist ja egal, auf welches ungültige Feld man hüpfen würde.... (müßte man nochmal genau durchdenken, sollte aber auch mit 10x12 passen...)

 

[HannsW]

Genau
rade nochmal überlegt: Das Feld, wo man dann links reinkommen würde, wäre ja das linkeste Feld, das ja auch ein (ungültiges) Randfeld ist - es ist ja egal, auf welches ungültige Feld man hüpfen würde.... (müßte man nochmal genau durchdenken, sollte aber auch mit 10x12 passen...)

Und was passiert bei 10*12, wenn du nach links hüpfst?
Dann landest Du in nem "legalen" feld? Oder?

 

[0x7F800000]

Oooh, leute, ich find's soo lustig was ihr hier für ein Brainfuck-2D wegen einem Schachbrett veranstaltet^^

 

[herrpink]

ich bin auch ein neuling und will ein schachspiel realisieren
ich glaube, ich verstehe den ansatz für das 12x12 feld nicht ganz.
was für einen vorteil würde dies für beispielsweise eine Figur in der mitte des spielfeldes bringen? oder vielleicht kann ja jemand nochmal genauer erklären, wodrin der vorteil liegt

vielen dank schonmal

 

[Marco13]

@HannsW: Und was passiert bei 10*12, wenn du nach links hüpfst?
Dann landest Du in nem "legalen" feld? Oder?

Hmnee, glaub' nicht - das eigentliche Schachbrett würde ja von [1,2]-[8,9] gehen, d.h. wenn man z.B. ganz links oben in der Ecke steht, steht man bei Array-Index
i = x+y*10 = 1+2*10 = 21
Wenn man dann einen Rösselsprung (2 links, 1 hoch) macht, landet man bei x=-1 und y=1, und damit bei Index
i = x+y*10 = -1+1*10 = 9
Das ist streng genommen zwar die falsche Zeile, aber trotzdem einfach nur eines "von vielen" ungültigen Feldern.


@herrpink: Der Vorteil erschließt sich nicht so unmittelbar. Genaugenommen: Es gibt keinen "sichtbaren" Vorteil. In allen Fällen hat man irgendwo eine Methode wie
canMoveTo(x,y)
der man ausgehend von der aktuellen Position) die möglichen Zielfelder übergibt. Entscheidend ist nur, wie diese Methode implementiert ist. Wenn man das Spielbrett intern als 8x8-Array darstellt, dann müßte man die etwa so implementieren:

boolean canMoveTo(int x, int y)
{
    if (x>=0 && x<8 && y>=0 && y<8) // Erstmal prüben, ob die Position gültig ist
    {
        if (field[x][y] == EMPTY) return true; // Wenn das Feld frei ist, kann man hin...
        ...
    }
}

Wenn man das Spielfeld aber als 12x12-Array speichert, und alle Figuren demnach auf den Feldern [2,2] bis [9,9] liegen, dann kann man die Methode so implementieren

boolean canMoveTo(int x, int y)
{
    if (field[x][y] == EMPTY) return true; // Wenn das Feld frei ist, kann man hin...
    ...
}

Und es ist sichergestellt, dass die Methode bei Springer-Sprüngen nie mit x,y-Werten aufgerufen wird, die außerhalb der Arraygrenzen liegen. Wenn ein Springer bei [2,2] steht, dann kann er nach [0,1] oder [1,0] hüpfen, aber nicht nach [-1,0] oder so.

Das ist aber wirklich nur relevant, wenn man das letzte Quentchen Rechenzeit einsparen will. Für den Anfang sollte man erstmal die einfachste denkbare Variante verwenden (also den 8x8-Array, mit den Abfragen, ob die Position gültig ist). Das ganze hat so immernoch genug Frustrationspotential

 

[HannsW]

Das ist aber wirklich nur relevant, wenn man das letzte Quentchen Rechenzeit einsparen will. Für den Anfang sollte man erstmal die einfachste denkbare Variante verwenden (also den 8x8-Array, mit den Abfragen, ob die Position gültig ist). Das ganze hat so immernoch genug Frustrationspotential

Ich glaube, sich Gedanken über einen guten Alghoritmus zu machen, bevor man an den Rechner geht, ist auch für den Anfänger relevant. EIngige kurze Zeilen im Kommentar, warum man mehr Felder benutzt, und schon wird der Code für einen Externen ( Leser ) wesentlich leichter zu verstehen.

Zudem ist nach meiner Sicht einfacher im Programm zu prüfen:

-Darf ich auf dieses Feld?
als
- 1.( Habe ich ein valides Feld als Ziel?
und
-2. Wenn Valid: ist es belegt?

 

[herrpink]

vielen dank, habs jetzt verstanden.

 

[Marco13]

@HannsW: Grundsätzlich stimmt das, nur wird gerade ein Anfänger bei einem Schachprogramm viel dringendere Probleme haben. Abgesehen davon, dass diese Darstellung "unintuitiv" ist (man muss sich erst an die Verschiebung gewöhnen), ist die Wahrscheinlichkeit, dass der komplette (riesige) Rest des Programmes so effizient ist, dass so eine Optimierung nicht vollkommen untergeht, verschwindend gering... Ein konkretes Beispiel ... siehe den Thread zu "Folgeterm gesucht": Dort werden Dinge berechnet, die zu Berechnen in dieser Form jegliche Optimierung durch eingesparte Vergleiche ad absurdum führen...

 

[HannsW]

@Marco13: Ja, stimme Dir völlig zu. Ich hatte bei meiner Antwort auch nicht das komplette Schachprogramm im Sinne, als vielmehr nur die Frage nach dem "Warum" gerade dieser Speziallösung 12x12.
Aber das ist ja das schöne bei einer solche Diskussion, daß man ( Zitat meiner Großmutter, man wird alt wie ne Kuh, und lernt immer noch dazu ) seinen eigenen Denkapperat überprüfen kann!
So würde ich denn bei meinem Programm wahrscheinlich folgendes Konstukt nehmen ( Zeitersparnis kontra Lesbarkeit des Codes ) :

if ( [COLOR=Red] ![/COLOR] darf_ich_auf_dieses_Feld ( aktive Figur ) )    {
       verweigere();
}else {
        erlaube();
}

Aber damit verlasse ich wohl dasThreadthema.