Jump to content
  • Advertisement
Sign in to follow this  
mandar9589

Trying Bit Boards for Connect-4

This topic is 2565 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For this I have used the code which John Tromp provided. here is the link to his page John Tromp .
I am basically trying to implement only the winning conditions for my engine in bit boards.
I am sucessful when I tried to play this is tested in multiplayer mode, but it doesnt function when my AI plays. I have used print statements to check my code and found that the player array which holds bits of players, doesnot return same values in single player-mode and multiplayer mode. So something is fishy in my makeMove method and I tried to rectify it, but unsuccessful.
I also looked at Mr.Tromp's search method, but in a way its far too different than my implementation, so tried to modify and reuse the logic of bit-boards according to my code and think sort of messed it up.
Here is what I have coded so far.

public static void undoMove(int board1[], int square, boolean white) {
board1[square] = 0;
int n;
n = moves[--nplies];
players[nplies&1] ^= 1L<<--height[n];
}



public static void makeMove(int[] board1, int square, boolean white) {

int n = square % 7;
players[nplies&1] ^= 1L<<height[n]++;
moves[nplies++] = n;
}


I have hand tested the evaluation conditions and it works fine.
Can anybody suggest something about this?

Share this post


Link to post
Share on other sites
Advertisement
I don't know how you decided that the problem is in those functions.
Find a simple test case where the code does the wrong thing. Then use the debugger to step into the code and check if the variables have the values that you expected.

We can't do that for you without the entire code. And, besides, it's boring. ;)

Share this post


Link to post
Share on other sites
@alvaro:Thanks for replying.

I hand tested the code. I printed the players[0] and players[1]. Once a winning condition was found, I put these numbers in those expression of shifts.
Previously when I implemented normal 2d-array negamax+abp, that time the abp code worked perfectly and hence, I concluded that abp has no faults in it. So when I googled more, I found that procedure to implement bit boards in search was similar to that of 2d-boards the only difference is the data structure used. So if my search function works properly with 2d-arrays then it should work with bitboards as well.
I just added the above lines to my makeMove and undoMove functions and tested it with Human-Human (Multiplayer) and it worked fine . but then we never use undoMove in 2 players serious game.
So according to my observation ,I think that the fault is somewhere in makeMove or undoMove.
When I tried to use the debugger, the values of player[0] and player[1] didnot match with the values that I obtained from multiplayer mode, with the same sequence of moves what can be the reason for this?.

I am actually surprised that it works with multiplayer mode but not with AI-mode.

