An Programmierer: Ist ein spekulativer Algorithmus mögl

[Eduard Nemeth]

Geschrieben von:/Posted by: Eduard Nemeth at 19 May 2004 13:05:42:

An Programmierer: Ist ein spekulativer Algorithmus möglich oder denkbar?
Ich fände sowas sehr interessant!
Beispiel:
Eduard vs. Opponent
I played now Nxg7!? and I won.

abcdefgh8877665544332211abcdefghSMIRF FullChess FEN-Editor (© by R. Scharnagl) Ver. 1.3.5

r1bqr1k1/p1p2ppp/1p1p1nn1/3PpNB1/4P3/P1PB4/2PQ1PPP/R4RK1 w - - 0 1
und hier kurz eine Analyse der ganzen Partie:
[Event "Blitz:3'"]
[Site "Playchess.com"]
[Date "2004.05.17"]
[Round "?"]
[White "Eduard"]
[Black "Opponent"]
[Result "1-0"]
[ECO "A45"]
[WhiteElo "????"]
[BlackElo "????"]
[Annotator "Nemeth,Eduard"]
[PlyCount "37"]
[EventDate "2004.??.??"]
1. Nc3 {1} Nf6 {1} 2. d4 {1} e6 {13} 3. e4 {2} Bb4 {1} 4. Bd3 {2} b6 {2} 5. a3
{1} Bxc3+ {2} 6. bxc3 {0} Bb7 {1} 7. Qe2 {1} d6 {7} 8. Nf3 {2} Nbd7 {1} 9. O-O
{1} e5 {3} 10. d5 {1} O-O {3} 11. Bg5 {2} Re8 {3} 12. Qd2 {2} Nf8 {2} 13. Nh4 {
2} Ng6 {3} 14. Nf5 {2} Bc8 {4} 15. Nxg7 $5 {
Nach 5s habe ich dieses Opfer gespielt! 5} Kxg7 {2} 16. f4 {1} Bg4 {7} (16...
exf4 17. Rxf4 Nxf4 18. Qxf4 Nh5 19. Qh4 f6 20. Qxh5 fxg5 21. e5 Rh8 22. Rf1 Qe7
23. Rf6 Kg8 24. Qxg5+ Qg7 25. Bg6 $16) (16... h6 17. Bxh6+ Kxh6 18. fxe5+ Kg7
19. exf6+ Kh7 20. e5 Rxe5 21. Rae1 Qf8 22. Rxe5 dxe5 23. Qg5 Qh6 24. Qxe5 $16)
(16... Qd7 17. f5 Nf4 18. g3 N4xd5 19. exd5 Qe7 20. Bh4 h6 21. g4 Rg8 22. Kh1
Kh7 23. g5 hxg5 24. Bxg5 Bb7 25. c4 Rg7 (25... Kg7 26. Bh6+ Kh8 (26... Kh7 27.
Rf3 $18) 27. Rf3 $16) 26. Rf3 $16) 17. fxe5 {2} Kg8 {9} 18. Bxf6 {4} Qd7 {3}
19. Qh6 {xxxxxxxx rinde (Lag: Av=0.82s, max=5.0s) 4} 1-0
In der Diagrammstellung würde Ruffian 2.1.0 z.B. so spielen:
Eduard - Opponent, Blitz:3' Playchess.com 2004
r1bqr1k1/p1p2ppp/1p1p1nn1/3PpNB1/4P3/P1PB4/2PQ1PPP/R4RK1 w - - 0 1
Analysis by Ruffian 2.1.0:
15.Sg3 h6 16.Lxf6 Dxf6 17.Lb5 Td8 18.Lc6 Tb8 19.Tab1 Ld7 20.Sh5 De7
= (-0.05) Tiefe: 11/22 00:00:23 6974kN
15.f3 h6 16.Le3 Lxf5 17.exf5 Se7 18.Le4 Dd7 19.Dd3 c6 20.c4 Tab8
= (0.07) Tiefe: 11/22 00:00:26 8365kN
15.f3 h6 16.Le3 Lxf5 17.exf5 Se7 18.Le4 Dd7 19.Dd3 c6 20.c4 Sxe4 21.fxe4
= (0.12) Tiefe: 12/22 00:00:42 14172kN
(Nemeth, Privat 19.05.2004)
In dieser Stellung würde mich als Menschen solch ein Zug wie hier 15. f3 oder 15. Ng3 eines Computers nicht vom Hocker reißen, im Gegenteil! Ich würde eher durchatmen!
Hier eine Analyse nach Nxg7!?:
Eduard - Opponent, Blitz:3' Playchess.com 2004
r1bqr1k1/p1p2pNp/1p1p1nn1/3Pp1B1/4P3/P1PB4/2PQ1PPP/R4RK1 b - - 0 1
Analysis by Ruffian 2.1.0:

15...Kxg7 16.f4 exf4 17.Txf4 Sxf4 18.Dxf4 Sh5 19.Dh4 f6 20.Le3 Te5 21.g4 Dd7 22.gxh5 Dg4+ 23.Dxg4+ Lxg4 24.h6+ Kg6
µ (-1.32) Tiefe: 14/29 00:02:00 37705kN
15...Kxg7 16.f4 exf4 17.Txf4 Sxf4 18.Dxf4 Sh5 19.Dh4 f6 20.Le3 Te5 21.g4 De8 22.gxh5 Txh5 23.Dg3+ Kh8 24.Tf1
µ (-1.37) Tiefe: 15/31 00:03:25 67776kN
(Nemeth, Privat 19.05.2004)
Nach etwa 3 Minuten (auf meinem lahmen p3 600MHz Rechner) zeigt Ruffian 2.1.0 trotz einer Figur weniger, hier nur etwa –1.30 gegen sich, andere Programme sind da sogar schon fast bei 0.00!
Für mich als Menschen, wäre es in der Tat sehr schwer, gegen einen Computer nach Nxg7 und folgendem f4!? eine Verteidigung zu finden, auch wenn das Opfer nicht ganz korrekt wäre!
(übrigens: das Opfer hier ist sogar korrekt)
Klar, gegen andere Programme ist ein spekulativer Algorithmus sicher nicht das Gelbe vom Ei, doch gegen Menschen kann das:
1. sehr interessant sein.
2. den Menschen sogar praktisch vor größere Probleme stellen!

Meine Idee wäre diese: Ein Programm untersucht in einem speziellen (nur gegen Menschen) spekulativen Modus, einige Opfereinschläge (Taktik also),
und findet das Programm dann, im Vergleich zu dem normalen Zug das es sonst
spielen würde, eine Opfervariante wo dann trotz einer Figur weniger (!) das Programm nur etwa –1 gegen sich anzeigt, so spielt es dann den spekulativen Zug!
Diesen Modus könnte man z.B. in den Engine-Optionen EIN – und Abschalten.
Interessante wäre auch noch, wenn beim eingeschaltem Spekulativen Modus, ein „solcher“ taktischer Opferzug angezeigt würde! Als Mensch könnte man dann die Stellung dann weiter analysieren...und wer weiß was man da alles finden könnte für das eigene Spiel-Repertoire?
Sowohl zum Training-Spiel (und sogar als Turnierspiel gegen Menschen), als auch als Analyse-Idee, wäre solch ein Modus in meinen Augen für den Menschen sehr interessant, da bin ich mir sehr sicher.
Was haltet ihr Programmierer davon?
Regards,
Eduard

[Reinhard Scharnagl]

Geschrieben von:/Posted by: Reinhard Scharnagl at 19. May 2004 15:17:
Als Antwort auf:/In reply to: An Programmierer: Ist ein spekulativer Algorithmus möglich? geschrieben von:/posted by: Eduard Nemeth at 19 May 2004 13:05:42:

[...]
Was haltet ihr Programmierer davon?
Regards,
Eduard

Hallo Eduard,
soweit ich weiß gibt es bereits solche Ansätze von "Schwindeln", womit man
meint, nicht den aus Sicht des Programms besten Zug zu spielen, sondern den,
mit dem man den Gegener in eine erkannte Falle locken möchte.
Damit solche Verfahren funktionieren, ist es jedoch nötig, über die Spieler-
Persönlichkeit (oder Engine-Charakteristik) des Gegners informiert zu sein.
Soweit ich informiert bin, gestattet nun UCI-2 der Engine die Kenntnis der
Identität des Gegners. Viele GUIs und wohl auch die Winboard Szene sind aber
wohl noch nicht so weit.
Erst also wenn Engines Buch führen über die Vorlieben ihrer Gegner, kann ein
solches Strategem wirklich Sinn machen. Vorher ist es ein Alles oder Nichts
Spiel. Darum warte ich damit lieber noch eine Weile.
Gruß, Reinhard.

[Volker Pittlik]

Geschrieben von:/Posted by: Volker Pittlik at 19 May 2004 22:09:06:
Als Antwort auf:/In reply to: Re: An Programmierer: Ist ein spekulativer Algorithmus möglich? geschrieben von:/posted by: Reinhard Scharnagl at 19. May 2004 15:17:


...

Soweit ich informiert bin, gestattet nun UCI-2 der Engine die Kenntnis der
Identität des Gegners. Viele GUIs und wohl auch die Winboard Szene sind aber
wohl noch nicht so weit.

Dann informiere Dich mal etwas weiter:
"... name X
This command informs the engine of its opponent's name. When the engine is playing on a chess server, xboard obtains the opponent's name from the server. When the engine is playing locally against a human user, xboard obtains the user's login name from the local operating system. When the engine is playing locally against another engine, xboard uses either the other engine's filename or the name that the other engine supplied in the myname option to the feature command. By default, xboard uses the name command only when the engine is playing on a chess server. Beginning in protocol version 2, you can change this with the name option to the feature command; see below."
Steht alles unter http://www.tim-mann.org/xboard/engine-intf.html. Link dazu steht oben auf der Titelseite.
Volker

[Reinhard Scharnagl]

Geschrieben von:/Posted by: Reinhard Scharnagl at 20. May 2004 00:01:
Als Antwort auf:/In reply to: Re: An Programmierer: Ist ein spekulativer Algorithmus möglich? geschrieben von:/posted by: Volker Pittlik at 19 May 2004 22:09:06:

...

Soweit ich informiert bin, gestattet nun UCI-2 der Engine die Kenntnis der
Identität des Gegners. Viele GUIs und wohl auch die Winboard Szene sind aber
wohl noch nicht so weit.

Dann informiere Dich mal etwas weiter:
"... name X
This command informs the engine of its opponent's name. When the engine is playing on a chess server, xboard obtains the opponent's name from the server. When the engine is playing locally against a human user, xboard obtains the user's login name from the local operating system. When the engine is playing locally against another engine, xboard uses either the other engine's filename or the name that the other engine supplied in the myname option to the feature command. By default, xboard uses the name command only when the engine is playing on a chess server. Beginning in protocol version 2, you can change this with the name option to the feature command; see below."
Steht alles unter http://www.tim-mann.org/xboard/engine-intf.html. Link dazu steht oben auf der Titelseite.
Volker

Danke für den Hinweis. So lerne ich dazu.
Reinhard.

[Eduard Nemeth]

Geschrieben von:/Posted by: Eduard Nemeth at 20 May 2004 00:26:15:
Als Antwort auf:/In reply to: Re: An Programmierer: Ist ein spekulativer Algorithmus möglich? geschrieben von:/posted by: Reinhard Scharnagl at 19. May 2004 15:17:

Hallo Eduard,
Hallo Reinhard!
soweit ich weiß gibt es bereits solche Ansätze von "Schwindeln", womit man
meint, nicht den aus Sicht des Programms besten Zug zu spielen, sondern den,
mit dem man den Gegner in eine erkannte Falle locken möchte.
Mir ist auch bekannt (weiß jetzt aber nicht welches Programm das ist) dass
es in aussichtslosen Stellungen sozusagen versucht zu schwindeln.
Meine Intension ist jedoch eine andere: Mir geht es,
a) nicht um einen Schwindel-Modus.
b) auch nicht darum dass der Gegner erkannt wird.
Eine Funktion ähnlich wie z.B. Anti-Human (wo dann meist ein Anti-Trojaner-Code
eingeschaltet wird), soll einen, sagen wir Spekulativ-Modus einschalten.
Das Besondere daran soll ein speziell für das Spiel gegen Menschen, sowie für
Analysen für Menschen, eingeschalteter Algorithmus sein.
Die Programme spielen ja immer nur so wie es ihnen die Bewertung sagt, und da die Suchtiefe der Programme oft nicht tief genug ist um manche interessante
Kombinationen zu finden, so entgeht ihnen manchmal eine schöne Kombination
(selbst für den Fall dass sie nicht ganz korrekt ist).
Bei dem von mir gedachtem Algorithmus dachte ich keineswegs daran, dass das
Programm dann nur schwindelt. Es kann gut ausgehen aber auch nicht. Man weiss es nicht genau.
Wenn jedoch ein Programm opfert (und danach noch genügend Material auf dem Brett hat, sagen wir Dame + Turm + eine Leichtfigur + mindestens 5 Bauern) und nur einen Score von etwa -1 gegen sich anzeigt, so sagt mir die Tendenz dass solch ein Opfer durchaus korrekt sein könnte (auch wenn das Programm noch nicht alles durchgerechnet hat), aber zumindest stellt es den Gegner vor eine sehr schwierige Verteidigung, hier vor allem den Menschen gegen einen Computer!
Ich würde solch ein Programm sehr attraktiv finden, auch für Analysen! Der Modus sollte manuell ein - und abschaltbar sein.
Damit solche Verfahren funktionieren, ist es jedoch nötig, über die Spieler-
Persönlichkeit (oder Engine-Charakteristik) des Gegners informiert zu sein.
Das ist in meinen Augen nicht notwendig, da dieser Modus ja NICHT
der Standard-Modus der Engine ist. Den Modus sollte man manuell einschalten
können.
Bei Fritz z.B. gibt es ja schon den Modus Freund, wo sich die Engine
mit der Zeit auf die Spielstärke des Gegners von selbst einstellt. Ferner gibt es bei Fritz auch den Modus Sparring, wo die Engine einmal in der Partie absichtlich einen taktischen Einschlag zulässt! Warum könnte man daher nicht auch einen Modus mit meiner Idee implementieren können?

Soweit ich informiert bin, gestattet nun UCI-2 der Engine die Kenntnis der
Identität des Gegners.
Das wusste ich nicht. Wie meinst Du das genau?
Viele GUIs und wohl auch die Winboard Szene sind aber
wohl noch nicht so weit.
Das weiss ich nicht? Bei Fritz jedenfalls funktioniert ja der Modus FREUND und SPARRING, also müsste auch ein Modus SPEKULATIV möglich sein.
Erst also wenn Engines Buch führen über die Vorlieben ihrer Gegner, kann ein
solches Strategem wirklich Sinn machen. Vorher ist es ein Alles oder Nichts
Spiel. Darum warte ich damit lieber noch eine Weile.
Auf dein Programm bin ich sehr gespannt Reinhard.
Gruß, Reinhard.
Gruss,
Eduard
PS: Dein FRC-Buch ist eine sehr interessante Sache. Wir könnten darüber ja per eMail sprechen. Ich weiss z. B. dass die nächsten Classics in Mainz im August stattfinden, und Svidler wird da seinen Titel im FRC verteidigen, auch wird er ein FRC-Simultan geben. FRC ist also noch IN.

[Reinhard Scharnagl]

Geschrieben von:/Posted by: Reinhard Scharnagl at 20. May 2004 18:13:
Als Antwort auf:/In reply to: Re: An Programmierer: Ist ein spekulativer Algorithmus möglich? geschrieben von:/posted by: Eduard Nemeth at 20 May 2004 00:26:15:

Hallo Eduard,
Hallo Reinhard!
soweit ich weiß gibt es bereits solche Ansätze von "Schwindeln", womit man
meint, nicht den aus Sicht des Programms besten Zug zu spielen, sondern den,
mit dem man den Gegner in eine erkannte Falle locken möchte.
Mir ist auch bekannt (weiß jetzt aber nicht welches Programm das ist) dass
es in aussichtslosen Stellungen sozusagen versucht zu schwindeln.
Meine Intension ist jedoch eine andere: Mir geht es,
a) nicht um einen Schwindel-Modus.
b) auch nicht darum dass der Gegner erkannt wird.
Eine Funktion ähnlich wie z.B. Anti-Human (wo dann meist ein Anti-Trojaner-Code
eingeschaltet wird), soll einen, sagen wir Spekulativ-Modus einschalten.
Das Besondere daran soll ein speziell für das Spiel gegen Menschen, sowie für
Analysen für Menschen, eingeschalteter Algorithmus sein.
Die Programme spielen ja immer nur so wie es ihnen die Bewertung sagt, und da die Suchtiefe der Programme oft nicht tief genug ist um manche interessante
Kombinationen zu finden, so entgeht ihnen manchmal eine schöne Kombination
(selbst für den Fall dass sie nicht ganz korrekt ist).
Bei dem von mir gedachtem Algorithmus dachte ich keineswegs daran, dass das
Programm dann nur schwindelt. Es kann gut ausgehen aber auch nicht. Man weiss es nicht genau.
Wenn jedoch ein Programm opfert (und danach noch genügend Material auf dem Brett hat, sagen wir Dame + Turm + eine Leichtfigur + mindestens 5 Bauern) und nur einen Score von etwa -1 gegen sich anzeigt, so sagt mir die Tendenz dass solch ein Opfer durchaus korrekt sein könnte (auch wenn das Programm noch nicht alles durchgerechnet hat), aber zumindest stellt es den Gegner vor eine sehr schwierige Verteidigung, hier vor allem den Menschen gegen einen Computer!
Ich würde solch ein Programm sehr attraktiv finden, auch für Analysen! Der Modus sollte manuell ein - und abschaltbar sein.
Damit solche Verfahren funktionieren, ist es jedoch nötig, über die Spieler-
Persönlichkeit (oder Engine-Charakteristik) des Gegners informiert zu sein.
Das ist in meinen Augen nicht notwendig, da dieser Modus ja NICHT
der Standard-Modus der Engine ist. Den Modus sollte man manuell einschalten
können.
Bei Fritz z.B. gibt es ja schon den Modus Freund, wo sich die Engine
mit der Zeit auf die Spielstärke des Gegners von selbst einstellt. Ferner gibt es bei Fritz auch den Modus Sparring, wo die Engine einmal in der Partie absichtlich einen taktischen Einschlag zulässt! Warum könnte man daher nicht auch einen Modus mit meiner Idee implementieren können?

