Problemskak og edb I (fra TD 20) v/ Steen Christensen Tilbage til forsiden

Inden for det sidste år er de fleste to-trækkere publiceret som originalopgaver her i bladet blevet undersøgt for korrekthed af en datamat inden publikation. Som en del af mit datalogistudium på Københavns Universitet har jeg fået antaget et projekt, der som resultat er blevet et program til løsning af to-trækkere. Projektet blev afsluttet i februar 1980, men programmet har været egnet til brug allerede fra omkring sommeren 1979.
Det finder alle løsninger med mat i 2 træk og udskriver disse i udvidet notation, fx. BA7-A8S, SG7xE6 eller 0-0-0. (I det anvendte programmeringssprog NUALGOL er det ikke muligt at udskrive små bogstaver). Den gennemsnitlige løsetid er 5 sekunder, men tallet kan svinge fra 0,1 sekunder til omkring 20. Det indeholder specielle rutiner til de 3 specialtræk rokade, forvandling og en-passant slag. Rokader tillades modsat en-passant slag i førstetrækket i følge gældende kodex.
Programmet har indtil nu testet omkring 150 originalopgaver (og fundet biløsninger i ca. 10 %), og fra vores faglige redaktørs store samling af to-trækkere har det undersøgt 300 opgaver der af den ene eller anden grund er suspekte. Hertil kommer en del testopgaver samt alle to-trækkere publiceret i originalafdelingen siden starten i 1976. Til forfatterne af disse opgaver kan det oplyses at programmet i alle tilfælde fandt den publicerede løsning.
En variant af programmet kan løse selvmatsopgaver i 2 træk. Teknisk skal der kun en mindre ændring til for at det kan lade sig gøre. Selvmatsprogrammet kører på en datamat af typen NCR-8430, og det har testet de 100 opgaver i Georg Thomas "MATTVANG" og indtil nu ca. 20 originalopgaver. Modsat to-træksprogrammet kan det udskrive den totale løsning til og med hvids 2. træk samt undersøge, om der findes skinspil og i bekræftende fald udskrive dette. Man kan således afsløre eventuelle dualer, og opgavens korrekthed kan verificeres fuldstændigt.
At udvide programmerne til også at kunne løse opgaver i mere end 2 træk er simpelt, men tiden til løsningen bliver let stor. Når en datamat bliver hvermands eje vil tidsproblemet blive elimineret, idet man kan lade den løse opgaver om natten og i påkrævende tilfælde i dagevis.
En to-trækker kræver i gennemsnit undersøgelse af 2000 træk og en selvmat omkring 10.000. Hvis man vil løse en hjælpemat i 2 træk med 30 træk fra hver side og 4 skakgivende i matdybden, vil et program skulle undersøge over 100.000 træk, da alle varianter nødvendigvis må undersøges. I de to andre typer af opgaver kan man spare undersøgelse af en lang række træk, fx. vil ligegyldige hvide førstetræk ofte strande på det samme sorte svar. Ved at undersøge varianter, der starter med dette sorte træk før alle andre, vil man kunne undlade at forsøge disse overhovedet, hvis førstetrækket allerede er fejlet på det stærke sorte træk. I den rapport der er skrevet i forbindelse med projektet er omtalt 5 lignende afkortningsmuligheder men pladsen her tillader ikke en nærmere omtale.
Programmer til løsning af opgaver har været brugt i omkring 20 år. I 1962 udviklede C. Bandelow et program til løsning af to-trækkere, og siden har Wolf (65), Veenker (65), Bell (70) og Manning (71) publiceret artikler der beskriver hver deres algoritme. Løsetiderne for disse kan måles i minutter, men det skyldes sikkert ikke algoritmerne, men at datamaterne er blevet væsentlig hurtigere siden da. Mere mærkeligt er det, at kun Bell har valgt at medtage de 3 specialtræk i sit program.
Mange andre typer af opgaver inden for problemskakken kan undersøges ved hjælp af en datamat. H.Mertes har således foretaget en fuldstændig beregning af alle korrekte hjælpematter med materialet K . S mod K . S. I alt findes 5.273 stillinger, som Mertes har udgivet under pseudonymet D. Relp. Enhver der mener at finde en publiceringsværdig stilling i denne samling må gøre det under eget navn, blot der tilføjes "Ex D. Relp". I THEMA DANICUM har vi set et eksempel på en sådan opgave (nr. 380).

Diagram 1
H. Mertes
Schach-Echo 1974
H#7 2+2

Opgave 1 viser den stilling, som Mertes selv finder er det bedste resultat. Løsningen er: 1 Ke6 Kd3 2 Kd5 Ke3 3 Kc4 Kd2 4 Kb3 Sd4+ 5 Ka2 Kc3 6 Ka1 Kb3 7 Sb1 Sc2#. Mertes har endvidere undersøgt alle hjælpematter med materialet K . S mod K . T og K . S mod K . G (græshoppe), og senest har T. Ströhlein og L. Zagler foretaget en fuldstændig analyse af slutspil med K . T mod K og K . T mod K . L.
Det gamle problem med beherskelse af skakbrættets 64 felter med de 8 hvide officerer blev endelig løst på en datamat. Man var længe i tvivl om det var muligt at dække alle felter, og Gregers Jensen publicerede i flere omgange 135 stillinger med dækning af 63 felter i det hedengangne STELLA POLARIS.

Diagram 2
T. R. Dawson & P. Frey
British Chess Magazine 1938
Ugarderet felt: a1 8+0

Nr. 2 viser den stilling, der i Jensens nummerering har nummer 1. Det endelige resultat, nemlig at det kun er muligt at gardere 63 felter og at der i alt findes 144 stillinger (spejlinger og drejninger undtaget) blev fundet af Walter Franz og Wilhelm Hackmann.

Diagram 3
Kilde ukendt
Gengivet i Schach und Zahl
8+0

Først med datamatens fremkomst blev det muligt at verificere, at problemet med placering af 8 dronninger på en sådan måde, at ingen kan slås, havde præcis 92 løsninger. Man var længe sikre på at dette tal var korrekt, men forsøg på at bevise tallet matematisk er mislykkedes. Den eneste stilling, som ved drejning af brættet 90, 180 og 270 grader giver den oprindelige stilling er vist som opgave nr. 3.

Donald Knuth har fremstillet et program, som kan finde samtlige ikke-krydsende springervandringer på kvadratiske brætter op til 8x8. Han fandt 2 på 3x3 brættet med længden 2, 5 på 4x4 med længden 5, 4 på 5x5 med længden 10, 1 på 6x6 med længden 17, 14 på 7x7 med længden 24 og endelig 4 på 8x8 med længden 35.
I STELLA POLARIS nr. 4/1971 stillede K. Fabel følgende gamle opgave (4331): Hvor mange forskellige trækserier findes der, når hvid og sort fra partiudgangsstillingen hver foretager 2 træk? Man havde indtil da antaget, at tallet var 197.299, men L. Zagler lavede et program som dokumenterede, at tallet faktisk "kun" er 197.281 trækserier. Samme resultat kom en række finske problemister til med deres eget program, som de yderligere lod undersøge antallet af trækserier til og med hvids 3. træk. De fandt tallet 4.865.609. Sådan kan man fortsætte, men til sidst bliver tidsforbruget for stort, hvilket også var grunden til at Knuth stoppede ved 8x8 brættet. Yderligere resultater er vel også i begge tilfælde uden egentlig interesse.
Den eneste begrænsning for hvad der kan undersøges på datamat er tiden. Løsere af nytårskonkurrencen havde mulighed for at gruble længe over nr. 1148, hvor man skulle placere 8 dronninger på en sådan måde, at 11 felter forblev ugarderede. Selv brugte jeg over 20 timer. En øvre grænse for placering af de 8 dronninger er 64! Divideret med 56! (64x63x62x61x60x59x58x57), svarende til 1.78x10 i 14. Potens forskellige placeringer. Selv om man kan dividere dette tal med 8!, da dronningerne er ens, og yderligere udelukke spejlinger og drejninger, vil antallet af undersøgelser blive stort, selv for en datamat. Jeg vil slutte denne artikel med en opgave, som er komponeret ved hjælp af en datamat. Opgave nr. 4. Steen Christensen, original.

De efterfølgende 6 spørgsmål bygger alle på stillinger med sort konge omgivet af de øvrige 7 sorte officerer (DTTLLSS). Et skemaeksempel er vist som opgave nr. 5.

Diagram 5
Skemaeksempel
0+8

Bemærkninger til opgaven: A og B er rent matematiske og kan løses uafhængigt af de øvrige. En løsning til C vil med den sorte stilling fra skemaeksemplet være 1 Ta4 d8S 2 Tb4 Sb7#. For C-F skal alle stillinger fundet som svar på B undersøges for at man kan være sikker på, at maksimum er fundet. Generelt anses kun stillinger udelukkende indeholdende sorte switchbacks for legale. I opgave nr. 5 vil tilføjelse af hBd7 og hKh8 bl.a. give løsningen 1 Sf5 d8S 2 Sd6 Se6#. Da denne trækfølge ikke indeholder sort switchback kan placeringen af hvid konge på h8 ikke være maksimal for den viste gruppering af de sorte officerer. Med hKh4 er det derimod muligt da Sf5 giver skak. I C-F skal kun betragtes hvide bondeforvandlinger til springer.

  1. På hvor mange måder kan de 7 sorte officerer placeres omkring kongen (ensfarvede løbere er ikke tilladt), når det ubesatte felt holdes fast?
  2. Tilføj en hvid bonde på d7. Hvid kan nu trække d8S efterfulgt af Sb7+. Hvor mange af de under A fundne stillinger giver efter denne trækfølge mat?
  3. Tilføj yderligere den hvide konge på h8. Hvilken af de under B fundne stillinger giver med fordringen H#2 det højeste antal løsninger med sorte switchbacks?
  4. Fjern den hvide konge fra h8. Hvor skal den i stedet placeres for med fordringen H#2 at give det højeste antal løsninger med sorte switchbacks?
  5. Fjern de hvide brikker. Hvor skal den hvide bonde (og dermed det ubesatte felt) og den hvide konge placeres for, stadig med sort konge på c5, at give det højeste antal løsninger med sorte switchbacks i en H#2?
  6. Hvor skal den sorte konge, omgivet af de 7 officerer, den hvide bonde og den hvide konge placeres for at give det højeste antal løsninger med sorte switchbacks i en H#2?