bitwise operations

Monkey Forums/Monkey Programming/bitwise operations

NoOdle(Posted 2012) [#1]
I am attempting to implement a Bitboard for a chess game. I had originally opted for a 2d array but the speed is awful when calculating moves so I have decided to change the data structure.

http://en.wikipedia.org/wiki/Bitboard#Chess_bitboards

I have never used bit operations before so it is a little confusing at first. I just need to check that I am on the right tracks before I try anything more complex. Here is a runnable example demonstrating a grid. I don't know about the Pow() stuff, it doesn't seem right to me but that might be because I have been following c++ and java tutorials on the topic.

Any help, advice, criticism or reassurance is greatly appreciated!

Import mojo

Class MyApp Extends App

	Field boardA : Int
	Field boardB : Int
	
	Method OnCreate()
		SetUpdateRate 60

		'set top line board A
		boardA = boardA | 1
		boardA = boardA | 2
		boardA = boardA | 4
		boardA = boardA | 8
		boardA = boardA | 16
		boardA = boardA | 32
		boardA = boardA | 64
		boardA = boardA | 128

		'set top line x = 2 and x = 4 for board B
		boardB = boardB | 2
		boardB = boardB | 8
				
	End Method
	

	Method OnUpdate()
	End Method
	

	Method OnRender()
		Cls 0, 0, 0	

		'draws grid	
		For Local i : Int = 0 Until 64
			Local x : Int = i Mod 8
			Local y : Int = ( i / 8 ) Mod 8
			'ands both boards, sets red if both have a bit at location
			If ( boardA & Pow( 2, i ) & boardB & Pow( 2, i ))
				SetColor 255, 0, 0
			Else
				SetColor 255, 255, 255
			Endif
			DrawRect x * 32, y * 32, 31, 31
		Next
		
	End Method

End Class


Function Main()
	New MyApp()
End Function



Jesse(Posted 2012) [#2]
I was going to try to show you that the Shl is faster than Pow but than I run into some problems. there seems to be a bug that allows Pow to calculate numbers longer than 32 bit but not stored in a variable

this should produce the same result:

Print Pow(2,32)
Print (1 Shl 32)

but they don't and even though you can Print the Pow result directly, you can't store it.

a = pow(2,32)
b = (1 shl 32)
Print a
Print b

in reality the Pow should not return a value larger than 32 bit.

also the Shl is wrapping around but it should not. so it's a bug on both.


Gerry Quinn(Posted 2012) [#3]
Pow is a floating point function - it is working correctly. There is no integer version.

The Shl does seem incorrect. Note, though, that Monkey does not guarantee that ints are only 32 bits long.


Jesse(Posted 2012) [#4]
really?
this code produces the result below:
		For Local i : Int = 0 Until 64
			Local q = Pow(2,i)
			Print i+"  "+q+"   "+(1 Shl i)+"    "+ Pow(2,i)
		Next


Does this seem right to you:

0 1______1______1
1 2______2______2
2 4______4______4
3 8______8______8
4 16______16______16
5 32______32______32
6 64______64______64
7 128______128______128
8 256______256______256
9 512______512______512
10 1024______1024______1024
11 2048______2048______2048
12 4096______4096______4096
13 8192______8192______8192
14 16384______16384______16384
15 32768______32768______32768
16 65536______65536______65536
17 131072______131072______131072
18 262144______262144______262144
19 524288______524288______524288
20 1048576______1048576______1048576
21 2097152______2097152______2097152
22 4194304______4194304______4194304
23 8388608______8388608______8388608
24 16777216______16777216______16777216
25 33554432______33554432______33554432
26 67108864______67108864______67108864
27 134217728______134217728______134217728
28 268435456______268435456______268435456
29 536870912______536870912______536870912
30 1073741824______1073741824______1073741824
31 -2147483648______-2147483648______2147483648
32 0______1______4294967296
33 0______2______8589934592
34 0______4______17179869184
35 0______8______34359738368
36 0______16______68719476736
37 0______32______137438953472
38 0______64______274877906944
39 0______128______549755813888
40 0______256______1099511627776
41 0______512______2199023255552
42 0______1024______4398046511104
43 0______2048______8796093022208
44 0______4096______17592186044416
45 0______8192______35184372088832
46 0______16384______70368744177664
47 0______32768______140737488355328
48 0______65536______281474976710656
49 0______131072______562949953421312
50 0______262144______1125899906842624
51 0______524288______2251799813685248
52 0______1048576______4503599627370496
53 0______2097152______9007199254740992
54 0______4194304______18014398509481984
55 0______8388608______36028797018963970
56 0______16777216______72057594037927940
57 0______33554432______144115188075855870
58 0______67108864______288230376151711740
59 0______134217728______576460752303423500
60 0______268435456______1152921504606847000
61 0______536870912______2305843009213694000
62 0______1073741824______4611686018427388000
63 0______-2147483648______9223372036854776000



html5 same with flash

Note, though, that Monkey does not guarantee that ints are only 32 bits long.



Well, At least it should have consistency within the target.


AdamRedwoods(Posted 2012) [#5]
Interesting!


AdamRedwoods(Posted 2012) [#6]
Interesting! Float to Int conversion using Pow()?


Floyd(Posted 2012) [#7]
I don't know much about mobile hardware, but on x86 the 32-bit integer shifts wrap so that shifting 32 bits is the same as shifting 0 bits. I assume this is because the instruction codes only have five bits, for a maximum of 31, for the size of the shift.

The displayed values of Pow(2,i) are clearly wrong for large i. For example

63 0______-2147483648______9223372036854776000

You know that's wrong because the trailing 0s mean the number is divisible by 10, and thus also by 5. Of course it is really divisible only by whole lot of 2s. The "float to string" operation, which produces the decimal digits being displayed, is ( as far as I know ) limited to double precision. It can't generate enough digits to show Pow(2,63) with full accuracy.


muddy_shoes(Posted 2012) [#8]
It's right in that it's doing what the target language does as far as converting floats to ints. Javascript doesn't actually have integers, so Monkey just uses floatval|0 to push the result through the pretend 32-bit signed integer bitwise operators and get a truncated value.


Gerry Quinn(Posted 2012) [#9]
Yes, it is correct. You are implicitly casting a large floating point number to a 32-bit int that is too small to hold it. The result is probably unspecified, but Monkey appears to choose 0 in such a case.

Try this:

Local f:Float = Pow( 2, 34 )
Local g:Int = f
Print f
Print g

Of course it would be better to write:
Local g:Int = Int( f )
...in such a case.


Floyd(Posted 2012) [#10]
I suspect the idea of using bitboards is fundamentally flawed if you are looking for speed on multiple mobile platforms. They would need native support for 64-bit boolean operations.


Gerry Quinn(Posted 2012) [#11]
I think there is truth in what Floyd says, but they might still end up faster than doing things the standard way.

But the real trouble with Chess is that you need deep wide minimax trees compared to most games.


Gerry Quinn(Posted 2012) [#12]
I hadn't realised that Javascript didn't have integers - I thought it had some kind of long-int a la Python. I ran into the same issue when I was creating an emulation of the MSVC rand() function (it's in the Code forum) and found I had to chop back the seed to 32 bits after every iteration, otherwise after a while it started always returning zero in HTML5.

I did think at the time that they were rather short for long-ints, which should happily have gone to 1000 digits or more. Javascript using floating point to emulate ints explains it.


NoOdle(Posted 2012) [#13]
Thanks for the input everyone. I thought I was going a little mad with the shl results I was experiencing. I might have to stick with arrays for now and hope that I can get it fast enough.


Gerry Quinn(Posted 2012) [#14]
Chess is a difficult game to get right. Part of the reason is that it requires such deep and wide analysis, and part of it is that it is so well-understood - both the game itself and the computer implementations. To provide a convincingly strong opponent you will almost certainly need an opening book, for example - simple minimax implementations are irresistably attracted to 1.P-Q4, 2.N-QB3 which is a viable opening as White but usually rather committal as Black. And bitboards are only the start of the techniques devised to optimise analysis in chess - other standard elements include transposition tables and quiescence search.

If Chess is what you want to do, go for it - but I personally would be inclined to pick another game.

If you are using arrays, be sure to use a 1D array. 2D Monkey arrays will kill your speed for certain!


NoOdle(Posted 2012) [#15]
Yea Chess is tricky but most of the techniques are fairly straight forward. I've implemented minimax before and have been reading up on transposition tables. Stumbled across quiescence the other morning but haven't looked into it.

This is all my mates fault, he wanted his own Battle Chess game and decided it would be an easy game for me to make! He doesn't program or realise how much work goes into the AI. At first I refused and then started to warm to the idea when I saw how ugly the MacBook chess game is!

If you are using arrays, be sure to use a 1D array. 2D Monkey arrays will kill your speed for certain!

Cheers that is definitely quicker and recommended by a few tutorials I was reading. The gamedev website has a nice 6 part Chess tutorial.
http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-ii-data-structures-r1046

If Chess is what you want to do, go for it - but I personally would be inclined to pick another game.

Nope Chess is not what I want to do but it has been an interesting learning experience. I think I'll go back to finishing my Framework....


Gerry Quinn(Posted 2012) [#16]
Wow, that is a great tutorial! Advanced, and yet perfectly clear.