Soweit ich informiert bin, gestattet nun UCI-2 der Engine die Kenntnis der
Identität des Gegners.
Das wusste ich nicht. Wie meinst Du das genau?
Viele GUIs und wohl auch die Winboard Szene sind aber
wohl noch nicht so weit.
Das weiss ich nicht? Bei Fritz jedenfalls funktioniert ja der Modus FREUND und SPARRING, also müsste auch ein Modus SPEKULATIV möglich sein.
Erst also wenn Engines Buch führen über die Vorlieben ihrer Gegner, kann ein
solches Strategem wirklich Sinn machen. Vorher ist es ein Alles oder Nichts
Spiel. Darum warte ich damit lieber noch eine Weile.
Auf dein Programm bin ich sehr gespannt Reinhard.
Gruß, Reinhard.
Gruss,
Eduard
PS: Dein FRC-Buch ist eine sehr interessante Sache. Wir könnten darüber ja per eMail sprechen. Ich weiss z. B. dass die nächsten Classics in Mainz im August stattfinden, und Svidler wird da seinen Titel im FRC verteidigen, auch wird er ein FRC-Simultan geben. FRC ist also noch IN.

Das was mir vorschwebt ist kein Modus, sondern eine grundlegende neue Strategie.
Offenbar werden im Schach alle Bewertungen von Stellungen mit der gleichen Funk-
tion ermittelt. Dies ist aber nicht optimal. Da es keine optimale Bewertungs-
funktion geben kann (der Spielbaum ist einfach zu groß) ist die eigentliche
Funktion bei der Bewertung gegnerischer Züge die der Prognose, welcher Zug
wohl vom Gegner gezogen würde. Dies hängt aber offenbar nicht von der eigenen
Bewertungsfunktion ab, sondern von der zumeist unbekannten des Gegners. Ziel
ist also eine Verbesserung dieser Prognoseeigenschaft, indem ein entsprechendes
Modell der gegnerischen Spielcharakteristik mit einbezogen wird.
Die Folge ist, dass das Negamax-Verfahren so nicht mehr anwendbar ist, weil
hierin vorausgesetzt wird, dass die Gegner-Einschätzung immer 1-x ist, wobei
x die eigene Einschätzung ist.
Die Bewertung setzt sich aber zusammen als ein lineares Produkt verschiedener
Elemente, welche in die Bewertung eingehen. Die analysierten Bestandteile
bleiben im neuen Ansatz zwar erhalten, werden aber mit anderen Faktoren (passend
zur Spielerpersönlichkeit) gewichtet. Die Bewertung mutiert also auf diese
Weise zu einem mehrdimensionalen Vektor.
Dieses ist aber Zukunftsmusik und findet erst in späteren Versionen Anwendung.
Es geht darum, dass eine Engine die Identität des Gegners kennt. So könnte
sie im Laufe der Zeit eine Art Persönlichkeitsprofil dazu errechnen, aus dem
der individuelle Spielstil hervorgeht.
Habe dir eine Arbeitskopie davon zugesandt, ich bitte um konstruktive Kritik.
Reinhard.