Is it time for another new move generator?

[Pradu]

The energy maps is what drives the FFT. These maps are two dimensional (2D FFT) and provide information about energy distribution within the system and not just the peak, i.e. band-power is IMO more valuable than absolute peak-power.

I'm still a little confused. A two dimensional FFT? Does that mean that you do FFTs for each direction separately, like ranks and files?

http://www.cnyack.homestead.com/files/a ... 2dint1.htm
http://www.cs.unm.edu/~brayer/vision/fourier.html

I also don't see how band power would mean anything in this context....I don't know much about FFTs, just some basic theory, so an example of how a position translates to a wave and then to an FT would great.

You see, nobody really does stuff like this, so everyone is amazed when they hear about it.

[Pradu]

The functions that generate KE and PE take into account minimum amount of chess rules and a few assumptions, however none of those can be considered "chess knowledge", at least not in the way other programs are using this term.

The KE function(s) (logically speaking there are really just two of them, one for pawns and one for everything else) don't have any special cases with respect to positions or particular piece configurations, those functions require the current position only so the generated energy map can follow the rules of chess. There is no explicit knowledge about "doubled pawns", "rook on the 7th", "trapped bishop", "open line", etc. etc. The only aspects of the position that those functions are concerned with are:
1) Is a square occupied by a piece?
1.1) Is this opponent piece?
1.2) Is this own pawn?

Does the type of piece matter? Or is it only that the piece type is occupied?

This is it. No other information is extracted from the position during energy map generation.

Can your energy function(s) recognize doubled pawns as bad and passed pawns as good even though you haven't explicitly coded it? If it can, what is the definition of energy you use for pawns.

The reason to use two different KE generation functions is that pawns "behave" drastically different from the other pieces and I couldn't figure out how to merge this behavior into one function.

Do you have something like KE + PE = 0 or something like KE + PE = Change in total energy in the system from a move?

I have tried both. Currently am using the KE+PE = Change in total E, not because it is inherently better, but because it is easier for me to understand.

If so what do you do to generate a score when the KE and PE of a position is known.

The easiest way of looking at it is that we have two sets of KE and PE:
For white: wKE + wPE = wTE
For black: bKE + bPE = bTE

