Perft inital position and number of transpositions

[Henk]

https://www.chessprogramming.org/Perft_Results

Does not give number of similar positions encountered.
Might be handy when testing transposition table.
Testing the key (IKey) used in search.

Code: Select all

  ITranspositionTable<IKey, UlongValue> ttable;
  

[Ajedrecista]

Hello Henk:

https://www.chessprogramming.org/Perft_Results

Does not give number of similar positions encountered.
Might be handy when testing transposition table.
Testing the key (IKey) used in search.

Code: Select all

  ITranspositionTable<IKey, UlongValue> ttable;
  

Do you mean cases like 1.- d4, d5; 2.- Nf3 and 1.- Nf3, d5; 2.- d4 in a Perft(3) run? If so, JetChess perft counter suits your need. I have posted many 'unique positions' runs over the years, just search "unique positions" and my username in the advanced search engine of TalkChess (the gear button next to the magnifying glass button, top right of the page).

You can download JetChess 1.0.0.0 using the WayBack Machine:

JetChess

It is a standalone programme, so just download, unzip and enjoy. For counting unique positions, you must tick:

Mode\Position
Flags\en passant

The number of different positions (not perft) from the starting position are known up to 11 plies (OEIS A083276):

Code: Select all

Positions( 1) =              20
Positions( 2) =             400
Positions( 3) =           5,362
Positions( 4) =          72,078
Positions( 5) =         822,518
Positions( 6) =       9,417,681
Positions( 7) =      96,400,068
Positions( 8) =     988,187,354
Positions( 9) =   9,183,421,888
Positions(10) =  85,375,278,064
Positions(11) = 726,155,461,002

You can compute 'unique positions' from any input position with JetChess, although very big calculations would either overflow or take much, much time. You only need to copy the FEN to the clipboard and paste it to JetChess through the 'Copy from Clipboard' button at the top right, next to the left and right yellow arrows.

Regards from Spain.

Ajedrecista.

[Henk]

I get for perft(4) 66377 unique positions instead of 72078

But I already doubted that key would be correct.
Maybe I should try a fen (string) as a key to find the bug.

Then I can test pos.ConvertToFen too.

[Ajedrecista]

Hello Henk:

Using advanced search, searching unique by username sje (the great Steven Edwards, who sadly passed away four years ago) at Programming and Technical Discussions subforum returns interesting results. Steven computed unique positions for different plies starting from the initial positions and uploaded the FEN strings. These links are dead now, but someone here might have downloaded them and can share these files if they keep them stored.

Here are some interesting threads:

Unique position data files

Unique(n) (n=0..6) FEN files available for download

Location of files for the Perft(14) project

These FEN strings, if available somehow, can be useful for you when tracking bugs. Good luck!

Regards from Spain.

Ajedrecista.

[Henk]

Being stupid. Key uses MD5 hashalgorithm. So no doubt it doesn't find all duplicates.

First I have to make it possible to accept strings as key.

Code: Select all

    class ULongTTable<T> : TranspositionTable<IKey, UlongValue> where T: IEqualityComparer<IKey>, new()
    {
        public ULongTTable() : base(new T() )
        {
        }
    } 
    
    public class PerftAlgoritm
    {
        IKeyFactory keyFactory;
        ITranspositionTable<IKey, UlongValue> ttable;

        public PerftAlgoritm()
        {
            keyFactory = new StringKeyFactory();
            ttable = new ULongTTable<StringKeyEQComparer>();
        }
        
        public ulong PerftUnique(IChessPosition pos, int depth)
        {

            var key = keyFactory.BuildKey(pos);
            var entry = ttable[key];
            if (entry != null)
            {
                return 0;
            }
             ulong res;
            if (depth == 0)
            {
                res = 1;
            }
            else
            {
                var legalMoves = LegalMoveGenerator.ListLegalMoves(pos);
                res = (ulong)legalMoves.Sum(mv => (long)PerftUnique(pos.Move(mv), depth - 1));
            }
            if (ttable[key] == null)
            {
                ttable = ttable.Add(key, new UlongValue(res));
            }
            
            return res;
        }
    }
    
     public class StringKeyFactory : IKeyFactory
    {

        public StringKeyFactory()
        {
        }
        public IKey BuildKey(IChessPosition pos)
        {
            var key = new StringKey(pos);
            return key;
        }

        public IEqualityComparer<IKey> BuildKeyComparer()
        {
            return new StringKeyEQComparer();
        }

    }
    
     public class StringKey : IKey
    {
        public string Fen
        {
            get;
        }

        public StringKey(IChessPosition pos)
        {
            Fen = pos.ConvertToFen();
        }

        public override int GetHashCode()
        {
            return Fen.GetHashCode();
        }
        public bool Equals(IKey key)
        {
            return ((StringKey)key).Fen == Fen;
        }
    }
    
    public class StringKeyEQComparer : IEqualityComparer<IKey>
    {
       
        public bool Equals(IKey x, IKey y)
        {
           return ((StringKey)x).Equals((StringKey)y);
           
        }

        public int GetHashCode(IKey key)
        {
            return ((StringKey)key).GetHashCode();          
        }
    }
    
     public class StringKeyFactory : IKeyFactory
    {

        public StringKeyFactory()
        {
        }
        public IKey BuildKey(IChessPosition pos)
        {
            var key = new StringKey(pos);
            return key;
        }

        public IEqualityComparer<IKey> BuildKeyComparer()
        {
            return new StringKeyEQComparer();
        }

    }
 

[Henk]

O wait MD5 can not be the error because hashkey is not used for testing position equality. It is always two steps. Using hashkey and then testing on equality of positions in same bin. I forgot how it works. But usage of MD5 can not be the error.

[Dann Corbit]

Hello Henk:

Using advanced search, searching unique by username sje (the great Steven Edwards, who sadly passed away four years ago) at Programming and Technical Discussions subforum returns interesting results. Steven computed unique positions for different plies starting from the initial positions and uploaded the FEN strings. These links are dead now, but someone here might have downloaded them and can share these files if they keep them stored.

I really like SJE. He wrote our PGN standard, and he shared the things he learned freely.
We should all think deeply about that.

I think unique EPD positions is (in itself) very hard to define.
First of all, we have e.p. squares, of which 97% are utterly bogus (the e.p. tag cannot be fulfilled because there is no legal capture move).
And does the half move clock matter or not? That one is especially hard to define.

[Henk]

O wait MD5 can not be the error because hashkey is not used for testing position equality. It is always two steps. Using hashkey and then testing on equality of positions in same bin. I forgot how it works. But usage of MD5 can not be the error.

[Looks like telling lies all the time]
When I use this class plus MD5 then MD5 might be the problem.
I think easier to use normal perft, compute two keys and compare.

Or better forget it. Price of efficiency.

Only need to test if transposition table and key class does not contain errors.

Code: Select all

  public class Key : IKey
    {
       
   
        readonly byte[] rep;

        public byte this[int i]
        {
            get
            {
                return rep[i];
            }
        }


        public Key(IChessPosition pos, HashAlgorithm hashAlgorithm)
        {
            rep = pos.ComputeHashKey(hashAlgorithm);
        }

        public bool Equals(IKey key)
        {
            int k = 0;
            foreach(var b in rep)
            {
                if (b != ((Key)key)[k]) return false;
                k++;
            }

            return true;
        }

    
        public override int GetHashCode()
        {
            return BitConverter.ToInt32(rep);
        }
    }