Shakista IV

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Likimain kerran vuodessa on palannut shakin syövereihin, vaikka shakki sinällään ei ole niin kiinnostava, paitsi ALGORITMINA.

Vuosi vuodelta uudelleen suunniteltuna ydinkoodi on lyhentynyt kohti A4:sta. Lyhyt koodi rekursiossa on aina tehokkaampi.

Laitan koodin oheen, jotta abskissa voi arvostella kommenttien vähyyttä, ja muita puutteita

[code:jssjwgqx]int A[64];
int C[32];

int MaxDeep=9;
int balance=0;

int whiteMove(int);
int blackMove(int);

inline void whiteRoutine(int &max, int i, int pin,
int from, int to, int tmp, int deep)
{
int x, mux;

if (tmp)
{
balance-=tmp>>16;
C[x=(tmp>>6)&31]=64;
}

C[i]=to;
A[to]=pin;

mux=deep
if (mux>max) max=mux;

if (tmp)
{
balance+=tmp>>16;
A[to]=tmp;
C[x]=to;
}
else A[to]=0;
}

inline void blackRoutine(int &min, int i, int pin,
int from, int to, int tmp, int deep)
{
int x, mux;

if (tmp)
{
balance-=tmp>>16;
C[x=(tmp>>6)&31]=64;
}

C[i]=to;
A[to]=pin;

mux=deep
if (mux

if (tmp)
{
balance+=tmp>>16;
A[to]=tmp;
C[x]=to;
}
else A[to]=0;
}

int whiteMove(int deep)
{
char *os;
int from, to;
int max=PIENIN;
int i, j, pin, tmp;

for (i=0; i<32; i+=2)
if ((from=C[i])<64)
{
pin=A[from];
A[from]=0;

if ((pin&SOTILAS)!=SOTILAS)
{
os=MV[B8[(pin&15)|(from<<4)]];
for (; *os<64; os+=8)
{
for (j=0; os[j]<64; j++)
{
if ((tmp=A[to=os[j]])&WhBit) break;
whiteRoutine(max, i, pin, from, to, tmp, deep);
if (tmp) /* ------------- */ break;
}
}
}

A[from]=pin;
C[i]=from;
}
return max;
}

int blackMove(int deep)
{
char *os;
int from, to;
int min=SUURIN;
int i, j, pin, tmp;

for (i=1; i<32; i+=2)
if ((from=C[i])<64)
{
pin=A[from];
A[from]=0;

if ((pin&SOTILAS)!=SOTILAS)
{
os=MV[B8[(pin&15)|(from<<4)]];
for (; *os<64; os+=8)
{
for (j=0; os[j]<64; j++)
{
if ((tmp=A[to=os[j]])&BlBit) break;
blackRoutine(min, i, pin, from, to, tmp, deep);
if (tmp) /* ------------- */ break;
}
}
}

A[from]=pin;
C[i]=from;
}
return min;
}
[/code:jssjwgqx]

Eny way, kaikkien upseerien liikkumissäännöt on ympätty samaan data-taulukkoon. (else osaan tulee joskus sotilaiden liikkumisen säännöt.)

Hiljainen tavoite on luoda shakkialgoritmi, joka nousisi joskus kaikissa ranking-listoilla ykköseksi. Mutta jo Rybkan upseeripelivoitossa on riittävästi tavoitetta.

Ellei sitä pysty kellistämään, on aivan turha ruveta kyhäämään yhtään enempää. Testauksessa olen käyttänyt suorastaan räjähtävää upseerialkuasemaa:

[code:jssjwgqx]char __xx_init[64]=
{
/* |---|---|---|---|---|---|---|---| */
/* | H | G | F | E | D | C | B | A | */
/* |---|---|---|---|---|---|---|---| */
/**/'T',' ',' ','K','D',' ',' ','T', // 1
/* |---|---|---|---|---|---|---|---| */
/**/'L',' ',' ','R','R',' ',' ','L', // 2
/* |---|---|---|---|---|---|---|---| */
/**/' ',' ',' ',' ',' ',' ',' ',' ', // 3
/* |---|---|---|---|---|---|---|---| */
/**/' ',' ',' ',' ',' ',' ',' ',' ', // 4
/* |---|---|---|---|---|---|---|---| */
/**/' ',' ',' ',' ',' ',' ',' ',' ', // 5
/* |---|---|---|---|---|---|---|---| */
/**/' ',' ',' ',' ',' ',' ',' ',' ', // 6
/* |---|---|---|---|---|---|---|---| */
/**/'l',' ',' ','r','r',' ',' ','l', // 7
/* |---|---|---|---|---|---|---|---| */
/**/'t',' ',' ','k','d',' ',' ','t', // 8
/* |---|---|---|---|---|---|---|---| */
};[/code:jssjwgqx]

Tämän ketjun viimeisenä pelaan viimeistelyllä koodilla Rybkaa vastaan. Jossain senkin rajat ovat. Vertailun vuoksi huippushakin pelaaja pystyy plaraamaan yli 16 puolisiirtoa asemaa eteenpäin.

Sivut

Kommentit (16)

Vierailija

Totaalinen OT, mutta kiinnostaisiko sinua lähteä pelaamaan Bridgeä nettipelinä partnerina kanssani?

Shakki on suhteellisen yksinkertainen peli Bridgeen verrattuna. Shakissa en pärjää, koska kaikki siinä on nykyisin jo pelattu (muutamaa keskisiirtoa lukuun ottamatta), mutta Bridge on aivan uutta jako kerrallaan.

Kutsuni koskee siis aivan kaikkia, Bridgenpelaajia paikalla?

Vierailija

Miksi tuossa on erkikseen aliohjelmat whiteMove ja blackMove kun ne ovat kuitenkin samat? Voisihan aliohjelmat olla tyyppiä move(boolean white, int deep)

Heksu
Seuraa 
Viestejä5463
Liittynyt16.3.2005
Lyde
Miksi tuossa on erkikseen aliohjelmat whiteMove ja blackMove kun ne ovat kuitenkin samat? Voisihan aliohjelmat olla tyyppiä move(boolean white, int deep)



Ihmettelin ihan samaa.

Vierailija
Lyde
Miksi tuossa on erkikseen aliohjelmat whiteMove ja blackMove kun ne ovat kuitenkin samat? Voisihan aliohjelmat olla tyyppiä move(boolean white, int deep)

Niin, voisivat kaiketi olla yhdet ja samat aliohjelmat vaikka näytäänkin käytettävän eri muuttujia min ja max valkeille ja mustille ... mutta, tietämättä tarkemmin millainen muusta ohjelmasta on tulossa niin voihan tuo tuollaisena olla parempikin, sillä eihän ohjelmakoodin lyhyyden optimointi ole sama asia kuin esimerkiksi nopeuden optimointi.

Vierailija

Juuri niin. Minimi ja maksimi sisältävät eri alkuarvot ja ja eri vertailut.

Kyllähän nuo luupit saisi ängettyä samaankin funktioon, ja vielä simuloida rekursio for-luupissa. Käytäntö on kuitenkin osoittanut, että on helpompi hallita koodi, kun mustalle ja valkealle on omat funktiot (double-rekursio).

Myös for-luupin käyttäminen rekursion sijasta antaa niin minimaalisen nopeuslisäyksen, ettei silläkään kellojaksot kummoisesti pienene, ainoastaan koodin kompleksisuus ja luettavuus lähentelee koodisillisalaatin maksimia.

ed: Ja vielä Phonylle, Shakin sielun on sanottu olevan sotilaissa. Minun mielestä shakin sielu on sellaisessa huippusommittelussa, että kaikki nappulat on tarjottu vastustajalle syötäväksi. Illuusio paljastuu vasta sitten, kun vastustaja rupeaa ottamaan uhrauksia vastaan. Tällaista shakkia ei ole olemassa, eikä niitä montaa ole pelattu. Vaan aina sitä iän ikuista nysväämistä palikoilla, jossa nappulat ja asema on enemmän staattinen kuin dynaaminen.

jjw
Seuraa 
Viestejä518
Liittynyt20.9.2010
_jone_

...

Tämän ketjun viimeisenä pelaan viimeistelyllä koodilla Rybkaa vastaan. Jossain senkin rajat ovat. Vertailun vuoksi huippushakin pelaaja pystyy plaraamaan yli 16 puolisiirtoa asemaa eteenpäin.




16 puolisiirtoa tarkoittaa valikoitua siirtosarjaa.
Tähän ja parempaan pystyvät selektiiviset algoritmitkin.

Vierailija

Niinpä. Tuohon brute-forcen oheen olen kirjoittanut eräänlaisen kiihdyttimen, joka plaraa vaikka 32 puolisiirtoa käden käänteessä. Ei siihen mitään selektiivisyyttä tarvita.

Homma vain heittää silloin tällöin (usein) härän persettä, jolloin koodissa on vielä bugi/bugeja. Kiihdyttimen rivimäärä on suunnilleen kolminkertainen raakaan brute-forceen nähden.

Bugit saa aina korjattua. Kerran jouduin mallintamaan ARM:in prosessorin, jonka simulaatio bongasi bittivirheen, joka sattui suunnilleen 1/miljoona välein. Sellaisessa koodivirheessä debugerit ovat melko voimattomia.

Mene ja tiedä. Mutta virheettömän koodin pitäisi ainakin periaatteessa antaa jonkinlaista vastusta Rybkalle, koska puolisiirtoja alkaa olemaan yhtä paljon sillä erolla, että toinen tutkii kaiken, ja toinen vain pienen määrän potentiaalisia muunnelmia.

Vierailija

No niin. Nyt ohjelma suoltaa melko järkevän tuntuisia siirtoja. Laitan oheen koodin, jolla tahtoo sanoa sitä, ettei shakkialgoritmi kovin montaa efektiivistä funktiota tarvitse.

Minun koodeja ei yleensä osaa lukea kukaan, vaan sen todetaan olevan musta laatikko, joka joko toimii tai ei toimi. Tämän vuoksi toimenkuvassa on paljon koodeja, jotka tutkivat jotain probleemaa, ja finaalissa on valmiit tulokset Wordilla kirjoitettuna, joka on sitten perusteellinen.

Noita koodinpaskoja koodataan enemmän kuin tarpeeksi. Koska Kiinalaisilla ei vielä paljon ole tietokoneita, siellä kaverit koodaavat kynällä ja paperilla. Homma tulee leviämään käsiin, ja joskus muutaman vuoden perästä kaikki koodit väännetään Kiinassa. Kannattaa siis hankkia muitakin ammatteja, koska IT-firmat tulevat kaatumaan yksi toisensa perään.

Mutta pitää tässä joku ilta peluuttaa Rybkaa vastaan. Häviö ei lannistaisi lainkaan, koska 2011 versio on vasta piirustuslaudalla.

[code:1mxd6vnh]#pragma hdrstop

#include
#include
#include
#include
#include

#define LAHETTI 0x01
#define TORNI 0x02
#define DAAMI 0x03
#define RATSU 0x04
#define KAARLE 0x08
#define SOTILAS 0x0c

#define WhBit 0x10
#define BlBit 0x20

#define SUURIN 0x7f7f7f7f
#define PIENIN 0x80808080

#include "data.hpp"

int A[64];
int C[32];
int F[256];
int balance=0;

#include "modul1.cpp"
#include "setpos.cpp"

int whMove(int);
int blMove(int);

inline void whiteRoutine(int &max, int i, int pin, int from, int to, int tmp, int deep)
{
int x, mux;

if (tmp)
{
balance-=tmp>>16;
C[x=(tmp>>6)&31]=64;
}

C[i]=to;
A[to]=pin;

mux=deep
if (mux>max) max=mux;

if (tmp)
{
balance+=tmp>>16;
A[to]=tmp;
C[x]=to;
}
else A[to]=0;
}

inline void blackRoutine(int &min, int i, int pin, int from, int to, int tmp, int deep)
{
int x, mux;

if (tmp)
{
balance-=tmp>>16;
C[x=(tmp>>6)&31]=64;
}

C[i]=to;
A[to]=pin;

mux=deep
if (mux

if (tmp)
{
balance+=tmp>>16;
A[to]=tmp;
C[x]=to;
}
else A[to]=0;
}

int whMove(int deep)
{
char *os;
int from, to;
int max=PIENIN;
int i, j, pin, tmp;

for (i=0; i<32; i+=2)
if ((from=C[i])<64)
{
pin=A[from];
A[from]=0;

if ((pin&SOTILAS)!=SOTILAS)
{
os=MV[B8[(pin&15)|(from<<4)]];
for (; *os<64; os+=8)
{
for (j=0; os[j]<64; j++)
{
if ((tmp=A[to=os[j]])&WhBit) break;
whiteRoutine(max, i, pin, from, to, tmp, deep);
if (tmp) /* ------------- */ break;
}
}
}

A[from]=pin;
C[i]=from;
}
return max;
}

int blMove(int deep)
{
char *os;
int from, to;
int min=SUURIN;
int i, j, pin, tmp;

for (i=1; i<32; i+=2)
if ((from=C[i])<64)
{
pin=A[from];
A[from]=0;

if ((pin&SOTILAS)!=SOTILAS)
{
os=MV[B8[(pin&15)|(from<<4)]];
for (; *os<64; os+=8)
{
for (j=0; os[j]<64; j++)
{
if ((tmp=A[to=os[j]])&BlBit) break;
blackRoutine(min, i, pin, from, to, tmp, deep);
if (tmp) /* ------------- */ break;
}
}
}

A[from]=pin;
C[i]=from;
}
return min;
}

void whFirstMove(move *M, int M_kpl)
{
int i, n, x;
int pin, tmp;
int from, to;

for (n=0; n
if (M[n].balance>0)
{
from=M[n].from;
to=M[n].to;

pin=A[from];
A[from]=0x00;
i=(pin>>6)&31;

if ((tmp=A[to])!=0)
{
balance-=tmp>>16;
C[x=(tmp>>6)&31]=64;
}

C[i]=to;
A[to]=pin;

M[n].balance=blMove(2);

if (tmp)
{
balance+=tmp>>16;
A[to]=tmp;
C[x]=to;
}
else A[to]=0;

A[from]=pin;
C[i]=from;
}
}

void InitProg(void)
{
char __xx_init[64]=
{
/* |---|---|---|---|---|---|---|---| */
/* | H | G | F | E | D | C | B | A | */
/* |---|---|---|---|---|---|---|---| */
/**/'T',' ',' ','K','D',' ',' ','T', // 1
/* |---|---|---|---|---|---|---|---| */
/**/'L',' ',' ','R','R',' ',' ','L', // 2
/* |---|---|---|---|---|---|---|---| */
/**/' ',' ',' ',' ',' ',' ',' ',' ', // 3
/* |---|---|---|---|---|---|---|---| */
/**/' ',' ',' ',' ',' ',' ',' ',' ', // 4
/* |---|---|---|---|---|---|---|---| */
/**/' ',' ',' ',' ',' ',' ',' ',' ', // 5
/* |---|---|---|---|---|---|---|---| */
/**/' ',' ',' ',' ',' ',' ',' ',' ', // 6
/* |---|---|---|---|---|---|---|---| */
/**/'l',' ',' ','r','r',' ',' ','l', // 7
/* |---|---|---|---|---|---|---|---| */
/**/'t',' ',' ','k','d',' ',' ','t', // 8
/* |---|---|---|---|---|---|---|---| */
};

for (int i=0; i<32; i++) C[i]=64;
memset(F, 0, sizeof(int)*256);
memset(A, 0, sizeof(int)*64);
SetPosit((char*)__xx_init);
}

void main(void)
{
elem X[256];
InitProg();
memset(X, 0, sizeof(elem)*256);

whiteMove(X, 1);

qsort(M, M_kpl, sizeof(move), whVert);

printf("...\n");

if (M[0].balance>=0)
{
whFirstMove(M, M_kpl);
qsort(M, M_kpl, sizeof(move), whVert);
}
else
{
printf("luovuttaa...\n");
}

for (int i=0; i
{
printf("%2d -> %2d ... %d\n",
M[i].from, M[i].to, M[i].balance);
}

getch();
}
[/code:1mxd6vnh]

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008
_jone_
Laitan koodin oheen, jotta abskissa voi arvostella kommenttien vähyyttä, ja muita puutteita

Tyydyn lainaamaan Knuthia, jonka parikymmentä vuotta sitten esittämään kehoitukseen yhdyn:

Donald E. Knuth
Let us change our traditional attitude to the construction of programs: Instead of imagining that our main task is to instruct a computer what to do, let us concentrate rather on explaining to human beings what we want a computer to do.

We're all mad here.

Vierailija

Hmm... kysymys on paljolti ehkä niin päin, että montako puolisiirtoa Rybkan löylytyksessä pärjää. Muutaman testipelin heittänyt lyhemmillä miettimisajoilla, jolloin Rybka on päässyt rankaisemaan keskipelin virheestä.

Nyt sitten pelaan vielä kerran pitemmillä miettimisajoilla. Jos pitäisi veikata, laittaisin lantit Rybkan puolesta likoon. Jos taas tulisi voitto, voisi sanoa aivan rehellisesti, että on päässyt höyhentämään Rybkaa.

No. Tämä brute-force pläjäys pelaa valkoisilla ja Rybka mustilla:

[code:19i01k7o]1. Lf4, Db6[/code:19i01k7o]

Sivut

Uusimmat

Suosituimmat