Author: Marek Mahdal
Date: 00:51:55 04/30/02
Go up one level in this thread
On April 28, 2002 at 18:49:41, Heiner Marxen wrote:
>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
Thank you ! I'll go through the code and let you know the result !
Sincerely,
Marek Mahdal
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.