I am programing a connect-5 game on a 13x13 ,15x15, 19x19, 20x20 board. Uptil now I have kept everything flexible, i just have to change the board size and rest would be managed by my program.
Its quiet natural that it has massive search space and one cannot deal with normal negamax, so I have added alpha-beta to it. AI part is working correctly, but at 4plys, its taking about 6 seconds.
When I profiled by logging things, I am was convinced that maximum time was spent on evaluation which at this point is nothing but only winning conditions, managed by 2- for loops per winning condition.

So I decided to speed it up, I need to represent in some other way, bit boards. Here is my main issue, considering the least board size of 13x13 , there are 169 square. I donot know how to represent this big number in bit boards.
In chess, generally 1L<<square[..] is written, I donot know how to write 1L<<169, this is just too huge for primitive data type.

Thinking of solution here, I thought that it might be better to make 2 2-dimensional arrays, check_Horizontal[size_col][0] and check_Vertical[size_row][0](It doesnt matter, number rows and colums are same.)
So if I want to check for horizontal win in 5 in rows , I access check_Horizontal[i/size_col][0] where i is index from 0 to size_row*size_col.

It also involves copying in respective locations, something which takes considerable amount.
as well this is fine for horizontal and vertical, but for diagonals, its going to be much more complex.

The other way by which I can speed up the process is to modify my alpha-beta, but this I can do in any time by adding killers and hashtables, its not a problem, even after doing this, the time taken by evaluation will be the same. Hence I want to tweak and speed up the evaluation and then get my hands on search again.

Is there any better approach? am I missing something.
Please help.
Thank you.

I doubt bitboards are going to be an advantage for such large boards. Can you post the current code to check for victory conditions? Since you need to check this after each move, you only need to check around the place where the last piece was placed. If you are a bit careful, this won't be expensive.

Currently i am using this as my winning conditions.
winning conditions.

I would use a single number to refer to a position. You can leave a padding of values that indicate you are out of the board. Then the code could look something like this:
int side = board[last_move];

static int const direction[4]={1,15,16,17}; // Say, for a 15x15 board with one space for padding

for (int i=0; i<4; ++i) {
int d = direction;
int count = 0;
for (int x = last_move+d; board[x] == side; x += d)
++count;
for (int x = last_move-d; board[x] == side; x -= d)
++count;
if (count >= 4)
return WIN;
}
return NO_WIN;


@Alvaro: Thank you, this works and has reduced time requirement.

static int const direction[4]={1,15,16,17}; // Say, for a 15x15 board with one space for padding
[/quote]
I think you meant 1,15,14,16.
and I dont get why
(count >= 4)
return WIN;
5 to connect so it seems that count>=5 is what you meant.
Another way I thought, but didnt program was to use Big-Number family , in java they are BigIntegers and i think in C++ they are BigNums(I am not very much familiar with C++).
Speaking of it, they would allow me to get bit-operations on them, but in java, these numbers are treated in string format which are slow and thus i think this might be one of the reason why you said that bit boards wouldnt be useful, if there are any, please mention them.

I will upload the coded game in form of applet and will post the link soon. If you have time, then play against it and tell me where it is going wrong.
My line of thinking is as follows, get the evaluation working fast, this starts with winning condition, as if the evaluation is slow, more conditions will even slow it down.
then add killers and transposition tables. Once if I can reach uptil 8-10 plys, with this, I think my AI would be a decent player.

Am I on a proper track?

@Alvaro: Thank you, this works and has reduced time requirement.

static int const direction[4]={1,15,16,17}; // Say, for a 15x15 board with one space for padding

I think you meant 1,15,14,16.[/quote]
No, I meant what I wrote. It is important to use a board that is slightly larger and has padding consisting of squares that are marked as being out of the board.

and I dont get why
(count >= 4)
return WIN;
5 to connect so it seems that count>=5 is what you meant.[/quote]
Again, I meant what I wrote. I am not counting the last stone itself, only the ones that line up with it, and I only need 4 of those to win.

Another way I thought, but didnt program was to use Big-Number family , in java they are BigIntegers and i think in C++ they are BigNums(I am not very much familiar with C++).
Speaking of it, they would allow me to get bit-operations on them, but in java, these numbers are treated in string format which are slow and thus i think this might be one of the reason why you said that bit boards wouldnt be useful, if there are any, please mention them.[/quote]
Yes, basically any implementation of large bitboards will require operations with integer types that are much larger than what the machine natively supports, so you can't expect them to be reasonably fast.

I will upload the coded game in form of applet and will post the link soon. If you have time, then play against it and tell me where it is going wrong.[/quote]
That would be fun!

My line of thinking is as follows, get the evaluation working fast, this starts with winning condition, as if the evaluation is slow, more conditions will even slow it down.
then add killers and transposition tables. Once if I can reach uptil 8-10 plys, with this, I think my AI would be a decent player.[/quote]
You are probably right. I think in this game it might be important to make the depth of the tree very non uniform, because some moves are much more likely than others. For instance, forced moves probably shouldn't count when measuring depth, so branches with many forced moves can be explored deeper.

Am I on a proper track?
[/quote]
Yes, I think you just need to keep working on it for a while. It is very important to see what types of positions are misplayed by the program, and then think hard about what to do about it. Also, really strong programs have procedures for accepting or discarding a change, usually consisting of a few thousand fast games against a previous version of the program or other reference programs. That's the only way to make sure that your changes all improve performance. But automated testing is probably overkill at this stage.

@Alvaro: Forcing moves seems to be a good idea, but since the approach of the search is depth first, I dont see a way how one can do it without searching the board.
I think if this has to be done, I have to change the approach to Iterative deepening which will go depth by depth in depth-first search.

Here is the applet link, please let me know how it works.
You need to press reset to reset the game, move to make computer play, the ply indicates maximum depth of search. and you have choice of negaMax with or without alpha-beta pruning.
The latest move from computer is marked with orange dot. (I know the graphics sucks, but I will soon make it look good.)

Please let me know if it works correct or not. At this point, only winning conditions are inputted.
and winning score is 1000.

Thank you.

Your program seems correct, but the lack of an evaluation function makes it very weak and boring. You can probably make it much more interesting (and stronger, believe it or not) by using a random number between -500 and +500 as your evaluation function. Of course a real evaluation function would be better, but this will make the search capture some notion of mobility and will add variety to the game with very minimal effort.

@Alvaro: Wow man, randomizing things did really work nicely as compared to strength, however, it took time significantly longer than before.
Without randomizing, at depth of 4, it took about 350-400 msecs, with randomizing it took about slightly more than 4000 msec. 10 times the before.
But I think this might be a tradeoff. I am planning soon to tweak it with weighing of squares, near the center, higher the score and also later on chaining effects, what you think about it.
What do you suggest.

At this point when I have randomized things, do you think it will be a good idea to play large number of games between the two versions and accumulate some sort of data, I am unable to think what that data should be and the reason behind it. May be it can be used to develop some heuristics.

Can you suggest something in this and the over all game through out?
-Thank you.