World Draughts Forum

It is currently Tue Jun 19, 2018 12:34

All times are UTC+02:00




Post new topic  Reply to topic  [ 7 posts ] 
Author Message
PostPosted: Thu Dec 21, 2017 17:44 
Offline

Joined: Mon Oct 17, 2016 09:05
Posts: 17
Real name: Robin Messemer
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:
 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 :)


Top
   
PostPosted: Thu Dec 21, 2017 19:40 
Offline

Joined: Sat Apr 28, 2007 14:53
Posts: 739
Real name: Ed Gilbert
Location: Morristown, NJ USA
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.
Quote:
Currently, I use a base 5 index function which seems utterly wasteful.

Why do you say it is wasteful?

-- Ed


Top
   
PostPosted: Thu Dec 21, 2017 20:01 
Offline

Joined: Mon Oct 17, 2016 09:05
Posts: 17
Real name: Robin Messemer
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:


Top
   
PostPosted: Thu Dec 21, 2017 20:20 
Offline

Joined: Sat Apr 28, 2007 14:53
Posts: 739
Real name: Ed Gilbert
Location: Morristown, NJ USA
Quote:
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.
Quote:
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


Top
   
PostPosted: Thu Dec 21, 2017 22:27 
Offline

Joined: Mon Oct 17, 2016 09:05
Posts: 17
Real name: Robin Messemer
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


Top
   
PostPosted: Thu Dec 21, 2017 23:07 
Offline

Joined: Sat Apr 28, 2007 14:53
Posts: 739
Real name: Ed Gilbert
Location: Morristown, NJ USA
Quote:
Did you use a fixed ply search when generating those games ?

See this post for more details: http://laatste.info/bb3/viewtopic.php?f=53&t=6808&p=114452#p114452 With two 8-core computers it takes a few weeks to play ~1M games.

-- Ed


Top
   
PostPosted: Fri Dec 22, 2017 09:41 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 244
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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 7 posts ] 

All times are UTC+02:00


Who is online

Users browsing this forum: No registered users and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited