{"content":{"sharePage":{"page":0,"digests":[{"id":"64439740","dateCreated":"1382230153","smartDate":"Oct 19, 2013","userCreated":{"username":"vladpetric","url":"https:\/\/www.wikispaces.com\/user\/view\/vladpetric","imageUrl":"https:\/\/www.wikispaces.com\/i\/user_none_lg.jpg"},"monitored":false,"locked":false,"links":{"self":"https:\/\/chessprogramming.wikispaces.com\/share\/view\/64439740"},"dateDigested":1531475774,"startDate":null,"sharedType":"discussion","title":"Demystifying the Magic Multiplier?","description":"Hi everyone,
\n
\nMy name is Vlad, I'm new to this site and I'm also an Othello dude. While working on an Othello project, unaware of all the good work done here, I essentially rediscovered the magic bitboard trick :) (mask, multiply, shift).
\n
\nHowever, I came to the same conclusion from a different angle. I looked at how multiplication works, and I was able to determine the multipliers in a straightforward manner - no need for brute force, just a direct algorithm.
\n
\nWould you mind taking a look at my writeup?
\n
\nhttp:\/\/drpetric.blogspot.com\/2013\/09\/bit-gathering-via-multiplication.html<\/a>
\n
\nI have no idea if this is original, but at the very least it seems to improve on the brute force finding.
\n
\nThank you!","replyPages":[{"page":0,"digests":[{"id":"66269904","body":"Hi Vlad,
\n
\nwelcome to cpw and thanks for sharing your writeup on magic multiplication. I am not yet entirely sure I understand your bit gathering correctly - whether you are able to analytically find magic multipliers to process two lines (i.e. file and rank, or both diagonals of a square) in one and-mul-shift-run? With two lines, many intermediate overflows may occur in multiplication, which is the issue in brute force searching for magics bitboards, likely with some initial guessing, i.e lowest bit set, highest bit set, number of bits, etc.. The second issue is to reduce the index range for attack-sets - there is not necessarily a bijective but surjective mapping from masked two-line occupancies to an occupied-index, where different redundant outer occupancy-bits "behind the first blocker" in each of up to four ray-directions, and therefor equal attack-sets, may share the same index.
\n
\nSingle-line multiplication is further elaborated in
\n- General Setwise Operations- Multiplication<\/a><\/li>
- Occupancy of any Line<\/a><\/li>
- Flipping Mirroring and Rotating - Rank, File and Diagonal<\/a><\/li>
- Kindergarten Bitboards<\/a><\/li><\/ul>
\nwhich seems the kind of overflow-less single-line multiplication you propose on your site. May be I miss something?
\n
\nRegards,
\nGerd","dateCreated":"1382259352","smartDate":"Oct 20, 2013","userCreated":{"username":"GerdIsenberg","url":"https:\/\/www.wikispaces.com\/user\/view\/GerdIsenberg","imageUrl":"https:\/\/www.wikispaces.com\/user\/pic\/1202793136\/GerdIsenberg-lg.jpg"}},{"id":"66285136","body":"Hi Gerd,
\n
\nI believe that Rank to File, Diagonal to Rank covers what I was doing pretty well :) (was unaware of them). How would the second diagonal (mirrored) be handled though? My writeup converts it into a Rank (assuming that rank means adjacent bits) as well. Probably not a big deal.
\n
\nRegards,
\nVlad","dateCreated":"1382304781","smartDate":"Oct 20, 2013","userCreated":{"username":"vladpetric","url":"https:\/\/www.wikispaces.com\/user\/view\/vladpetric","imageUrl":"https:\/\/www.wikispaces.com\/i\/user_none_lg.jpg"}},{"id":"66301054","body":"Ok, I think the "carryless" multiplication to manifold numbers - or later bitpattern is very old. However, it took me some time to understand it though, when I played around with this stuff some years ago, using De Bruijn sequences and randoms. In processing bitboards, multiplication technique rather than a sequence of shift\/add became applicable with fast 64-bit multiplication on AMD K8 and Intel Core2 architectures.
\n
\nCheers,
\nGerd","dateCreated":"1382347049","smartDate":"Oct 21, 2013","userCreated":{"username":"GerdIsenberg","url":"https:\/\/www.wikispaces.com\/user\/view\/GerdIsenberg","imageUrl":"https:\/\/www.wikispaces.com\/user\/pic\/1202793136\/GerdIsenberg-lg.jpg"}},{"id":"66308950","body":"Oh I totally get that now :). Thanks for your patience :)
\n
\nAs an aside, would an algorithm that takes a number of arbitrary bit positions (0-63) and produces the tightest packing be helpful? I think I have an idea as to how to approach it. Not going to be P-class (if original order is not preserved, the problem smells of NP completeness), but perhaps better than trial&error.","dateCreated":"1382363704","smartDate":"Oct 21, 2013","userCreated":{"username":"vladpetric","url":"https:\/\/www.wikispaces.com\/user\/view\/vladpetric","imageUrl":"https:\/\/www.wikispaces.com\/i\/user_none_lg.jpg"}},{"id":"66314876","body":"Sure, you are very welcome to improve our mathematical understanding on magic bitboards.","dateCreated":"1382370690","smartDate":"Oct 21, 2013","userCreated":{"username":"GerdIsenberg","url":"https:\/\/www.wikispaces.com\/user\/view\/GerdIsenberg","imageUrl":"https:\/\/www.wikispaces.com\/user\/pic\/1202793136\/GerdIsenberg-lg.jpg"}}],"more":0}]},{"id":"10615562","dateCreated":"1238184273","smartDate":"Mar 27, 2009","userCreated":{"username":"ludamad","url":"https:\/\/www.wikispaces.com\/user\/view\/ludamad","imageUrl":"https:\/\/www.wikispaces.com\/i\/user_none_lg.jpg"},"monitored":false,"locked":false,"links":{"self":"https:\/\/chessprogramming.wikispaces.com\/share\/view\/10615562"},"dateDigested":1531475774,"startDate":null,"sharedType":"discussion","title":"Magic bitboards in Java","description":"Do they have to be handled differently due to lack of unsigned multiplication? Is there any java source code implementing magic bit boards I can look at?","replyPages":[{"page":0,"digests":[{"id":"10617540","body":"The "lower" half of the 128-bit product long * long is same for signed or unsigned multiplication. For unsigned shift right you have >>>, so Java has no problem with Magic Bitboards.
\n
\nSomething like this...
\n\n