Schach-Programm (Anfangs-tipps)

[Gast]

Moinsen,

da ich hier die meisten erfahrenen Progger vermute, stelle ich hier mein Problem.
Ich möchte einen Schach-spiel Programm schreiben. Die GUI wäre ein Problem, ich könnte das zwar in 3D Versuchen (da meine erste Frage, lohnt sich das überhaupt?), 2D wäre aber auch ok.
Meine zweite Frage wäre dann die interne Spielweise des Programms. Ich denke, das klassische Brute-force Prinzip (so ca. 2-3 Züge im Voraus, Weltmeister machen auch nur 6), und die Schwierigkeitsstufe wird nach der Anzahl Züge, die der Computer im Voraus abklappert, bestimmt.

Also, ich werde eine abstrakte Basisklasse figure für alle Figuren schreiben (macht Sinn), von der ich dann alle anderen Figuren ableite. Es gibt dann eine (pur) virtuelle Funktion bool move() und bool can_move().

Also vorwärts-deklariere ich figure, mache dann die Schach-brett Klasse (die ein Multidimensionales array von figure-pointern enthält (die entweder mit nullptr (0) oder einem Zeiger auf eine Kindklasseninstanz belegt sind). Jede Figur hat einen Zeiger auf ein Schachbrett (auf dem sie steht) und muss dann move() implementieren sodass sie entweder false zurückgibt (wenn die Abfrage mit can_move() false zurückgibt) oder true (es wurde gezogen).
Wird eine Figur geschlagen, wird sie gelöscht und in die Chronik eingetragen (falls einmal zurück-gezogen werden möchte). Die Stelle im MD-Array des Bretts wird mit nullptr besetzt.

So ähnlich also:

#include <vector>

class figure;

class Brett
{
    std::vector<std::vector<figure*>> figureArray;

public:

    Brett():
    figureArray(8, std::vector<figure*>(8, nullptr)) {}
};

class figure
{
public:

    typedef std::size_t size_type;

    virtual bool move(size_type, size_type) = 0;
    virtual bool can_move(size_type, size_type) = 0;

    size_type x(){return x_pos;}
    size_type y(){return y_pos;}

    virtual void moveToInitialPos() = 0;

private:

    size_type x_pos, y_pos,
              ini_x_pos, ini_y_pos;
};

Über Vorschläge und so würde ich mich freuen

VD

[SeppJ]

Hacker schrieb:

Meine zweite Frage wäre dann die interne Spielweise des Programms. Ich denke, das klassische Brute-force Prinzip (so ca. 2-3 Züge im Voraus, Weltmeister machen auch nur 6), und die Schwierigkeitsstufe wird nach der Anzahl Züge, die der Computer im Voraus abklappert, bestimmt.

Schätz doch solche Pläne zumindest mal grob ab, bevor du damit an die Öffentlichkeit gehst. Du wirst feststellen, dass das bei drei Zügen etwas in Richtung 100 Milliarden Kombinationen ist. Außerdem fehlt etwas ganz entscheidendes: Wie bewertest du, ob ein Zug gut oder schlecht ist?

Es wäre wohl auch eine gute Idee, sich vielleicht mal grundlegend über Schachalgorithmen zu informieren, man muss ja nicht unbedingt immer alle Räder neu erfinden. Dann wird das wenigstens auch ein Programm, das auf einem Desktoprechner einen schlechten Menschen schlagen kann und kein Programm, dass nur auf Superrechnern läuft und so spielt wie ein hirnamputierter Vierjähriger du selber.

Also, ich werde eine abstrakte Basisklasse figure für alle Figuren schreiben (macht Sinn), von der ich dann alle anderen Figuren ableite. Es gibt dann eine (pur) virtuelle Funktion bool move() und bool can_move().

Also vorwärts-deklariere ich figure, mache dann die Schach-brett Klasse (die ein Multidimensionales array von figure-pointern enthält (die entweder mit nullptr (0) oder einem Zeiger auf eine Kindklasseninstanz belegt sind). Jede Figur hat einen Zeiger auf ein Schachbrett (auf dem sie steht) und muss dann move() implementieren sodass sie entweder false zurückgibt (wenn die Abfrage mit can_move() false zurückgibt) oder true (es wurde gezogen).
Wird eine Figur geschlagen, wird sie gelöscht und in die Chronik eingetragen (falls einmal zurück-gezogen werden möchte). Die Stelle im MD-Array des Bretts wird mit nullptr besetzt.

So ähnlich also:

#include <vector>

class figure;

class Brett
{
    std::vector<std::vector<figure*>> figureArray;

public:

    Brett():
    figureArray(8, std::vector<figure*>(8, nullptr)) {}
};

class figure
{
public:

    typedef std::size_t size_type;

    virtual bool move(size_type, size_type) = 0;
    virtual bool can_move(size_type, size_type) = 0;

    size_type x(){return x_pos;}
    size_type y(){return y_pos;}

    virtual void moveToInitialPos() = 0;

private:

    size_type x_pos, y_pos,
              ini_x_pos, ini_y_pos;
};

Über Vorschläge und so würde ich mich freuen

VD

Viel zu konkrete Planung bei viel zu vagem Konzept. Definier doch erst einmal genau, was deine Klassen sind und was sie können, bevor du dir Gedanken um die technische Umsetzung vonwegen Kindklassenzeigern, Nullpointern & Co. machst. Oder wenn du nichts von Planung hältst, dann programmier doch einfach weiter und passe dein Modell den Notwendigkeiten an. Letzteres ist keine Ironie, sondern durchaus ein gutes Vorgehen für kleine Progrämmchen wie du hier planst. Man lernt dann bloß nichts über Planung, wenn man das so macht .

P.S.: Planst du eigentlich, dass dein Schachfeld im Laufe des Spiels seine Form und Größe ändert oder warum ist dein Brett ein dynamisches Feld von dynamischen Feldern?
Woher weiß eine Bauer, wo er am Anfang steht? Sind nicht alle Bauern gleich?
Woher weiß eine Figur, ob sie ziehen kann? Sie muss dafür das Brett kennen.
Ich halte das ganze Modell, welches bis hier ersichtlich ist, für nicht sonderlich gelungen. Die Verantwortlichkeiten sind komisch aufgeteilt und die Objekte merkwürdig modelliert. Ich kann deinen Gedankengang zwar nachvollziehen, aber dein Ergebnis ist dann eben jenes, welches man durch nicht sehr tiefgehendes Nachdenken erhält.

[Gast]

SeppJ schrieb:

Planst du eigentlich, dass dein Schachfeld im Laufe des Spiels seine Form und Größe ändert oder warum ist dein Brett ein dynamisches Feld von dynamischen Feldern?

Haha, ja hast Recht. Ich nehme ein std::array.

SeppJ schrieb:

Woher weiß eine Bauer, wo er am Anfang steht? Sind nicht alle Bauern gleich?

Bin schon weiter, es gibt einen eigenen Konstruktor für die initial positions

SeppJ schrieb:

Woher weiß eine Figur, ob sie ziehen kann? Sie muss dafür das Brett kennen.

Bin auch schon weiter, Klasse figure hat einen Zeiger auf eine Brett-Instanz , die beim Konstruktor übergeben wird.

SeppJ schrieb:

Ich halte das ganze Modell, welches bis hier ersichtlich ist, für nicht sonderlich gelungen. Die Verantwortlichkeiten sind komisch aufgeteilt und die Objekte merkwürdig modelliert. Ich kann deinen Gedankengang zwar nachvollziehen, aber dein Ergebnis ist dann eben jenes, welches man durch nicht sehr tiefgehendes Nachdenken erhält.

Klar könntest du Recht haben, aber.. Nun, ich werde das alles näher Planen müssen, da hast du schon Recht. Denn wenn man NICHT plant, kann gern die ein oder andere große Überrraschung kommen...

[__cu]

1. http://chessprogramming.wikispaces.com/
2. sag Bescheid, sobald dein Programm stärker als Houdini ist.

[Gast]

SeppJ schrieb:

Dann wird das wenigstens auch ein Programm, das auf einem Desktoprechner einen schlechten Menschen schlagen kann und kein Programm, dass nur auf Superrechnern läuft und so spielt wie ein hirnamputierter Vierjähriger du selber.

Ich spiele ziemlich gut Schach.

Als guten Zug könnte ich einen Zug werten lassen, der mehreres Angreift (Gabeln), etwas frisst das entweder geschützt ist aber mehr als die Figur wert ist, oder nicht geschützt und dann eben vielleicht schlechter. Dabei gibt es Prioritäten von stehen bleiben und fressen für bestimmte Figuren ...

Das ich den Algorithmus genau Planen muss ist ja mal sowas von klar. Aber das ist der theoretische Planungsteil, den ich ja noch mache (das oben ist doch nur eine Skizze).

[Gast]

http://de.wikipedia.org/wiki/Alpha-Beta-Suche

[nachtfeuer]

Gui ist hier erstmal irrelevant (und später auch kein großes Problem), würde ich sagen. Zuerst Konsoleversion, dann weitersehen.

Zu diesem Thema wird hier aber öfter was geschrieben, und es lohnt sich auch, mal reinzugucken, z.B.
http://www.c-plusplus.net/forum/299768-10?highlight=schach&sid=a3a96127892eae54bb195775ee1fa69d
oder
http://www.c-plusplus.net/forum/289261?highlight=schach&sid=a3a96127892eae54bb195775ee1fa69d

[Gast]

µ schrieb:

http://de.wikipedia.org/wiki/Alpha-Beta-Suche

Danke (Danke natürlich auch an SeppJ, der aber wieder etwas böse auf mich ist (weil ich doof bin?))

Edit: Danke an nachtfeuer

[Gast]

Ich werde zuerst das Klassen-interface fertigmachen (dazu gehört einfach die Hierarchie der Figuren und ihre can_move/move Funktionen). Danach werde ich mich definitiv mit den Algorithmen auseinandersetzen. Vielen Dank an alle, werde hier noch Posten, wie es bei mir geht (vielleicht kann SeppJ das ja ins Projekte-Forum verschieben?).

[Gast]

SeppJ schrieb:

Du wirst feststellen, dass das bei drei Zügen etwas in Richtung 100 Milliarden Kombinationen ist.

Ich wette dagegen
Kubikwurzel aus 100 Milliarden ist ca. viereinhalb Tausend. Bei einem durchschnittlichen Schachspiel (zwischendrin) summiert sich die Anzahl aller möglicher Züge durchschnittlich auf 60 -70 (was natürlich stark abweichen kann, aber nicht auf 1000 kommt). z.B. 100³ ist eine Million, 60³ ist 216000. Tja, du hast auch so Recht.

Edit: Bedenke! Der Computer hat relativ viel Zeit (ich habe nichts gegen ca. 10 Sekunden, 15 Sekunden ist ok).

[Mario Sandler]

http://de.wikipedia.org/wiki/Schach#Grundbegriffe_und_Spielziel

In der Schachnotation wird immer eine weiße und eine anschließende schwarze Figurenbewegung zusammen nummeriert und als Zug bezeichnet.

Mit deinen 3 Zügen im voraus bist du dann bei 60^6 = 50 Milliarden.
Die Abschätzung passt also schon

[Mechanics]

Hacker schrieb:

Ich spiele ziemlich gut Schach.

Wie gut? Wie hoch ist deine ELO bzw. DWZ?

[Jester]

Mechanics schrieb:

Hacker schrieb:

Ich spiele ziemlich gut Schach.

Wie gut? Wie hoch ist deine ELO bzw. DWZ?

Was erwartest Du denn bei jemandem der geschützte und nicht geschützte Figuren frisst?

[Gast]

Mechanics schrieb:

Hacker schrieb:

Ich spiele ziemlich gut Schach.

Wie gut? Wie hoch ist deine ELO bzw. DWZ?

Ich spiele nicht im Verein.

Edit: Nun, im Vergleich zu den Top 200. Deutschen spiele ich natürlich nicht gut Schach. Aber gut genug, um (seit ca. 1 Jahr durchgehend) bester in der Schach-AG meiner Schule zu sein (was was heißt, denn dann bin ich bester der Schule).

[Gast]

Jester schrieb:

Mechanics schrieb:

Hacker schrieb:

Ich spiele ziemlich gut Schach.

Wie gut? Wie hoch ist deine ELO bzw. DWZ?

Was erwartest Du denn bei jemandem der geschützte und nicht geschützte Figuren frisst?

Tu ich nicht (?)

[Gast]

Mario Sandler schrieb:

http://de.wikipedia.org/wiki/Schach#Grundbegriffe_und_Spielziel

In der Schachnotation wird immer eine weiße und eine anschließende schwarze Figurenbewegung zusammen nummeriert und als Zug bezeichnet.

Mit deinen 3 Zügen im voraus bist du dann bei 60^6 = 50 Milliarden.
Die Abschätzung passt also schon

Bin schon etwas wirr im Kopf. Danke.

[Mechanics]

Hacker schrieb:

Mechanics schrieb:

Hacker schrieb:

Ich spiele ziemlich gut Schach.

Wie gut? Wie hoch ist deine ELO bzw. DWZ?

Ich spiele nicht im Verein.

Edit: Nun, im Vergleich zu den Top 200. Deutschen spiele ich natürlich nicht gut Schach. Aber gut genug, um (seit ca. 1 Jahr durchgehend) bester in der Schach-AG meiner Schule zu sein (was was heißt, denn dann bin ich bester der Schule).

Das kann ich schlecht einschätzen. Kann ja durchaus sein, dass alle anderen total schlecht spielen. Ich bin mir ziemlich sicher, dass ich in der Schule damals auch alle locker geschlagen hätte, bis auf einen. Hast du mal auf größeren Portalen im Internet gespielt, wo man die Spielstärke halbwegs einschätzen kann?

[Gast]

Mechanics schrieb:

Hacker schrieb:

Mechanics schrieb:

Hacker schrieb:

Ich spiele ziemlich gut Schach.

Wie gut? Wie hoch ist deine ELO bzw. DWZ?

Ich spiele nicht im Verein.

Edit: Nun, im Vergleich zu den Top 200. Deutschen spiele ich natürlich nicht gut Schach. Aber gut genug, um (seit ca. 1 Jahr durchgehend) bester in der Schach-AG meiner Schule zu sein (was was heißt, denn dann bin ich bester der Schule).

Das kann ich schlecht einschätzen. Kann ja durchaus sein, dass alle anderen total schlecht spielen. Ich bin mir ziemlich sicher, dass ich in der Schule damals auch alle locker geschlagen hätte, bis auf einen. Hast du mal auf größeren Portalen im Internet gespielt, wo man die Spielstärke halbwegs einschätzen kann?

Nope. Empfehl mal eins. Oder lass mal zusammen spielen.

[cooky451]

rofl, bester in der Schule.
Kannst du hier den Hard mode schlagen? http://www.chess.com/play/computer.html

[Mechanics]

Hacker schrieb:

Nope. Empfehl mal eins. Oder lass mal zusammen spielen.

Naja, der größte kostenlose ist wohl FICS, oder zumindest kenne ich keine größeren.
Nicht dass du jetzt meinst, ich würde gut spielen... Ich finde eher, dass ich total schlecht spiele. Keine Chance gegen Vereinsspieler.

[Gast]

cooky451 schrieb:

rofl, bester in der Schule.
Kannst du hier den Hard mode schlagen? http://www.chess.com/play/computer.html

Ja, ich dich auch rofl. Und: Ich bin weit gekommen... nur leider hat er mir eine völlig unerwartete Gabel gestellt.