Tangibles are small, graspable objects that act as input devices or physical representations of digital data. Oftentimes, it is desirable to track the position of tangibles on a surface and their relation to each other. However, outside-in tracking techniques - such as capacitive touchscreens or cameras - require setting up elaborate infrastructure and are prone to occlusion or interference. We propose Dothraki, an inside-out tracking technique for tangibles on flat surfaces. An optical mouse sensor embedded in the tangible captures a small (36×36 pixel / 1×1 mm), unique section of a black-and-white De-Bruijn dot pattern printed on the surface. Our system efficiently searches the pattern space in order to determine the precise location of the tangible with sub-millimeter accuracy. Our proof-of-concept implementation offers a recognition rate of up to 95%, robust error detection, an update rate of 14 Hz, and a low-latency relative tracking mode.