Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Negamax AI and staying on the same turn


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
26 replies to this topic

#21 Álvaro   Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 13 March 2013 - 09:01 AM


Ooops! It returns 0x4000000000000000l, of course. Sorry about that.

I think it should return 0x4000000000000000 which I'm interpreting that the horizontal mill for square 1 is closed.


That's what I was saying. If the `l' at the end of the constant confused you, just ignore it: It's just C syntax for "long constant".
 

Using the same concept, is it possible to determine:

1. if mills are open (1 square is still empty, 2 owned by the player)

Yes.

2. if mills are blocked (2 squares owned by the player, 1 by the opponent)

Yes.

3. get adjacent squares for a square

You can create a table of 24 numbers that contains bitboards indicating the adjacent squares for each square.

4. get empty squares

  long empties = ~(bitboard[0]|birboard[1]);

5. etc....

Basically, yes.

And if this would be possible, I'm assuming that shifting bits needs to be done and it wouldn't work on signed values.

No, I am sure you can work around that.

Try to write code to solve one of these problems (say, find blocked mills). If you can't figure it out, ask again and I'll post some code.

EDIT: If you are going to perform all these other operations as well, I would forget about the trick of initializing the counters to 1, because it will complicate matters. So initialize to 0 instead, and now checking for mills becomes
  long mills = (magic_sum + 0x1111111111111111l) & 0x4444444444444444l;

Edited by Álvaro, 13 March 2013 - 09:09 AM.


Sponsor:

#22 cryo75   Members   -  Reputation: 143

Like
0Likes
Like

Posted 14 March 2013 - 05:22 AM

Ok, I think I will start small with using bitboards because I need to understand what the code is doing. So I read up on bitboards but all the resources I found relate to chess. However I didn't give up!!

As this game has just 24 positions I was thinking of using int. I will also have to handle signed because Java doesn't support unsigned. So I did the following:

int[] bb = {0, 0};

bb[0] = bb[0] | (1 << 0) | (1 << 1) | (1 << 2);
bb[1] = bb[1] | (1 << 9) | (1 << 21);

int free = ~(bb[0] | bb[1]) & 0xFFFFFF;

In the above code, I'm setting the positions' bits for each player, then I get the free spaces. This works fine because the result is:

110111111111110111111000

Now my question is: Do I have to loop through each bit in the result and check if the bit is set? If set, then it's free. If I use bitboards in this case what's the advantage over using a 1D array if I'm not going to get rid of the loops?

#23 Druzil   Members   -  Reputation: 618

Like
0Likes
Like

Posted 14 March 2013 - 04:05 PM

You don't have loop over all the bits.  There is a trick to loop over just the bits that are set.

if

b=110111111111110111111000

 

then

 

c = b & (0 - b)

 

will give you the lowest bit that is set

 

once you process this bit

 

you can then do

 

b = b^c

 

and start the process over again until b = 0



#24 cryo75   Members   -  Reputation: 143

Like
0Likes
Like

Posted 15 March 2013 - 03:21 AM

&nbsp;

You don't have loop over all the bits.&nbsp; There is a trick to loop over just the bits that are set.
if
b=110111111111110111111000
&nbsp;
then
&nbsp;
c = b &amp; (0 - b)
&nbsp;
will give you the lowest bit that is set
&nbsp;
once you process this bit
&nbsp;
you can then do
&nbsp;
b = b^c
&nbsp;
and start the process over again until b = 0

&nbsp;

Thanks for the tip. That will save lots of iterations!

#25 cryo75   Members   -  Reputation: 143

Like
0Likes
Like

Posted 15 March 2013 - 08:26 AM

I'm nearly finished with implementing bitboards (still didn't start testing though). I have bitboards for the player, opponent, free spaces, mill positions, player mill and opponent mill positions. Each bitboard is 24bits long and representats the spaces on the board with board position 0 being the first bit (from the right).

 

I have 2 small problems which i can't figure out:

 

1. How to find out if a player mill is blocked by an opponent (2 player pieces and 1 opponent piece)

2. How to find out if a player mill is open (2 player pieces and 1 free space)

 

Do you have any tips on how I can calculate this?



#26 Álvaro   Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 15 March 2013 - 08:50 AM

I would describe the position with two bitboards (White, Black) and two magic sums. It might be reasonable to also have other bitboards that you might use often, like empties, so you don't keep recomputing them in different parts of the program (this happens in chess; not sure if it's worth it in this case).
 
About the 2 small problems you can't figure out, this code solves them:
 
#include <cstdio>

int main() {
  // These are numbers like magic sums, designed so every combination                         
  // of white and black occupation is tested                                                  
  long white = 0x0000000123012010l;
  long black = 0x0000000000111223l;

  // White's count ends in "10" while black's count ends in "0"                               
  long white_blocked_mills = ~white & (white>>1) & black & 0x1111111111111111l;

  // White's count ends in "10" while black's count ends in "1"                               
  long white_open_mills = ~white & (white>>1) & ~black & 0x1111111111111111l;

  std::printf("%016lx\n", white);
  std::printf("%016lx\n", black);
  std::printf("%016lx\n", white_blocked_mills);
  std::printf("%016lx\n", white_open_mills);
}
[EDIT: I found an easier way to code it than what I originally posted.]

Edited by Álvaro, 15 March 2013 - 09:03 AM.


#27 cryo75   Members   -  Reputation: 143

Like
0Likes
Like

Posted 15 March 2013 - 12:37 PM

Thanks. That will help!!






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS