For further study: minor/temporary thoughts - Sorting answers (by heuristic): Since in most cases only the first of all the defender moves gets executed, we may save the sorting effort, and just find the best move in a linear scan. Sorting will be done only, if that best answer was not sufficient. For this, attributizing by answer heuristic, and sorting must to be separated. - analyse() should return a found solution always. This enables analysis of the solution in order to find a better move for the defender. - fac_km_dirs: use escape position of king ? - Wenn K+X gegen K+D gewinnen soll, und der Verteidiger ist dran, dann hat er oft eine Gabel: Schach dem K und Schlag dem X. Wenn der K die D nicht schlagen kann (kein nahes Schach), und der X die D nicht schlagen kann, und nichts zwischen D und X steht, so ist anschliessend X weg, und damit der K nackt: - entweder der K bewegt sich, dann ist der X noch dort, wo die D ihn schlagen kann - oder X bewegt sich, was also eine Blockade des Schach sein muss, so dass die D sogar mit Schach schlagen kann. Ist die D durch X gefesselt, kann X sofort geschlagen werden. ==> b_fig_set implementieren (hilft hier weiter) - Wenn K+X+Y gegen K+D gewinnen soll, und der Verteidiger ist dran, dann hat er manchmal eine Schlag-gabel: + D schlaegt X und sagt Schach und attackiert Y. Wenn das ein legaler Zug ist, und das Schach nicht durch das Schlagen von D zu beantworten ist, dann wird anschliessend die D den letzten Angreifer Y schlagen. Achtung: Zwischen-Matt/-Patt. - Hilfsmatt (helpmate): S. Anregung von Norbert Geissler: Moegliche Zielpositionen fuer sK aufzaehlen, und beschraenkte Suche durchfuehren. Vielleicht alle Zielpositionen erzeugen, und mit Abstandsfunktion arbeiten? Probleme: Umwandlung/Rochade/e.p. Vereinfachung: wenn gar keine B da (und keine Rochade) haben wir nur einfache Zuege (Startfeld->Zielfeld). Schwierig: was ist mit Gedaechtnis? Die Beschraenkung darf da nicht rein. - Hilfsmatt: h#1: muss oft ein Schach vorbereiten. Das kann besser vor dem Zug geprueft werden, ob es eine Moeglichkeit geben wird. - Hilfsmatt: Nur noch K+BBB zum Mattsagen: Tabelle fuer kuerzest moegliches kooperatives Schach: fastest_koop_check: Seite * 64 * 64 -> plies Dito fuer S. Das kann sogar vor einem K-Zug von Schwarz geprueft werden. - Mate finder mode: jede, noch so tiefe Loesung ist akzeptabel. Problem: wie haelt man die im Gedaechtnis fest? (Damit man die Loesung auch tief genug ausgeben kann) - restricted mate finder mode: Bei der Suche nach der Loesung nur Angreifer Zuege betrachten, auf die entweder Matt in k folgt, oder hoechstens m legale Antworten. Das sollte den untersuchten Baum schmal halten. - Killer-Heuristik: aber wie? - Begriff "Line": jedes Feld befindet sich auf je einer aus 4 Klassen von Linien: - senkrecht (1 aus 8) - waagerecht (1 aus 8) - aufsteigende Diagonale (1 aus 15) - absteigende Diagonale (1 aus 15) Fasst man die Diagonalen einer Art mit Laenge <= 4 zusammen (schmeisst also 20 der 64 Felder in einen Topf (<1/3)), hat man auch bei den Diagonalen nur 1 aus 8 und insgesamt 32 Linien. Idee zur Benutzung: zwei Positionen, die keine Linie gemeinsam haben, koennen auch keine D-Beziehung haben. Das kann Attack-Abschaetzungen verbessern, die so weit von der momentanen Position weg sind, dass jetzt noch keine aktuellen Attack-Bits da sind. Tabelle: Pos64 -> SetOf(Linie) == uint32 - Im "Field" redundant halten, welche Bauern dahin ziehen koennen. Von jeder Farbe kann das hoechstens einer sein. Moeglich waere also ein int8 f_bmvidx[2]; /* [colour]: which B can move here */ Unklar: wenn das Feld besetzt ist, wie ist dann der Wert? Folge: einige Blockade-Abschaetzungen werden vereinfacht/ermutigt. - Konzentriere OS-Abhaengigkeiten. - Interface fuer Produktion? Kann ja wohl kaum mit IPC passieren. Wie sieht das also aus? - acm: Spare xboard durch Kodierungs-Tricks? Neben BSLTDK und leer ist noch ein Kode 7 frei. Z.B. kann ein ep-faehiger Bauer als 7 kodiert werden. Und eine erlaubte Rochade durch einen K statt des beteiligten T. Problem: update-Operationen auf diesen Tricks sind komplizierter. - Kompaktes LegalDelta? Tabelle LegalDelta -> LegDelInx Hilft, andere Tabellen zu kompaktieren. - Special Figure codes for white and black bauer (after normal codes): More specific attack info etc. Sometimes even better: special case for promotion/non-promotion. - Solution tree more compact: (a) Mehrfach auszugebende Subbaeume, die gross genug sind, benennen und mehrfach referenzieren. (b) Wenn Baum zu gross, aber mind. ein Top-Level-Zug komplett, Top-Level-Breite raufziehen, bekannte Unterbaeume ausgeben, Platz machen, Rest neu versuchen. (c) Auf Mattzug-Ebene optional auf Duale verzichten, und den jeweils haeufigsten Mattzug waehlen: kann wesentlich kuerzer werden. Evtl. darauf umschalten, wenn grosse Loesung. Evtl. Indikator am Ende, z.B. "etc" Sonst Probleme mit Monster-grossen Loesungen. Statistik(solopt) nach kompletter Loesung ausgeben (nodes/fails/saved) - solopt: vielleicht nuetzt es (bei grossen Loesungen), erst moeglichst viel Information in der Breite zu erschnuppern, bevor wir wirklich in die Tiefe gehen, und Knoten rausschmeissen, die wir gebraucht haetten. - Feld-Redundanz: PieceSet der aktuellen Figuren (konditional mit #def). - mate2: wenn A im Schach: haben wir da was von? Den zweiten Zug pseudo-legal abzuschaetzen ist hier etwas grob, oder? Statistik dafuer machen (wie oft). - mate2: Wenn V-K voellig frei, d.h. |E|==9 (was 33% haeufig sein kann), geht das dann nicht schneller zu verifizieren? --> Statistik ueber die verbleibenden Freiheiten fuer den letzten Zug. - apx_cost/apx_ovhd: Sollte das nicht bei PROD_LEV=2 fehlen? --> Mache spezielles #def & Makro: WITH_APX und ON_APX(body) - E25-Konzept: 5*5 Environment []: Pos64 --> E25Set (uint32) []: dir*dir --> E25Inx (uint8) --> use currently best to cut off computation (like alpha cut) - acm: allow hash 0, forbid e.g. info==0 Problem: beim Suchen ist der Hash das erste was man anfasst. Kodiert man einen freien Slot anders als durch den Hash, muss man stets noch einen zweiten Slot betrachten. Loesung evtl: das wieder nur, wenn der Hash tatsaechlich 0 ist. - acmsize.h: Extract configuration into local file "acmconf.h". ACM_SLOTS/ACM_MEGS Even better: *compute* a prime ACM_SLOTS for an ACM_MEGS value and with sizeof(AcmNode). - inited.h: Also create some h-file with #defs, e.g. for the constant value of "fig_cov[dame]". - sol*.c: If a solution requires to end in mate, try to replace chess marks '+' by '#', where it is a mate move. - move.c: Das staendige rauf- und runter-zaehlen der Piece- und Fig-orientierten Zaehler ist nicht noetig, solange kein lazy up/down-date erfolgt. Die Anzahl der Pieces der ziehenden Farbe aendert sich nie. Eine Aenderung der Material-Verteilung (der ziehenden Seite) gibt es nur bei Umwandlungen. Sowas kann also zusammengefasst/eliminiert werden. Muss aber sorgfaeltig auf das Down-Date-Konzept abgestimmt werden: dort sind die Kommandos low level und werden auch fuer Rochade und ep-Schlag usw. benutzt. - anti-Patt kann genauso gut sein, wie Anti-Matt. - Solution-Tree in HTML: Links fuer "next/prev" brother. - K vs K and many same coloured bishops: cannot mate (but stalemate).