Author: Heiner Marxen
Date: 15:49:41 04/28/02
Go up one level in this thread
On April 28, 2002 at 08:31:15, Marek Mahdal wrote:
>On April 27, 2002 at 13:50:50, Russell Reagan wrote:
>
>>On April 27, 2002 at 11:15:00, Marek Mahdal wrote:
>>
>>>Hi everybody !
>>> Can somebody help me to find a function, which will generate all possible legal
>>>moves for a given position (any chessboard representation) in PHP or any other
>>>scripting non-type programming language ? I am not looking for a chess engine,
>>>only for the move generatino routine.
>>>
>>>Example:
>>>input parameters could be:
>>>
>>>- current chessboard representation
>>>- ep status
>>>- castle status
>>>- maybe history of moves
>>>
>>>output:
>>>- array of all possible move in the given position.
>>>
>>>Thank you a lot !
>>>
>>>Marek Mahdal, Slovakia
>>
>>This depends on your specific needs. For example, do you want a list of 100%
>>legal moves? Most chess programs don't generate all of the legal moves. For
>>example most don't detect pinned pieces and often move them, and they catch them
>>when they make the move and see that the side not to move is in check. So if you
>>want 100% legal moves you'd have to either write a pin detection function or a
>>function to make a move, find if one of the king's is in check, and eliminate
>>the illegal moves.
>>
>>I assume that you're trying to do some kind of web interaction. If that is the
>>case, I would suggest writing this in C or C++ and maybe write a script that
>>will parse the form data, then call the C/C++ program and store it's output in a
>>variable, then output it back to the user. That's what I would do rather than
>>write this kind of thing in a scripting language.
>>
>>Russell
>
>I need 100% legal moves, that means I need to make the move() and unmove()
>functions.
>Thank you for your suggestion with the C module. It will be definetely the best
>solution, but I have no clue of C++. That's why I am asking for help in
>scripting languages. Another problem is that my provider will not allow me to
>run C/C++ programs on the server, nor running a deamon, or socket reading. So I
>really needs to be done in some kind of scripting language.
>
>Sincerely,
>Marek Mahdal, Slovakia
I have used the following awk script as part of a CGI program.
It generates a select list for the possible legal moves in SAN notation,
marked with the resulting FEN. It reads a single FEN line from the input.
May be you can adapt the encorporated ideas.
(NB: it is not written for efficiency)
BEGIN {
dbg = 0
#prf = 1
for( i=1 ; i<=8 ; ++i ) nums["" i] = i
for( i=1 ; i<=6 ; ++i ) {
p = substr("pnbrqk", i, 1)
## 123456
P = toupper(p)
pieces[p] = i
colour[p] = "b"
pieces[P] = i
colour[P] = "w"
}
oppc["w"] = "b"
oppc["b"] = "w"
cK["w"] = "K"
cK["b"] = "k"
cR["w"] = "R"
cR["b"] = "r"
cPstep["w"] = 1
cPstep["b"] = -1
cProm["w"] = "QNRB"
cProm["b"] = "qnrb"
## 6 2 4 normal Q directions
## 1 * 0
## 5 3 7
defD( 0, 1, 0, "qQrR", "kK")
defD( 2, 0, 1, "qQrR", "kK")
defD( 4, 1, 1, "qQbB", "kK") # up-right + down-left
defD( 6,-1, 1, "qQbB", "kK") # up-left + down-right
defD( 8, 1, 2, "", "nN")
defD(10, 2, 1, "", "nN")
defD(12, 1,-2, "", "nN")
defD(14, 2,-1, "", "nN")
defPatt(4)
defPatt(6)
for( row=1 ; row<=8 ; ++row ) {
for( col=1 ; col<=8 ; ++col ) {
isB[col,row] = 1
}
}
chkStr[0] = ""
chkStr[1] = "+"
chkStr[2] = "#"
k2q["k"] = "q"
k2q["K"] = "Q"
k2r["k"] = "r"
k2r["K"] = "R"
casRcol["K"] = 8
casRcol["Q"] = 1
casRcol["k"] = 8
casRcol["q"] = 1
casRpos["K"] = 8 SUBSEP 1
casRpos["Q"] = 1 SUBSEP 1
casRpos["k"] = 8 SUBSEP 8
casRpos["q"] = 1 SUBSEP 8
casKpos["K"] = casKpos["Q"] = 5 SUBSEP 1
casKpos["k"] = casKpos["q"] = 5 SUBSEP 8
}
function defPatt(d) # add pawn attacks
{
#if(prf) prfC["defPatt"] += 1
Patt1[ d ] = Patt1[ d ] "p" # up: incoming attack from black
Patt1[d+1] = Patt1[d+1] "P" # down: incoming attack from white
}
function defD(d,x,y,pcs,pcs1)
{
#if(prf) prfC["defD"] += 1
xD[ d ] = x ; yD[ d ] = y
xD[d+1] = -x ; yD[d+1] = -y
PattD[ d ] = pcs
PattD[d+1] = pcs
Patt1[ d ] = pcs1
Patt1[d+1] = pcs1
oppD[ d ] = d+1 ##FFS used?
oppD[d+1] = d
}
function putP(f)
{
#if(prf) prfC["putP"] += 1
B[col,row] = f
if( (f == "k") || (f == "K") ) B[f] = col row # K-pos cache
if( ++col > 8 ) { col = 1; --row }
}
function mk_fen(B ,col,row,fen,ec)
{
#if(prf) prfC["mk_fen"] += 1
for( row=8 ; row>0 ; --row ) {
ec = 0
for( col=1 ; col<=8 ; ++col ) {
if( B[col,row] != " " ) {
fen = fen (ec ? "" ec : "") B[col,row]
ec = 0
}else {
++ec
}
}
if( ec ) fen = fen ec
if( row > 1 ) fen = fen "/"
}
return fen " " B["ctm"] " " B["cas"] " " B["epi"]
}
function bAttBy(B,col,row,cta ,dir,x,y,c,r,p,cnt)
{
#if(prf) prfC["bAttBy"] += 1
for( dir=0 ; dir<16 ; ++dir ) {
#if(prf) prfC["bAttBy.dir"] += 1
x = xD[dir] ; y = yD[dir]
c = col ; r = row
p = "" ; cnt = 0
for(;;) {
#if(prf) prfC["bAttBy.dir.step"] += 1
c += x ; r += y ; ++cnt
if( ! isB[c,r] ) break ## border
if( (p = B[c,r]) != " " ) {
#if(prf) prfC["bAttBy.dir.step.att"] += 1
if( colour[p] == cta ) { ## actually an attacker
if( index(PattD[dir], p) ) return 1
if( (cnt==1) && index(Patt1[dir], p) ) return 1
}
break;
}
if( (cnt==1) && ! PattD[dir] ) break ## FFS delete
}
}
return 0 ## no attack found
}
function noteRes(nB,mov,rp,rc,rr,mv,suf)
{
#if(prf) prfC["noteRes"] += 1
++nR
Rfen[nR] = mk_fen(nB)
Rmov[nR] = mov
Rp[ nR] = rp
Rc[ nR] = rc
Rr[ nR] = rr
Rmv[ nR] = mv
Rsuf[nR] = suf
RmvC[rp mv] += 1
}
function filtRes( i,j,need,okC,okR,dis)
{
#if(prf) prfC["filtRes"] += 1
for( i=1 ; i<=nR ; ++i ) {
if( ! Rmov[i] ) { ## not yet ready
#if(prf) prfC["filtRes.i"] += 1
need = 0
if( RmvC[Rp[i] Rmv[i]] >= 2 ) {
#if(prf) prfC["filtRes.i.2"] += 1
okC = okR = 1
for( j=1 ; j<=nR ; ++j ) {
#if(prf) prfC["filtRes.i.2.j"] += 1
if( j == i ) continue
if( (Rmv[j] != Rmv[i]) || (Rp[j] != Rp[i]) ) continue
need = 1
if( Rc[j] == Rc[i] ) okC = 0
if( Rr[j] == Rr[i] ) okR = 0
}
}
dis = ""
if( need ) {
if( okC ) {
dis = Rc[i]
}else if( okR ) {
dis = Rr[i]
}else {
dis = Rc[i] Rr[i]
}
}
Rmov[i] = Rp[i] dis Rmv[i] Rsuf[i]
}
}
}
function colname(col)
{
#if(prf) prfC["colname"] += 1
return substr("abcdefgh", col,1)
}
function captStr(target)
{
#if(prf) prfC["captStr"] += 1
return (target == " ") ? "" : "x"
}
function filterCas(B ,ncass,cas,i)
{
#if(prf) prfC["filterCas"] += 1
ncass = ""
for( i=1 ; i<=4 ; ++i ) {
#if(prf) prfC["filterCas.i"] += 1
cas = substr("KQkq", i,1)
if( index(B["cas"], cas) ) {
if( B[casKpos[cas]] == cK[colour[cas]] \
&& B[casRpos[cas]] == cR[colour[cas]] ) {
ncass = ncass cas
}
}
}
B["cas"] = (ncass ? ncass : "-")
}
function genResult(B,nB, col,row, c,r, cas ,mov,ic,rp,rc,rr,suf)
{
#if(prf) prfC["genResult"] += 1
## FFS: enable ep
filterCas(nB)
mv = suf = ""
if( cas ) {
mov = cas
}else {
if( index("pP", B[col,row]) ) { ## pawn move
mov = ((col != c) ? colname(col) "x" : "")
}else { ## non-pawn move
## FFS: We use long algebraic notation: easier to generate
mov = ""
rp = toupper(B[col,row])
rc = colname(col)
rr = row
mv = captStr(B[c,r])
}
mv = mv colname(c) r
if( nB[c,r] != B[col,row] ) {
mv = mv "=" toupper(nB[c,r])
}
}
ic = inCheck(nB)
if( ic && chkIsMate(nB) ) ++ic
suf = chkStr[ic]
if( mov ) {
mov = mov mv suf ; mv = suf = ""
}
noteRes(nB, mov, rp,rc,rr,mv,suf)
return 1
}
function bFind(B,who ,cr,col,row)
{
#if(prf) prfC["bFind"] += 1
if( who in B ) {
cr = B[who]; col = substr(cr,1,1); row = substr(cr,2,1)
if( isB[col,row] && (B[col,row] == who) ) {
return cr
}
}
for( row=1 ; row<=8 ; ++row ) {
#if(prf) prfC["bFind.r"] += 1
for( col=1 ; col<=8 ; ++col ) {
#if(prf) prfC["bFind.r.c"] += 1
if( B[col,row] == who ) {
if( (who=="k") || (who=="K") ) B[who] = col row ## K-pos cache
return col row
}
}
}
return ""
}
function kAttacked(B,cta ,cr)
{ ## whether king of side "cta" is attacked
#if(prf) prfC["kAttacked"] += 1
cr = bFind(B, cK[cta])
if( cr ) {
return bAttBy(B, substr(cr,1,1), substr(cr,2,1), oppc[cta])
}
return 0 ## missing piece is not attacked
}
function bLegal(B)
{
#if(prf) prfC["bLegal"] += 1
## fails, when ctm can beat opponents K (pseudo-legally)
return ! kAttacked(B, oppc[B["ctm"]])
}
function inCheck(B)
{
#if(prf) prfC["inCheck"] += 1
return kAttacked(B, B["ctm"])
}
function bNullMove(B, nB ,k)
{
#if(prf) prfC["bNullMove"] += 1
#for( k in nB ) delete nB[k]
for( k in B ) nB[k] = B[k] ## inclusive "cas"
nB["ctm"] = oppc[B["ctm"]] ## change colour to move
nB["epi"] = "-" ## reset ep info
}
function genCas1(B,col,row,cas,dcol,mov ,sum,c,r,nB)
{ ## #(moves) | whether exists one
#if(prf) prfC["genCas1"] += 1
if(dbg) printf(" genCas1(%d,%d, %s,%2d, %s)\n", col,row,cas,dcol,mov)
## we are not in check
sum = 0
if( ! index(B["cas"], cas) ) return 0
#if(dbg) printf(" genCas1: right ok\n")
if( B[col+ dcol,row] != " ") return 0
#if(dbg) printf(" genCas1: K+d empty\n")
if( B[col+2*dcol,row] != " ") return 0
#if(dbg) printf(" genCas1: K+2d empty\n")
if( B[casRcol[cas]-dcol,row] != " ") return 0
#if(dbg) printf(" genCas1: R-d empty\n")
if( bAttBy(B, col+ dcol, row, oppc[B["ctm"]]) ) return 0
#if(dbg) printf(" genCas1: K+d not attacked\n")
if( bAttBy(B, col+2*dcol, row, oppc[B["ctm"]]) ) return 0
#if(dbg) printf(" genCas1: K+2d not attacked\n")
c = col+2*dcol
r = row
if(dbg)printf(" try cas to %d,%d\n", c,r)
nB["epi"] = "-" ## make nB an array
bNullMove(B, nB)
nB[col,row] = " "
nB[ c , r ] = B[col,row]
nB[B[col,row]] = c r ## K-pos cache
nB[col+dcol,row] = B[casRpos[cas]]
nB[casRpos[cas]] = " "
if( bLegal(nB) ) {
sum += genResult(B,nB, col,row, c,r, mov)
}
return sum
}
function genNorm1(B,gen,col,row,c,r,p ,nB)
{ ## #(moves) | whether exists one
#if(prf) prfC["genNorm1"] += 1
nB["epi"] = "-" ## make nB an array
bNullMove(B, nB)
nB[col,row] = " "
nB[c,r] = p
if( (p=="k") || (p=="K") ) nB[p] = c r ## K-pos cache
if( bLegal(nB) ) {
if( gen ) genResult(B,nB, col,row, c,r, "")
return 1 ## legal move exists
}
return 0
}
function genGen(B,gen,col,row,dlo,dhi,mxstep ,sum,p,dir,x,y,c,r,cnt,t)
{ ## #(moves) | whether exists one
#if(prf) prfC["genGen"] += 1
if(dbg)printf(" genGen(%d, %d,%d, %d,%d,%d)\n", gen,col,row,dlo,dhi,mxstep)
sum = 0
p = B[col,row]
for( dir=dlo ; dir<dhi ; ++dir ) {
#if(prf) prfC["genGen.dir"] += 1
x = xD[dir] ; y = yD[dir]
c = col ; r = row ; cnt = 0
for(; ++cnt <= mxstep ;) {
#if(prf) prfC["genGen.dir.step"] += 1
c += x ; r += y
if( ! isB[c,r] ) break ## border
t = B[c,r]
if( colour[t] == B["ctm"] ) break
sum += genNorm1(B,gen,col,row,c,r,p)
if( !gen && sum ) return 1 ## legal move exists
if( t != " " ) break
}
}
# legal castling implies normal legal K move
if( gen && index("kK", p) && (B[casKpos[p]] == p) ) { ## try castling
## FFS: castlings
if(dbg) printf(" chk cas=%s p=%s@(%d,%d)\n", B["cas"],p,col,row)
if( index(B["cas"], p) || index(B["cas"], k2q[p]) ) {
if(dbg) printf(" cas: rights present\n")
if( ! inCheck(B) ) {
if(dbg) printf(" cas: not in check \n")
sum += genCas1(B,col,row, p , 1,"O-O" )
sum += genCas1(B,col,row,k2q[p],-1,"O-O-O")
}
}
}
if( !gen && sum ) return 1 ## legal move exists
return sum
}
function genPawn1(B,gen,col,row,c,r,epi,delc,delr,t ,nB)
{ ## #(moves) | whether exists one
#if(prf) prfC["genPawn1"] += 1
nB["epi"] = epi ## make nB an array
bNullMove(B, nB)
nB["epi"] = epi
nB[col,row] = " "
nB[ c , r ] = t
if( isB[delc,delr] ) nB[delc,delr] = " "
if( bLegal(nB) ) {
if( gen ) genResult(B,nB, col,row, c,r, "")
return 1 ## legal move exists
}
return 0
}
function genPawnSome(B,gen,col,row,c,r,epi,delc,delr ,sum,pp,i)
{ ## #(moves) | whether exists one
#if(prf) prfC["genPawnSome"] += 1
sum = 0
if( r==1 || r==8 ) {
pp = cProm[B["ctm"]]
for( i=1 ; i<=4 ; ++i ) {
sum += genPawn1(B,gen,col,row,c,r, epi,delc,delr, substr(pp,i,1))
}
}else {
sum += genPawn1(B,gen,col,row,c,r, epi,delc,delr, B[col,row])
}
if( !gen && sum ) return 1 ## legal move exists
return sum
}
function genPawnCapt(B,gen,col,row,c,r)
{ ## #(moves) | whether exists one
#if(prf) prfC["genPawnCapt"] += 1
if( isB[c,r] ) {
if( B[c,r] == " " ) {
if( B["epi"] == (colname(c) r) ) {
return genPawnSome(B,gen, col,row, c,r, "-",c,row)
}
}else if( colour[B[c,r]] == oppc[B["ctm"]] ) {
return genPawnSome(B,gen, col,row, c,r, "-",0,0)
}
}
return 0
}
function genPawn(B,gen,col,row ,sum,d,r,epi)
{ ## #(moves) | whether exists one
#if(prf) prfC["genPawn"] += 1
## FFS
sum = 0
d = cPstep[B["ctm"]]
r = row + d
if( isB[col,r] && (B[col,r] == " ") ) {
sum += genPawnSome(B,gen, col,row, col,r, "-",0,0)
r = r + d
if( (row==2 || row==7) && isB[col,r] && (B[col,r] == " ") ) {
epi = colname(col) (row+d)
sum += genPawnSome(B,gen, col,row, col,r, epi,0,0)
}
}
sum += genPawnCapt(B,gen, col,row, col-1,row+d)
sum += genPawnCapt(B,gen, col,row, col+1,row+d)
if( !gen && sum ) return 1 ## legal move exists
return sum
}
function genMvs(B,gen ,sum,row,col,p)
{ ## #(moves) | whether exists one
#if(prf) prfC["genMvs"] += 1
sum = 0
for( row=1 ; row<=8 ; ++row ) {
#if(prf) prfC["genMvs.r"] += 1
for( col=1 ; col<=8 ; ++col ) {
#if(prf) prfC["genMvs.r.c"] += 1
p = B[col,row]
if( colour[p] != B["ctm"] ) continue
if(dbg) printf(" Piece %s at %d/%d\n", p, col,row)
if( index("nN", p) ) sum += genGen(B,gen,col,row,8,16,1)
else if( index("rR", p) ) sum += genGen(B,gen,col,row,0, 4,7)
else if( index("bB", p) ) sum += genGen(B,gen,col,row,4, 8,7)
else if( index("qQ", p) ) sum += genGen(B,gen,col,row,0, 8,7)
else if( index("kK", p) ) sum += genGen(B,gen,col,row,0, 8,1)
else if( index("pP", p) ) sum += genPawn(B,gen,col,row)
if( !gen && sum ) return 1
}
}
return sum
}
function chkIsMate(B)
{
#if(prf) prfC["chkIsMate"] += 1
return ! genMvs(B,0)
}
{
if(dbg) printf("Input: %s\n", $0)
fen = $1
ctm = tolower(substr($2 "w",1,1))
cas = $3
epi = $4
B["ctm"] = ctm
B["cas"] = cas
B["epi"] = epi
row = 8
col = 1
sli = 0
len = length(fen)
for( i=1 ; i<=len ; ++i ) {
if( row < 1 ) break
f = substr(fen, i, 1)
if( f in nums ) {
for( j=1 ; j<=f ; ++j ) putP(" ")
continue
}
if( f in pieces ) {
putP(f)
continue
}
if( f == "/" ) {
if( sli == (i-1) ) putP(" ")
while( col > 1 ) putP(" ")
sli = i
}
}
filterCas(B)
if( dbg ) {
printf("<pre>\n")
genMvs(B, 1)
filtRes()
for( i=1 ; i<=nR ; ++i ) {
printf("%3d: %8s %s\n", i, Rmov[i], Rfen[i])
}
printf("</pre>\n")
}else {
if( ! bLegal(B) ) {
printf("This board is illegal!\n")
}else {
genMvs(B, 1)
filtRes()
if( ! nR ) {
ic = inCheck(B)
printf("This is %smate!\n", ic?"":"stale")
}else {
printf("<select name=\"mvfen\" size=1>\n")
printf("<option value=\"\" checked> move\n")
for( i=1 ; i<=nR ; ++i ) {
printf("<option value=\"%s%%%s\"> %d: %s\n", \
Rmov[i], Rfen[i], i,Rmov[i])
}
if( ! inCheck(B) ) {
nB["epi"] = "-" ## make nB an array
bNullMove(B, nB)
mov = "NULL"
printf("<option value=\"%s%%%s\"> %s\n", \
mov, mk_fen(nB), mov)
}
printf("</select>\n")
}
}
}
}
END {
#if(prf) {
# print "<pre>"
# for( k in prfC ) printf("%25s %6d\n", k, prfC[k])
# print "</pre>"
#}
}
Cheers,
Heiner
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.