algorithm - Determine if two chess positions are equal -

i'm debugging transposition table chess variant engine pieces can placed (ie. not on board). need know how i'm hitting key collisions. i'm saving piece list in each table index, along usual hash data. simple solution determining if 2 positions equal failing on transpositions because i'm linearly comparing 2 piece lists.

please not suggest should storing board-centric instead of piece-centric. have store piece list because of unique nature of placable , captured pieces. pieces in states occupying overlapping , position-less location. please @ description of how pieces stored.

// [piece list] //  // contents: location of pieces. //           values 0-63 board indexes; -2 dead; -1 placeable // structure: black pieces @ indexes 0-15 //            white pieces @ indexes 16-31 //            within each set of colors pieces arranged following: //            8 pawns, 2 knights, 2 bishops, 2 rooks, 1 queen, 1 king // example: piece[15] = 6 means black king on board index 6 //          piece[29] = -2 means white rook dead char piece[32]; 

a transposition happens when pieces moved in different order, end result same board position. example following positions equal:

1) first rook on a1; second rook on d7 2) first rook on d7; second rook on a1 

the following non-optimised general algorithm; , inner loop similar general problem, added restraint values in 0-63 happen once (ie. 1 piece per square).

for each color:     each piece type:         pieces in same position, disregarding transpositions? 

the following comparison not work because of transpositions. need way detect transpositions equal , report different positions.

bool operator==(const position &b) {     (int = 0; < 32; i++)         if (piece[i] != b.piece[i])             return false;     return true; } 

performance/memory consideration because table gets on 100k hits (where keys equal) per turn , typical table has 1 million items. henceforth, i'm looking faster copying , sorting lists.

"do not suggest should storing board-centric instead of piece-centric".

you're focused on not doing that, miss obvious solution. compare board-specific. compare 2 position lists l1 , l2, place elements of l1 on (temporary) board. then, each element of l2, check if it's present on temporary board. if element of l2 not present on board (and in l1), return unequal.

if after removing elements of l2, there still pieces left on board, l1 must have had elements not present in l2 , lists equal. l1 , l2 equal when temporary board empty afterwards.

an optimization check lengths of l1 , l2 first. not catch many discrepancies quickly, eliminates need remove elemetns of l2 baord , "empty board" check @ end. needed catch case l1 true superset of l2. if l1 , l2 have same size, , l2 subset of l1, l1 , l2 must equal.