Index funtion for eval func

Discussion about development of draughts in the time of computer and Internet.
Post Reply
CheckersGuy
Posts: 17
Joined: Mon Oct 17, 2016 09:05
Real name: Robin Messemer

Index funtion for eval func

Post by CheckersGuy » Thu Dec 21, 2017 17:44

Hey,
I am currently working on my evaluation function and wanted to copy the approach used by Scan and other programs. I use regions of the size 4x4 and need a good index function.

Currently, I use a base 5 index function which seems utterly wasteful.

(PseudoCode)

Code: Select all

 for(uint32_t i=0;i<8;++i){
        uint32_t maske =1<<(i+shift);
        if((maske&(bp&k))==maske){
            index+=factor*4;
        }else if((maske&(wp&k))==maske){
            index+=factor*3;
        }else if((maske&(bp))==maske){
            index+=factor*2;
        }else if((maske&(wp))==maske){
            index+=factor*1;
        }else{
            index+=factor*0;
        }
            factor*=5;
    }
}
My board implementation uses 3 bitboards. BP=BlackPieces,WP=WhitePieces,K=Kings.

What index function are u using and could you explain why your index function works :)

Ed Gilbert
Posts: 776
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: Index funtion for eval func

Post by Ed Gilbert » Thu Dec 21, 2017 19:40

I'm looking at this now for use in an eval function for 8x8 English checkers. I think you can speed up the index calculation using the PEXT instrinsic that is available on newer CPUs.
Currently, I use a base 5 index function which seems utterly wasteful.
Why do you say it is wasteful?

-- Ed

CheckersGuy
Posts: 17
Joined: Mon Oct 17, 2016 09:05
Real name: Robin Messemer

Re: Index funtion for eval func

Post by CheckersGuy » Thu Dec 21, 2017 20:01

Oh, I thought there were better index functions. Better = less memory :P

I am using this for checkers as well and initial resullts were quite promising. May I ask which optimization algorithm u use for the logistic regression ? I tried stochastic graidient descent which works but is still rather slow. The Gauss Newton method is next on my list if I find a good matrix library which supports sparse matrices :wink:

Ed Gilbert
Posts: 776
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: Index funtion for eval func

Post by Ed Gilbert » Thu Dec 21, 2017 20:20

Oh, I thought there were better index functions. Better = less memory
Only if you want to consider compression. There are a lot of indexes that are not used because they don't represent quiet positions, or men of the wrong color on a king row. But even the simplest compression schemes like RLE are a lot slower, and I don't think it is a good tradeoff for an eval.
May I ask which optimization algorithm u use for the logistic regression ?
I'm using simple gradient descent, with a few iterations (epochs?) of mini-batches before using the whole dataset for the remaining iterations. Convergence takes about 3-1/2 hours using 75M training positions. Nothing fancy, single-threaded optimizer.

-- Ed

CheckersGuy
Posts: 17
Joined: Mon Oct 17, 2016 09:05
Real name: Robin Messemer

Re: Index funtion for eval func

Post by CheckersGuy » Thu Dec 21, 2017 22:27

Intresting :P 75M position is really a lot and I am not even close to that. Did you use a fixed ply search when generating those games ? If so, how many plies were sufficient ? I am currently doing a 7 ply search during the "generating-games"-part.Takes me quite some time to generate a lot of unique positions

Ed Gilbert
Posts: 776
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: Index funtion for eval func

Post by Ed Gilbert » Thu Dec 21, 2017 23:07

Did you use a fixed ply search when generating those games ?
See this post for more details: viewtopic.php?f=53&t=6808&p=114452#p114452 With two 8-core computers it takes a few weeks to play ~1M games.

-- Ed

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Index funtion for eval func

Post by MichelG » Fri Dec 22, 2017 09:41

CheckersGuy wrote:Oh, I thought there were better index functions. Better = less memory :P

I am using this for checkers as well and initial resullts were quite promising. May I ask which optimization algorithm u use for the logistic regression ? I tried stochastic graidient descent which works but is still rather slow. The Gauss Newton method is next on my list if I find a good matrix library which supports sparse matrices :wink:
I wouldn't bother with stochastic methods; the eval score function is a simple convex function. Stochastic methods just add complexity in this case.

I am using a multithreaded conjungated gradient algorithm for optimization . It works fairly well, but gradient descent works as well and is much easier to program.

For small number of weights and data points dragon runs pretty quickly. As the number of weights/data points increase, they don't fit into cache anymore and the algorithm slows down.

As for the number of training positions; i think 5-10 million is a good point to start and experiment with. As you increase the training set, the performance will keep increasing every time you double the amount of positions.

Michel

Post Reply