Because the measured quantity, the total energy for a side will change for every move, there is no need to split it up into kinetic and potential components right? (Because every move will cause a change in the energy of the system so perhaps we can't use any conservation laws to benefit anything). Lets say a Knight has a PE=0.5 at b1. If one plays Nc3 it's PE becomes 0.4 and it's KE becomes 0.1. But we do know the score is better when it's at c3; so, there can't be any conservation of energy and the move adds energy to the system to say make it PE = 0.5, KE = 0.1. Now lets say it goes back to b1. If energy was conserved it would suggest PE=0.6, KE=0.0. But we know it's value is less so lets say the move removes energy from the system and it becomes PE=0.5, KE=0.0. But what you will be measuring here is the change in the total energy so perhaps there's no advantage to separating KE and PE from the total energy because nothing is going to get conserved.

and then try to maximize the TE for the side to move while minimizing the TE for the opponent. The ratio between wTE and bTE is what drives the final score.

In the case where the result from the position is known (say a "mate" is found) the return value that I'm using is +INFINITY. Although this is not necessary, since the ratio would be 1.0, i.e. the opponent has no Energy left.

Ok I think you meant the score is done such that score=wTE/(wTE + bTE) because the ratio would be zero or infinity if one side didn't have any energy for score = wTE/bTE.

Also what information is in the datastream for the FFT and what do you do with the (I'm guessing peak-power) frequencies obtained from power spectrum?

The energy maps is what drives the FFT. These maps are two dimensional (2D FFT) and provide information about energy distribution within the system and not just the peak, i.e. band-power is IMO more valuable than absolute peak-power.

What do you do with the frequency domain representation of the energy distribution. You will get a measure of how periodic the energy distribution is but how will this help in generating the score. Also won't there be problems with aliasing? You have to sample the energy distribution at a little above the Nyquist frequency of highest frequency of your data set. Say you had a signal that alternated RMS energy every square. This would require a sampling which would sample a little more than 2 times every square, but we have no such things as half-squares. The FFT suggests that this signal is actually two or more sinusoids of a lower frequency, but it could very well be a signal with a much higher frequency. So what do you do to avoid aliasing problems.

As you can imagine at this point in the evaluation we are completely removed from any notion of "chess knowledge".

Indeed it sounds like a very expensive eval if you have to generate a datastream for each position and do an FFT on it, but I guess one would need to do some testing to see if the quality of the knowledgeless eval is good enough to offset the loss in search depth.

I don't know if this is better than the "built in chess knowledge" approach, but the sheer novelty factor makes it more fun to experiment with. In fact, this approach might not lead to a better playing chess program.

There are many different ways to generate the Energy maps and even more ways to analyze them. For instance the FFTs are not necessary, but it is surely fun to see a spectrogram of a chess position.

New ideas are always nice, even if they don't work out at first.

Regards and Good morning,
Hristo

Yes my sleep schedule is off because of a lot of things...

[hristo]

The energy maps is what drives the FFT. These maps are two dimensional (2D FFT) and provide information about energy distribution within the system and not just the peak, i.e. band-power is IMO more valuable than absolute peak-power.

I'm still a little confused. A two dimensional FFT? Does that mean that you do FFTs for each direction separately, like ranks and files? I also don't see how band power would mean anything in this context. Perhaps you mean that by band power you are saying the amount of "energy" put along certain ranks, files, and diagonals? I don't know much about FFTs, just some basic theory, so an example of how a position translates to a wave and then to an FT would great.

The position doesn't translate into a wave, but it rather translates into an image. For simplicity lets say that each square of the board becomes a pixel of a 64x64 image. (although it is better if the image is larger, say 128X128, so we can apply windowing ...)
In each pixels is encoded the overall "energy" (for lack of a better word) of all pieces. That "energy" can be either positive (if white pieces exert more energy on that square) or negative.

Once you have the image (derived from the position) you can use the FFT to determine how much "power" is in the system -- IOW, how much and how often does the energy encoded in the pixels swing from "+" to "-".

The assumption here is that this view of the chess position actually has some relation to the game. (That is a big assumption) If it does then moves that improve the Energy balance can be considered good and searched first.

Here, for example, is the output from the static evaluation at the starting position:

Code: Select all

--  e2e3{5.85803}
--  e2e4{5.5325}
--  d2d4{4.40868}
--  d2d3{3.4629}
--  c2c4{2.07885}
--  c2c3{2.00861}
--  g1f3{1.72662}
--  b1c3{1.65587}
--  b2b3{1.30058}
--  g2g3{1.15774}
--  b2b4{1.01449}
--  g2g4{0.870827}
--  h2h4{0.798838}
--  a2a4{0.726744}
--  g1h3{0.654545}
--  f2f4{0.582242}
--  b1a3{0.582242}
--  f2f3{-0}
--  h2h3{-0.0732064}
--  a2a3{-0.0732064}

There is no search involved in this ... just make the move and calculate the energy.
BTW, the scores after the moves have nothing to do with "pawn advantage" ... they simply indicate how much the energy changed in some unnamed units.

You see, nobody really does stuff like this, so everyone is amazed when they hear about it.

[Pradu]

This would require a sampling which would sample a little more than 2 times every square

I meant a little more than 1 time every square...

[hristo]

The functions that generate KE and PE take into account minimum amount of chess rules and a few assumptions, however none of those can be considered "chess knowledge", at least not in the way other programs are using this term.

The KE function(s) (logically speaking there are really just two of them, one for pawns and one for everything else) don't have any special cases with respect to positions or particular piece configurations, those functions require the current position only so the generated energy map can follow the rules of chess. There is no explicit knowledge about "doubled pawns", "rook on the 7th", "trapped bishop", "open line", etc. etc. The only aspects of the position that those functions are concerned with are:
1) Is a square occupied by a piece?
1.1) Is this opponent piece?
1.2) Is this own pawn?

Does the type of piece matter? Or is it only that the piece type is occupied?

The only piece type that is treated "differently" is the pawns for the side to move. The primary reason for this is that I was too lazy to write the code to handle them in a generic way, so instead I use them as units that block the energy for the side to move, which is what they do more often than not.

This is it. No other information is extracted from the position during energy map generation.

Can your energy function(s) recognize doubled pawns as bad and passed pawns as good even though you haven't explicitly coded it? If it can, what is the definition of energy you use for pawns.

Doubled pawns are not immediately "bad" but depending on the position they often lead to reduced energy score. There are several reasons as to why this might happen:
1) The pawns have a single energy vector and when they are doubled (tripled) the pawns that are behind have their energy vector blocked which leads to reduction of energy.
2) Doubled pawns create little barriers for the energy propagation of the other pieces of the same color -- reduces overall KE -- but they don't reduce the Energy for the opponent since they can be captured. (this is situational)
3) They create lumpiness in the energy that more often than not seems to have negative impact on the overall energy. (this is very situational and probably doesn't have a huge effect. Besides it is difficult to visualize or predict, I observed it but don't know what to make of it.)

Passed pawns are considered "good" because their energy vector extends all the way to the promotion square. When building the energy map for such pawn the energy of the promoted piece (hardcoded to Queen) is added to the map of the pawn, and even though this additional energy is greatly reduced based on the distance to promotion, it has measurable effect on the total energy calculation.

The reason to use two different KE generation functions is that pawns "behave" drastically different from the other pieces and I couldn't figure out how to merge this behavior into one function.

Do you have something like KE + PE = 0 or something like KE + PE = Change in total energy in the system from a move?

I have tried both. Currently am using the KE+PE = Change in total E, not because it is inherently better, but because it is easier for me to understand.

If so what do you do to generate a score when the KE and PE of a position is known.

The easiest way of looking at it is that we have two sets of KE and PE:
For white: wKE + wPE = wTE
For black: bKE + bPE = bTE

Because the measured quantity, the total energy for a side will change for every move, there is no need to split it up into kinetic and potential components right? (Because every move will cause a change in the energy of the system so perhaps we can't use any conservation laws to benefit anything). Lets say a Knight has a PE=0.5 at b1. If one plays Nc3 it's PE becomes 0.4 and it's KE becomes 0.1. But we do know the score is better when it's at c3; so, there can't be any conservation of energy and the move adds energy to the system to say make it PE = 0.5, KE = 0.1. Now lets say it goes back to b1. If energy was conserved it would suggest PE=0.6, KE=0.0. But we know it's value is less so lets say the move removes energy from the system and it becomes PE=0.5, KE=0.0. But what you will be measuring here is the change in the total energy so perhaps there's no advantage to separating KE and PE from the total energy because nothing is going to get conserved.

Excellent point!!!
I wrestled with this issue for a long time and didn't want to introduce PE, using similar argumentation as you. It was about a year ago when I managed to convince myself that PE is needed or is beneficial to the Energy evaluation. Without looking through my notes (source code comments) here are some of the reasons for PE:
1) The KE for a piece could be negligible in some positions while other pieces could easily gain more KE. In this case the Evaluation would drop the undeveloped piece way too easily. This convinced me that KE (only) is not a sufficiently accurate representation or that the energy maps (KE) is not constructed properly. Since I couldn't figure out a better way to build KE map I opted for introducing PE.
2) The eval takes into account the ratio between the KE of both sides. Thus it is possible to make a move that doesn't increase the KE for the side to move but it reduces the KE for the opponent. The consequence of this is that, again, the eval tends to drop undeveloped pieces like flies. (follows the same as #1)
3) The presence of pieces on the board limits the KE they can achieve and this also leads to "desire" to remove some of your own pieces to maximize the KE of the others.

The PE is the maximum possible energy that a piece can have when there are only kings on the board. So, what I did, create a position with just two kings and calculate the energy then add a single piece, calculate again and subtract the Kings-only energy map.

and then try to maximize the TE for the side to move while minimizing the TE for the opponent. The ratio between wTE and bTE is what drives the final score.

In the case where the result from the position is known (say a "mate" is found) the return value that I'm using is +INFINITY. Although this is not necessary, since the ratio would be 1.0, i.e. the opponent has no Energy left.

Ok I think you meant the score is done such that score=wTE/(wTE + bTE) because the ratio would be zero or infinity if one side didn't have any energy for score = wTE/bTE.

Of course.
If black are mated then they would have no energy etc.

Also what information is in the datastream for the FFT and what do you do with the (I'm guessing peak-power) frequencies obtained from power spectrum?

The energy maps is what drives the FFT. These maps are two dimensional (2D FFT) and provide information about energy distribution within the system and not just the peak, i.e. band-power is IMO more valuable than absolute peak-power.

What do you do with the frequency domain representation of the energy distribution. You will get a measure of how periodic the energy distribution is but how will this help in generating the score. Also won't there be problems with aliasing? You have to sample the energy distribution at a little above the Nyquist frequency of highest frequency of your data set. Say you had a signal that alternated RMS energy every square. This would require a sampling which would sample a little more than 2 times every square, but we have no such things as half-squares. The FFT suggests that this signal is actually two or more sinusoids of a lower frequency, but it could very well be a signal with a much higher frequency. So what do you do to avoid aliasing problems.

This is all true and it would be a problem if I were interested in the actual frequency domain information. However, what is important (to me) is the total power of the system which is not effected by the aliasing in frequency. As I said earlier the FFTs are not needed, as such, but are fun. In my case the band-power is the entire position and not a particular part of the board.

As you can imagine at this point in the evaluation we are completely removed from any notion of "chess knowledge".

Indeed it sounds like a very expensive eval if you have to generate a datastream for each position and do an FFT on it, but I guess one would need to do some testing to see if the quality of the knowledgeless eval is good enough to offset the loss in search depth.

I don't know if this is better than the "built in chess knowledge" approach, but the sheer novelty factor makes it more fun to experiment with. In fact, this approach might not lead to a better playing chess program.

There are many different ways to generate the Energy maps and even more ways to analyze them. For instance the FFTs are not necessary, but it is surely fun to see a spectrogram of a chess position.

New ideas are always nice, even if they don't work out at first.

Regards and Good morning,
Hristo

Yes my sleep schedule is off because of a lot of things...

Best Regards and Good morning (again ),
Hristo

[Tommy]

Hi Bill,

You are allowed to publish 'basic code'. We C/C++ people are not going to attack you!

Ok, here is one written in BASIC which uses the idea of pre-calculated moves stored in an array. Probably not as cleverly implemented as the examples already shown, but here it is anyway...

Code: Select all

sub MoveGen()
    
    'Move Generator

dim as integer iY,iX 
dim as integer iPiece,iSquare,iDir,iToSquare,iDist 
dim iIndex as integer

MoveList(Depth,0,0)=0 ' reset move index

' Loop through each piece for side to move.
for iIndex=1 to PieceList(SideToMove+1,0,0)
    iSquare=PieceList(SideToMove+1,1,iIndex) ' From square
    iPiece=abs(board(iSquare)) ' piece being moved
    if iPiece <> 1 then
        ' sliding pieces & knight
        for iDir=1 to PieceMaxDir&#40;iPiece&#41;
            For iDist=1 to MaxDist&#40;iSquare,iPiece,iDir&#41;
                iToSquare=MoveOffSet&#40;iSquare,iPiece,iDir,iDist&#41;
                
                if board&#40;iToSquare&#41;=0 then 'Empty square
                    call SaveMove&#40;iSquare,iToSquare,0&#41;
                else 
                    if sgn&#40;board&#40;iSquare&#41;)=sgn&#40;board&#40;iToSquare&#41;) then ' Capture piece is same colour 
                        exit for
                    else 
                        if abs&#40;Board&#40;iToSquare&#41;)=6 then ' king captured
                            MoveList&#40;Depth,0,0&#41;=0 
                            call SaveMove&#40;iSquare,iToSquare,0&#41;
                            exit sub 'Return only one move in move list.
                        else
                            call SaveMove&#40;iSquare,iToSquare,0&#41; ' Capture piece is of opposite colour
                            exit for
                        end if
                    end if
                end if
            next
        next
    else ' white pawn 
        if SideToMove=White then 
            if board&#40;iSquare-10&#41;=0 then call SavePawnMove&#40;iSquare,iSquare-10,0&#41;
            if board&#40;iSquare-9&#41;<0 then call SavePawnMove&#40;iSquare,iSquare-9,0&#41;
            if board&#40;iSquare-11&#41;<0 then call SavePawnMove&#40;iSquare,iSquare-11,0&#41;
            if iSquare>80 then
                if board&#40;iSquare-10&#41;=0 and board&#40;iSquare-20&#41;=0 then call SaveMove&#40;iSquare,iSquare-20,0&#41;
            end if
        else ' black pawn
            if board&#40;iSquare+10&#41;=0 then call SavePawnMove&#40;iSquare,iSquare+10,0&#41;
            if board&#40;iSquare+9&#41;>0 then 
                if board&#40;iSquare+9&#41;< 10 then call SavePawnMove&#40;iSquare,iSquare+9,0&#41;
            end if
            if board&#40;iSquare+11&#41;>0 then 
                if board&#40;iSquare+11&#41;< 10 then call SavePawnMove&#40;iSquare,iSquare+11,0&#41;
            end if
            if iSquare<39 then
                if board&#40;iSquare+10&#41;=0 and board&#40;iSquare+20&#41;=0 then call SaveMove&#40;iSquare,iSquare+20,0&#41;
            end if
        end if
    end if
next



'castling
if SideToMove=White then
    if bit&#40;CastleRights,1&#41;=-1 then
        if board&#40;96&#41;=0 then
            if board&#40;97&#41;=0 then
                if InCheckII&#40;96&#41;=0 and InCheckII&#40;97&#41;=0 then 
                    if InCheckII&#40;WhiteKing&#41;=0 then call SaveMove&#40;95,97,1&#41;
                end if
            end if
        end if
    end if
    if bit&#40;CastleRights,2&#41;=-1 then
        if board&#40;94&#41;=0 then
            if board&#40;93&#41;=0 then
                if board&#40;92&#41;=0 then
                    if InCheckII&#40;94&#41;=0 and InCheckII&#40;93&#41;=0 then 
                        if InCheckII&#40;WhiteKing&#41;=0 then call SaveMove&#40;95,93,2&#41;
                    end if
                end if
            end if
        end if
    end if
else
    if bit&#40;CastleRights,3&#41;=-1 then
        if board&#40;26&#41;=0 then
            if board&#40;27&#41;=0 then
                if InCheckII&#40;26&#41;=0 and InCheckII&#40;27&#41;=0 then 
                    if InCheckII&#40;BlackKing&#41;=0 then call SaveMove&#40;25,27,3&#41;
                end if
            end if
        end if
    end if
    if bit&#40;CastleRights,4&#41;=-1 then
        if board&#40;24&#41;=0 then
            if board&#40;23&#41;=0 then
                if board&#40;22&#41;=0 then
                    if InCheckII&#40;24&#41;=0 and InCheckII&#40;23&#41;=0 then 
                        if InCheckII&#40;BlackKing&#41;=0 then call SaveMove&#40;25,23,4&#41;
                    end if
                end if
            end if
        end if
    end if    
end if

'Enpassant move
if EnpassantSquare<>0 then
    if SideToMove=White then
        if board&#40;EnpassantSquare+1&#41;=1 then SaveMove&#40;EnpassantSquare+1,EnpassantSquare-10,5&#41;
        if board&#40;EnpassantSquare-1&#41;=1 then SaveMove&#40;EnpassantSquare-1,EnpassantSquare-10,5&#41;
    else
        if board&#40;EnpassantSquare+1&#41;=-1 then SaveMove&#40;EnpassantSquare+1,EnpassantSquare+10,5&#41;
        if board&#40;EnpassantSquare-1&#41;=-1 then SaveMove&#40;EnpassantSquare-1,EnpassantSquare+10,5&#41;
    end if
end if

end sub

[Michael Sherwin]

Thanks, I will have a look and then add it to my collection.

[Alex Lobanov]

Very simple move generator with precalculated square array (freebasic):

sample knight move:

Code: Select all

sub GEN_MOVES (moves() as cmove,nummoves as integer)

 dim from as ubyte, target as ubyte, square as ubyte
 dim s as integer
 dim tmove  as cmove

 nummoves = 0
 
 if whiteturn = true then '--white move--                 
  for from = a1 to h8
   select case board(from)
    case wn  '--knight--
     tmove.from = from
     for s = 0 to 7                          
      square = knighttable(from, s)
      if square=endtable then exit for
      target = (ccolor and board(square)) 
      if target <> cwhite then              
       tmove.target=square
       moves&#40;nummoves&#41;=tmove &#58; nummoves += 1                 
      endif
     next s
     ......
    end select
  next s
 else  '-- black move--
 ......
 end if
end sub

knighttable(from, s) - square array.
endtable = stop marker.

for sliding piece:
4 ray (4 for)

Code: Select all

for s = 0 to 6                      
 square=rooktable(from, s)
 if square=endtable then exit for
 target=(ccolor and board(square)) 
 if target = empty then          
  tmove.target=square:tmove.typemove=normal
  moves(nummoves)=tmove
  nummoves += 1
 elseif target=cblack then 
  tmove.target=square:tmove.typemove=capture
  moves(nummoves)=tmove
  nummoves+=1
  exit for
 elseif target=cwhite then 
  exit for
 endif
next s

for s = 7 to 13
...
next s
for s = 14 to 20
...
next s
for s = 21 to 27
...
next s