Hi everyone. I'm building a Connect 4 program and I was hoping to further improve the performance with some better move ordering.

My program implements the following:

-Bit-Boards based on Jon Tromp's design.

-NegaMax AB pruning.

-Transposition tables (Although I believe a lot of collisions are occurring).

-Iterative deepening.

-Killer heuristic.

Currently from start it can search up to a depth of 21 in 8 seconds however it does this based on very stiff move ordering. Given an array statically ordered from center to edge (see below) of every board position it will loop over and check to see if the corresponding move is open.

int orderMoves={iterate , killerMoves[depth][0], killerMoves[depth][1], 21,22,23,24,25,26,28,29,30,31,32,33,14,15,16,17,18,19,35,36,37,38,39,40,7,8,9,10,11,12,42,43,44,45,46,47,0,1,2,3,4,5};

However, no matter what I replace this with it unfortunately is always slower. One method I was considering was implementing history heuristics as it apparently offers a great speed increase for a Connect 4 engine but I am having trouble understanding how. If anyone has any knowledge and can help me out that would be great. :)

The version of history heuristic that Fhourstones (John Tromp's exhaustive-search program) uses works well for me: Keep one number per player and square of the board. Sort moves in descending order of their values on that table. When a move produces a beta cut, increase its entry in the table by the number of moves that preceded it, and decrease the entries for those moves by one.

So if you try moves 5, 16 and 29 and 29 produces a beta cut, do table[player][5]--, table[player][16]-- and table[player][29]+=2.

Thank you for replying! So given that, the sum of the series will always remain 0? If so I believe I have implemented this correctly but I am not seeing positive results so something I am doing must be wrong.

for (int i=0;i<48;i++){

if (((1L<<(48-i))&allMoves)!=0){ //Add all available moves to array.

moves[i/7]=i;

}

}

for (int i=0;i<7;i++){//Just sort the available moves.

for (int j=1;j<(7-i);j++){

if (history[turn][moves[j-1]]<history[turn][moves[j]]){ //Order moves in descending order based on history[turn][position].

int temp=moves[j-1];

moves[j-1]=moves[j];

moves[j]=temp;

}

}

}

Then when a cut off occurs I do this:

for (int i=0;i<movesTaken.size();i++){ //movesTaken is an array of all moves performed up until now.

history[turn][movesTaken.get(i)]--;

}

history[turn][move]+=movesTaken.size();

movesTaken.clear();

Here is a printout of what the moves are and their values. *Move numbers correspond to bitBoard position.

-----

17, 2757

10, 1198

32, 254

0, -7226

35, -8510

42, -9743

24, -11841

-----

Here is an example of a history: [55589, 18459, 404506, 770523, 484749, 592282, 0, 62085, -242440, -298837, 74761, -78500, -28116, 0, 56330.............................

I've previously disabled heuristics and have just left it at win, loss or draw to make the program faster. Could that be factoring into this? If not my best guess would be either the inefficiency of the sort or perhaps I need to cap the values off at a min and max value?

A few things are a bit odd in your code:

* Your move generation looks rather ugly. You should have code to quickly loop over the set bits on a bitboard: https://chessprogramming.wikispaces.com/Bitboard+Serialization?responseToken=9a40d754294bf64d917c555203cd7b7b

* Your first move should be one coming from the transposition tables, if there was a hit: https://chessprogramming.wikispaces.com/Hash+Move

* Why do you need a container `movesTaken' at all? All you need is an index into the array of moves.

Anyway, hash move is probably the most important element of move ordering. Discussing the effectiveness of history heuristic without implementing that makes no sense.

You may want to try the killer heuristic as well: https://chessprogramming.wikispaces.com/Killer+Heuristic