bitwise operations
Monkey Forums/Monkey Programming/bitwise operations
| ||
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 |
| ||
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. |
| ||
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. |
| ||
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. |
| ||
Interesting! |
| ||
Interesting! Float to Int conversion using Pow()? |
| ||
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. |
| ||
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. |
| ||
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. |
| ||
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. |
| ||
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. |
| ||
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. |
| ||
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. |
| ||
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! |
| ||
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.... |
| ||
Wow, that is a great tutorial! Advanced, and yet perfectly clear. |