[Programmierung] SEE und/oder History Heuristic

By Karl-Heinz Milaster Date 2009-08-22 21:11 Edited 2009-08-22 21:17

[quote="Reinhard Scharnagl"]Macht es Sinn, beide Verfahren parallel zu verwenden, oder sollte man sich
für nur eines davon entscheiden, und falls ja, aus welchem Grund?[/quote]

Hallo Reinhard,

Da SEE dazu dient, Schlagzüge zu beurteilen, die History Heuristic (http://www.personeel.unimaas.nl/m-winands/documents/relhis.pdf) aber für eine bessere Zugsortierung hergenommen wird, verstehe ich Deine Frage nicht.

Gruss,
khm

By Reinhard Scharnagl Date 2009-08-22 23:33

[quote="Karl-Heinz Milaster"]
[quote="Reinhard Scharnagl"]Macht es Sinn, beide Verfahren parallel zu verwenden, oder sollte man sich
für nur eines davon entscheiden, und falls ja, aus welchem Grund?[/quote]
Da SEE dazu dient, Schlagzüge zu beurteilen, die History Heuristic (http://www.personeel.unimaas.nl/m-winands/documents/relhis.pdf) aber für eine bessere Zugsortierung hergenommen wird, verstehe ich Deine Frage nicht.[/quote]
Hallo Karl-Heinz,

die Beurteilung von Schlagzügen hat u.a. Einfluss auf deren Sortierung - auf der anderen Seite gibt eine History Heuristic (je nach deren Ausprägung in unterschiedlicher Präzision) auch gute (wenn auch weniger präzise) Prognosen ab für die Durchschlagskraft eines Schlagzugs, dies allerdings mit m.E. deutlich geringerem Aufwand.

Insofern stellt sich die Frage, ob es nicht ökonomischer ist, sich ggf. nur auf eine dieser Ideen zu konzentrieren, da deren produzierte Informationsgewinne eben nicht orthogonal sind.

Danke für Deine Reaktion hier, mit bestem Gruß, Reinhard.

By Karl-Heinz Milaster Date 2009-08-23 00:09

[quote="Reinhard Scharnagl"]die Beurteilung von Schlagzügen hat u.a. Einfluss auf deren Sortierung[/quote]

Hier stimme ich Dir nur insoweit zu, als dass SEE (Static Exchange Evaluation) Einfluss auf die Sortierung der Schlagzüge, nicht aber auf den Rest der Züge hat.

Gruss,
khm

By Reinhard Scharnagl Date 2009-08-23 01:01

Ein Schlagabtausch ist auch auf dem Zielfeld nach einem ruhigen Zug möglich. Insofern machte SEE auch bei Nichtschlagzügen Sinn. Dass man es i.d.R. nicht so macht, ist wohl dem Aufwand geschuldet, der dem SEE innewohnt, eigentlich aber inkonsequent. Dahinter steckt wohl die geringe Hoffnung, dass gespielte Schlagzüge größere Vorteile bringen können, als nicht gespielte Patzerzüge Nachteile zu vermeiden helfen. Sind aber Schlagzüge nicht zielführend, könnte SEE auch bei den übrigen wertvoll sein.

By Karl-Heinz Milaster Date 2009-08-23 18:13

[quote="Reinhard Scharnagl"]Ein Schlagabtausch ist auch auf dem Zielfeld nach einem ruhigen Zug möglich. Insofern machte SEE auch bei Nichtschlagzügen Sinn[/quote]
???
SEE wird immer dann aufgerufen, wenn Schlagzüge von Weiss und Schwarz auf ein bestimmtes Feld möglich sind: Player schlägt auf e4, Opponent schlägt auf e4, Player schlägt auf e4 ... solange, bis keine Schlagzüge auf e4 mehr möglich sind. Wenn Player oder Opponent am Zug bereits einen Materialvorteil aus dem Schlagabtausch haben, wird abgebrochen.
Beispiel: Weisse Dame schlägt Bauer auf e4, scharzer Bauer schlägt Dame auf e4, weisser Springer schlägt Bauer auf e4. Schwarz hat jetzt einen Statischen Materialvorteil, der Schlagabtausch wird abgebrochen. Der "Zug weisse Dame schlägt Bauer e4" wird nach hinten sortiert (zwecks der Allgemeinverständlichkeit vereinfachte Beschreibung).
Bei Nichtschlagzügen gibt es - wie der Name schon sagt - keine SEE ( Static Exchange Evaluation = Statische Analyse eines Schlagabtauschs).

By Reinhard Scharnagl Date 2009-08-23 18:34

Wir reden aneinander vorbei. Drum lass' ich's mal.

By Gerd Isenberg Date 2009-08-25 00:12

Ja klar, Karl-Heinz ist ein bisserl zu sehr fixiert auf direkte Schlagzüge. Es sollte Sinn machen, auch bei ruhigen Zügen sie "Sicherheit" des Zielfeldes zu überprüfen, z.B. ganz trivial und billig Einstellen beim Damenzug (oder jeder Figur) mit Zielfeld kontrolliert durch gegnerischen Bauern. Tord meinte mal, SEE für ruhige Züge sei bei ihm kontraproduktiv. Ich denke bei PV-Nodes kann man sicher mehr in die Zugsortierung inverstieren. Bei Cut-nodes machts meisten ein hash- oder killer-zug (wenn nicht Schlagzug), wenn nicht, degeniert er häufig zum All-node, so dass sich ggf. weiterer Aufwand nicht lohnt, und es egal ist, wann man was einstellt. Bei erwarteten All-nodes ist es meist auch egal. Such-Statistik, zählen was wann passiert und Differenzierung der erwarteten Knotenart des minimalen Suchbauems ist da sicher hilfreich.

Wenn man eh (inkrementelle) Attack-tabellen hat, sollte man sie auch "sinnvoll" benutzen, um ihren Aufwand zu rechtfertigen

Bei der (relativen) History Heuristic streiten sich auch die Geister. Manche (Vincent, Bob) meinen die produzieren nur noch Rauschen bei heutigen Suchtiefen. Dann könnte man sie ja eventuell lokaler machen und sie bei PV-Knoten mit Resttiefe X zu löschen, um sie nur weiter unten wirken zu lassen, in etwa Teilbäumen der Grösse, wo die Heuristik früher gut war. Die Idee des Bestrafens von Zügen, die bei einem Cut vorher probiert wurden (RHH), finde ich nett. Ich glaub der Index Trend geht mehr nach Figur und Zielfeld als nach Start und Ziel.

Die Kombination von mehreren Heuristiken (z.B. noch spezielle Piece Square Tables alá Ed Schröder) ist immer tricky und deren Gewichtung scheint eher was für Neuronale Netze zu sein

Gerd

By Karl-Heinz Milaster Date 2009-08-25 10:54

[quote="Gerd Isenberg"]Ja klar, Karl-Heinz ist ein bisserl zu sehr fixiert auf direkte Schlagzüge[/quote]
Nicht wirklich, weil nicht nur ich nach einem Zug aus der HV - wenn einer vorhanden - generell zuerst die Schlagzüge auf die zuletzt gezogene Figur des Gegners (capture of last piece moved, unter Einbeziehung von SEE) untersuche. Damit werden Nichtschlagzüge auf der nächsten Ebene automatisch per SEE untersucht. Ich bezweifle, dass der Vorteil durch eine Untersuchung eines Zielfeldes vor der Zugausführung per SEE messbar ist.

Gruss
khm

By Reinhard Scharnagl Date 2009-08-25 12:22

[quote="Karl-Heinz Milaster"]... Ich bezweifle, dass der Vorteil durch eine Untersuchung eines Zielfeldes vor der Zugausführung per SEE messbar ist ...[/quote]Mir ging es nicht darum, die Effizienz von SEE irgendwie zu verbessern, sondern um meine ursprüngliche Fragestellung.

Ansonsten: es ist ja fast banal, aber eine Figur wirkt dort am wenigsten, wo sie steht. Die Tatsache, dass sie aber (noch) auf ihrem Platz steht, ist meist ein gutes Zeichen, denn andernfalls hätte sie ja bereits geschlagen worden sein. Jeder Zug auf ein anderes Feld schwächt dieses Zielfeld um die Wirkung der darauf ziehenden Figur. Bei einem Schlagzug gibt es auf jeden Fall erst einmal eine Belohnung dafür im Wert der Beutefigur, bei einem ruhigen Zug dagegen nichts. Die Tatsache, dass eine Beute auf dem Zielfeld stand, ist aber im Falle, dass diese schon länger dort stand, eher ein Indiz für deren Abgesichertheit. In beiden Fällen sollte es aber lohnen, sich über das Überleben der Figur auf ihrem neuen Platz Gedanken zu machen.

By Karl-Heinz Milaster Date 2009-08-25 18:15

[quote="Reinhard Scharnagl"] Bei einem Schlagzug gibt es auf jeden Fall erst einmal eine Belohnung dafür im Wert der Beutefigur, ...[/quote]
Genau das soll SEE ja untersuchen. Wenn SEE den Schlagzug nicht verwirft, kann man den Schlagzug ausführen und erhält zusätzlich den Wirkungswert der Beutefigur.
Die Entscheidung, ab der Schlagzug wirklich vorteilhaft war, fällt aber der Suchbaum.
Nun ja, wahrscheinlich redest Du von Äpfeln und ich von Birnen.

Gruss,
khm

By Benno Hartwig Date 2009-08-25 14:57

[quote="Gerd Isenberg"]Es sollte Sinn machen, auch bei ruhigen Zügen sie "Sicherheit" des Zielfeldes zu überprüfen, z.B. ganz trivial und billig Einstellen beim Damenzug (oder jeder Figur) mit Zielfeld kontrolliert durch gegnerischen Bauern. [/quote]Ich denke, ihr seid gar nicht so weit auseinander.
Natürlich macht SEE auch nach einem ruhigen Zug Sinn, wenn eben statisch abgeschätzt wird, ob nicht das Schlagen der gerade ruhig gezogenen Figur für den anderen einen Vorteil verspricht. Trotzdem ist diese Prüfung durch SEE dann eine Abschätzung davon, was eine Folge von Schlagzügen jetzt bringen könnte.

Benno

By Karl-Heinz Milaster Date 2009-08-24 09:15

Wie SEE in für eine Engine programmiert wird, zeigt der Quell-Code (C++) von David Shawul (Scorpio):

Code:

#include "scorpio.h"

#define AddSlider(strt,stp,wrb,brb) {                \
  sq = strt + stp;                        \
  while(board[sq] == empty) sq += stp;              \
    if(sq != from) {                        \
       switch(board[sq]) {                      \
         case wqueen:                        \
         case wrb:                          \
         w_atkers[w_atks++] = sq;                \
         break;                          \
         case bqueen:                        \
         case brb:                          \
         b_atkers[b_atks++] = sq;                \
         break;                          \
     }                              \
  }                                \
}

#define AddHiddenAttacker(strt) {                  \
    step = sqatt[strt - to].step;                  \
    switch(step) {                          \
       case UU:                            \
       case DD:                            \
       case RR:                            \
       case LL:                            \
        AddSlider(strt,step,wrook,brook);              \
        break;                          \
       case RU:                            \
       case RD:                            \
       case LU:                            \
       case LD:                            \
        AddSlider(strt,step,wbishop,bbishop);            \
        break;                          \
  }                                \
}

static const int piece_see_v[15] = {0,99, 9, 5, 3, 3, 1,99, 9, 5, 3, 3, 1,0};

int SEARCHER::see(MOVE move) {
  
  int list[32],n;
  int from = m_from(move),to = m_to(move),sq,score;
  int w_atkers[16],b_atkers[16];
  int w_atks = 0,b_atks = 0;
  int w_count , b_count;
  int col,atkd_val;
  int i,bi,bv,v,step,temp;

    PLIST current;
    /*collect attackers*/
  if (board[to - RU] == wpawn && from != (to - RU)) {
    w_atkers[w_atks++] = to - RU;
  }
  if (board[to - LU] == wpawn && from != (to - LU)) {
    w_atkers[w_atks++] = to - LU;
  }
  if (board[to - RD] == bpawn && from != (to - RD)) {
    b_atkers[b_atks++] = to - RD;
  }
  if (board[to - LD] == bpawn && from != (to - LD)) {
    b_atkers[b_atks++] = to - LD;
  }
  current = plist[wknight];
  while (current) {
    sq = current->sq;
    if (sqatt[to - sq].pieces & NM) {
      if(sq != from)
        w_atkers[w_atks++] = sq;
    }
    current = current->next;
  }

  current = plist[bknight];
  while (current) {
    sq = current->sq;
    if (sqatt[to - sq].pieces & NM) {
      if(sq != from)
        b_atkers[b_atks++] = sq;
    }
    current = current->next;
  }
  AddSlider(to,UU,wrook,brook);
  AddSlider(to,DD,wrook,brook);
  AddSlider(to,RR,wrook,brook);
  AddSlider(to,LL,wrook,brook);
  AddSlider(to,RU,wbishop,bbishop);
  AddSlider(to,LU,wbishop,bbishop);
  AddSlider(to,RD,wbishop,bbishop);
  AddSlider(to,LD,wbishop,bbishop);

  sq = plist[wking]->sq;
  if (sq != from && (sqatt[to - sq].pieces & KM)) {
    w_atkers[w_atks++] = sq;
  }
  sq = plist[bking]->sq;
  if (sq != from && (sqatt[to - sq].pieces & KM)) {
    b_atkers[b_atks++] = sq;
  }

  /*we start by capturing*/
  score = piece_see_v[m_capture(move)];
  atkd_val = piece_see_v[m_piece(move)];
  col = invert(COLOR(m_piece(move)));
  if(col == opponent)
    AddHiddenAttacker(from);

  list[0] = score;
  n = 1;
  w_count  = 0;
    b_count  = 0;
  
  while(true) {
    if((col == white && w_count == w_atks) || 
       (col == black && b_count == b_atks) )
      break;
    
    list[n] = -list[n-1] + atkd_val; 
    n++;
    
    if(col == white) {
      /*get smallest attacker to the front*/
      bi = w_count;
      bv = piece_see_v[board[w_atkers[bi]]];
      
      for(i = w_count + 1;i < w_atks;i++) {
        v = piece_see_v[board[w_atkers]]; 
        if(v < bv) {
          bi = i;
          bv = v;
        }
      }
      if(bi != w_count) {
        temp = w_atkers[bi];
        w_atkers[bi] = w_atkers[w_count];
        w_atkers[w_count] = temp;
      }
      /*add hidden attacker*/
      sq = w_atkers[w_count];
      AddHiddenAttacker(sq);

      atkd_val = bv;
      col = black;
      w_count++;
    } else {
      /*get smallest attacker to the front*/
      bi = b_count;
      bv = piece_see_v[board[b_atkers[bi]]];
      
      for(i = b_count + 1;i < b_atks;i++) {
        v = piece_see_v[board[b_atkers]]; 
        if(v < bv) {
          bi = i;
          bv = v;
        }
      }
      if(bi != b_count) {
        temp = b_atkers[bi];
        b_atkers[bi] = b_atkers[b_count];
        b_atkers[b_count] = temp;
      }
      /*add hidden attacker*/
      sq = b_atkers[b_count];
      AddHiddenAttacker(sq);

      atkd_val = bv;
      col = white;
      b_count++;
    }
  }

  while(--n)
        list[n-1] = min(-list[n], list[n-1]);

  score = list[0];

  return (100 * score);
}

(Warum erscheint der Text hier in italic?)
Da der Quellcode frei verfügbar ist, gehe ich davon aus, dass einer Veröffentlichung hier nichts im Wege steht.

Gruss,
khm

By Gerhard Sonnabend Date 2009-08-25 07:10

[quote="Karl-Heinz Milaster"]
(Warum erscheint der Text hier in italic?)
[/quote]

Kursiv wird ab dieser Stelle ausgelöst, da dort am Ende der Befehl dafür auftaucht.
...
v = piece_see_v[board[w_atkers
...

Viele Grüsse,
G.S.