0x88

0x88 schackbrädesrepresentationen är en kvadratcentrisk metod för att representera schackbrädet i datorschackprogram . Talet 0x88 är ett hexadecimalt heltal (136 ₁₀ , 210 ₈ , 10001000 ₂ ). Rang- och filpositionerna representeras var och en av en nibble (hexadecimal siffra), och bitluckan förenklar ett antal beräkningar till bitvisa operationer .

Layout

I 0x88-bräderepresentationen är layouten utspridd för att täcka ett 8-av-16-bräde, lika med storleken på två intilliggande schackbräden. Varje ruta i 8-av-16-matrisen tilldelas ett nummer som kan ses i tavlans layouttabell. I detta schema representerar varje nibble en rang eller en fil, så att 8-bitars heltal 0x42 representerar kvadraten vid (4,2) i nollbaserad numrering, dvs. c5 i standard algebraisk notation .

Att lägga till 16 till ett tal för en kvadrat resulterar i talet för kvadraten en rad ovanför, och subtrahering av 16 resulterar i talet för kvadraten en rad nedanför. För att flytta från en kolumn till en annan ökas eller minskas antalet med en. I hexadecimal notation är lagliga schackpositioner (A1-H8) alltid under 0x88. Denna layout förenklar många beräkningar som schackprogram behöver utföra genom att tillåta bitvisa operationer istället för jämförelser.

0x88 kortlayout
	0x00 (a)	0x01 (b)	0x02 (c)	0x03 (d)	0x04 (e)	0x05 (f)	0x06 (g)	0x07 (h)	0x08	0x09	0x0A	0x0B	0x0C	0x0D	0x0E	0x0F
0x70 (8)	70	71	72	73	74	75	76	77	78	79	7A	7B	7C	7D	7E	7F
0x60 (7)	60	61	62	63	64	65	66	67	68	69	6A	6B	6C	6D	6E	6F
0x50 (6)	50	51	52	53	54	55	56	57	58	59	5A	5B	5C	5D	5E	5F
0x40 (5)	40	41	42	43	44	45	46	47	48	49	4A	4B	4C	4D	4E	4F
0x30 (4)	30	31	32	33	34	35	36	37	38	39	3A	3B	3C	3D	3E	3F
0x20 (3)	20	21	22	23	24	25	26	27	28	29	2A	2B	2C	2D	2E	2F
0x10 (2)	10	11	12	13	14	15	16	17	18	19	1A	IB	1C	1D	1E	1F
0x00 (1)	00	01	02	03	04	05	06	07	08	09	0A	0B	0C	0D	0E	0F

Algebraisk notation och konvertering

Rutor på ett schackbräde med algebraisk notation

Den moderna standarden för att identifiera rutorna på ett schackbräde och drag i ett spel är algebraisk notation , där varje ruta på brädet identifieras av ett unikt koordinatpar - en bokstav mellan a och h för den horisontella koordinaten, känd som filen, och ett tal mellan 1 och 8 för den vertikala koordinaten, känd som rang.

I datorschack representeras filrankningskoordinater internt som heltal som sträcker sig från 0 till 7, med fil en mappning till 0 till fil h mappning till 7, medan rangkoordinaten skiftas ned med en till intervallet 0 till 7.

En fördel med 0x88-kodningsschemat är att värden enkelt kan konverteras mellan 0x88-representation och filrankningskoordinater med endast bitvisa operationer , vilket är enkla och effektiva för datorprocessorer att arbeta med. Så här konverterar du en nollbaserad filrankningskoordinat till ett värde av 0x88:

{\text{square}}_{0{\rm {{x}88}}}=({\text{rank} }_{\text{0 till 7}}<<4)+{\text{fil}}_{\text{0 till 7}}