I am still working on that but I donot know how to get it right so asking for help.:(
I have provided the code here, it contains entire code to write with negamax.(I have removed the abp, first would like to get this working then installing abp wouldnot be much of a problem ).
code

Share this post


Link to post
Share on other sites
I find your code hard to follow:
* Why is the array representation passed around as an argument while the bitboard representation is contained in data members of the NegaEngine class? Wouldn't it make more sense to have a Board class that would contain whatever representations you are using?
* Why is the "% 7" hard coded if the height and width are described in constants at the beginning of the code? And shouldn't it be "/ 7" instead (well, actually "/ H1")? It's hard to tell because the variable name n is uninformative, but I guess you are trying to determine in which column the square is...


EDIT: Also, when testing your low-level functions, you should write low-level tests (initialize an empty board, make a few moves, undo them, print out the board in the intermediate stages to make sure it looks as you expect...). Just trying the whole complicated program and seeing it fail will not give you any clues as to what you did wrong.

Share this post


Link to post
Share on other sites
@Alvaro: Thanks for replying.
* Why is the array representation passed around as an argument while the bitboard representation is contained in data members of the NegaEngine class? Wouldn't it make more sense to have a Board class that would contain whatever representations you are using?[/quote]

The above code is programmed using java, and since there is finite time taken to create objects, I havent used the OOP structure as it is. The code-style is bad and I accept it.
I made many changes in previous code and forgot to delete the unused variables and methods also I hurriedly coded the program so there are some magic numbers and I apologize for the same, so there are quiet a few of them. I think I may not worry of them either as deleting them would cause much of an issue and neither will it take lot of time,but I agree with you that its hard to read and thanks for pointing it out I will make the changes soon.
I didnot make class of Board as it would just add another object in the program making it sort of slower. The code I provided contains only the engine class.
As of now I am trying to code only the evaluation in bitboards and not other methods like PossibleMoves() which used arrays, I am trying to get it in steps and not at once. This again is highly inefficient because I am using two data-structure for the game which could be satisfied with only one, but since this is my first time in bit boards, I let efficiency took second place.So once I get my winning conditions working, I would switch to make PossibleMoves in bitboards and later other stuffs, slowly replacing the 2d-arrays by bitboards.


* Why is the "% 7" hard coded if the height and width are described in constants at the beginning of the code? And shouldn't it be "/ 7" instead (well, actually "/ H1")? It's hard to tell because the variable name n is uninformative, but I guess you are trying to determine in which column the square is...
[/quote]

I think that should be (square%7) or making the code eligible, it should be (square%columns) as I am taking the reference from Mr.Tromps code.here and a square in this term is (7*row_number+column_number).
The point is I am failing to see any visible particular in my code.
I tried hand-debugging and using debugger.

example: the makeMove() and undoMove()

int n = square % column; //Getting the column number
players[nplies & 1] ^= 1L << height[n]++; /*toggling between players[0]& players[1]
as it is based on the number of moves(nplies in the code)
played and filling with resp bits.*/

moves[nplies++] = n; /*Incrementing the moves array which
would later be used for displaying the moves.*/


board1[square] = 0; //Inefficeient.Used to undo the move in array-data struture.
int n;
n = moves[--nplies]; // denoting the last played column to vacate it.
players[nplies&1] ^= 1L<<--height[n]; /*toggling between players[0]& players[1]
as it is based on the number of moves(nplies in the code)
played and undoing with resp bits.*/


EDIT: Also, when testing your low-level functions, you should write low-level tests (initialize an empty board, make a few moves, undo them, print out the board in the intermediate stages to make sure it looks as you expect...). Just trying the whole complicated program and seeing it fail will not give you any clues as to what you did wrong.[/quote]

I am trying hands at bit boards for first time so do you think its a good idea to try it on comparitively complex game as connect 4? or should I go for Tic-Tac-Toe?
I printed the intermidiate moves and boards, but then the values in players[0] and players[1] are not equal to what I get in multiplayer mode. It seems that in multiplayer mode, functions quiet well, where the option of undo is not given.
I also have one more query, is there any other simple (effficiency is not an issue since this is my first time.) method to implement connect four in bit boards?

Share this post


Link to post
Share on other sites

* Why is the "% 7" hard coded if the height and width are described in constants at the beginning of the code? And shouldn't it be "/ 7" instead (well, actually "/ H1")? It's hard to tell because the variable name n is uninformative, but I guess you are trying to determine in which column the square is...


I think that should be (square%7) or making the code eligible, it should be (square%columns) as I am taking the reference from Mr.Tromps code.here and a square in this term is (7*row_number+column_number).
The point is I am failing to see any visible particular in my code.[/quote]

If you look at the diagram at the beginning of John's code (copied at the beginning of yours), you'll see that the convention is not what you think it is.

I am trying hands at bit boards for first time so do you think its a good idea to try it on comparitively complex game as connect 4?[/quote]
Connect 4 is fine.

I printed the intermidiate moves and boards, but then the values in players[0] and players[1] are not equal to what I get in multiplayer mode. It seems that in multiplayer mode, functions quiet well, where the option of undo is not given.[/quote]
If you suspect that the problem is with playing and undoing moves, make a test program that takes an empty board, plays a move in the middle of the board and undoes it. The board should be left in the same state you had before. When you have a test that fails, the simpler the test the easier it will be to debug.

I also have one more query, is there any other simple (effficiency is not an issue since this is my first time.) method to implement connect four in bit boards?[/quote]
There is nothing complex about this method. Bitboards feel very natural once you have worked on them for a while.

Why did you modify John's simple code where only the column number is used to identify the move?

Share this post


Link to post
Share on other sites
It seems like if your game logic functions differently with AI or a player, there is some sort of unnecessary coupling going on.

If I were to guess I'd say that your AI is changing something in the board when it is evaluating which move it should make.

Share this post


Link to post
Share on other sites
@way2lazy2care: Thanks for replying me.
@alvaro and way2lazy2care:I identified the cause of this.
During my getMove(), I undo all the moves and hence after returning the final square index, I donot change the values in the bit boards.
So there are same values in bit structure.
When I changed this, my program only looks for a win in 1 move. i.e next move should be the win then it plays that move,it doesnt care about the losses or anything.
Will look into this more later. Can it happen that there are some algorithms which might reduce the nodes evaluated so indirectly the time taken to compute the moves.
I read about null move pruning,and infact also implemented, but it played worse(Importance of parity in connect 4). so dropped the idea of null move. implemented Prob-Cut but either its ineffective in this game or my implementation is sloppy, I found that number of nodes increase drastically (And the time) as compared to only alpha-beta.
So are there any such algorithms which doesnot use the concept of null move or any such concept which is not applicable to connect 4.

Share this post


Link to post
Share on other sites
Null-move won't work on this game, because zugzwang is the common case, not the exception. Prob-cut is hard to tune, and it's unclear if it's even worth it. It might depend on some smoothness features of the evaluation function, which might be hard to achieve in connect 4, because of its all-or-nothing nature.

I don't know if there are any other algorithms that would give you a big improvement in this game. Fhourstones doesn't use anything too fancy and weakly solves the game in a few minutes, so perhaps you don't need anything too fancy.

Do you ever figure out if "%7" gives you the column or the row?

Share this post


Link to post
Share on other sites
@alvaro:Thanks for replying.
Do you ever figure out if "%7" gives you the column or the row?[/quote]
Yes, I figured it out while writing the code,that "%7" will give me the (col number -1) . Its the column number which when multiplied by H1(i.e 7, it will contain values like 0,7,14,21,28,35,42) and so on.
BTW why did you ask me this? Is there any flaw? perhaps I made a mistake or call my implementation sloppy by using magic numbers like 7, which makes the code hard to read.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!