Således motsvarar a 1 $\displaystyle 00000000_{2}}$ { , med alla 8 bitarna inställda på ${\displaystyle 0} ,$ b 2 motsvarar $00010001_{2}$ , till $01110111_{2}$ .

Så här konverterar du ett 0x88-värde till ett filrankningskoordinatpar:

{\text{fil}}_{\text{0 till 7}}={\text{kvadrat}}_{0{\rm {{x}88} }}\ \&\ 7

{\text{rank}}_{\text{0 till 7}}=({\text{square}} _{0{\rm {{x}88}}}\ >>4)

Obs: I formlerna ovan representerar << och >> vänster och höger logiska bitskiftsoperationer respektive medan & representerar bitvis och .

Ansökningar

Off-the-board detektering

Detektering utanför brädet är en funktion i schackprogram som avgör om en pjäs är på eller utanför det lagliga schackbrädet. I 0x88 representerar den högsta biten av varje napp om en pjäs finns på brädet eller inte. Närmare bestämt, av de 8 bitarna för att representera en kvadrat, måste den fjärde och den åttonde båda vara 0 för att en bit ska finnas inom brädet. Detta möjliggör detektering utanför kortet genom bitvis och operationer. Om $square AND 0x88 (eller, binärt, 0b10001000 ) inte är noll, så finns inte kvadraten på brädet. Denna bitvisa operation kräver färre datorresurser än heltalsjämförelser. Detta gör beräkningar som olaglig rörelsedetektering snabbare.

Kvadratiska relationer

Skillnaden mellan giltiga 0x88 koordinater A och B är unik med avseende på avstånd och riktning, vilket inte är sant för klassiska packade trebitars rang- och filkoordinater. Det gör sökningar efter Manhattan-avstånd , möjliga pjäsattacker och lagliga pjäsrörelser mer resursvänliga. Medan klassiska kvadratkoordinater i intervallet 0–63 kräver 4K-stora tabeller (64×64), tar skillnaden 0x88 1/16 av det eller 256-stora tabeller – eller till och med 16 mindre.

En offset på 119 (0x77 som maximalt giltigt kvadratindex) läggs till för att göra ±119 till ett intervall på 0–238 (en storlek på 240 av justeringsskäl).

0x88Diff = 0x77 + A − B

Adoption

Även om 0x88-representationen från början var populär, har den mestadels ersatts av systemet med bitbrädor .

Anförda verk

Hyatt, Robert (2013). "Representationer för schackprogramstyrelsen" . Arkiverad från originalet den 12 februari 2013 . Hämtad 6 mars 2020 .
Reul, Fritz Max Heinrich (2009). Nya arkitekturer inom datorschack (Thesis). Gildeprint, TICC Dissertation Series 6. ISBN 9789490122249 .
Østensen, Emil Fredrik (Hösten 2016). Universitetet i Oslo (PDF) (Master i programmering och nätverksuppsats). Universitetet i Oslo.
Moreland, Bruce (2007-07-16). "0x88 Move Generation" . Arkiverad från originalet 2007-07-16 . Hämtad 2020-03-12 .
Schalk, Andrea (7 augusti 2008). "COMP30191 Teorin om spel och spelmodeller" (PDF) . University of Manchester Institutionen för datavetenskap . Hämtad 2020-03-18 .
Keen, Ben (november 2009). "En historia om datorschack" (PDF) . Laboratoire Bordelais de Recherche en Informatique . Arkiverad från originalet (PDF) 2020-03-23 . Hämtad 2020-03-23 .
Dagligen, Paul; Gotojuch, Dominik; Henning, Neil; Lawson, Keir; Macdonald, Alec; Tajaddinov, Tamerlan (18 mars 2008). "Chess Mantis A Chess Engine" . Hämtad 2020-03-23 .

externa länkar

Schackbrädesrepresentationer av Robert Hyatt
Hur Zarkov spelar schack arkiverad 2020-08-19 på Wayback Machine av John Stanback
0x88-representationen från Mediocre Chess Arkiverad 2018-08-20 på Wayback Machine av Jonatan Pettersson