This paper explores the inner workings of algorithms that computers may use to play Chess. First, we discuss the classical Alpha-Beta algorithm and several improvements, including Quiescence Search, Transposition Tables, and more. Next, we examine the state-of-the-art Monte Carlo Tree Search algorithm and relevant optimizations. After that, we consider a recent algorithm that transforms Alpha-Beta into a “Rollout” search, blending it with Monte Carlo Tree Search under the rollout paradigm. We then discuss our C++ Chess Engine, Homura, and explain its implementation of a hybrid algorithm combining Alpha-Beta with MCTS. Finally, we show that Homura can play master-level Chess at a strength currently exceeding that of our backtracking Alpha-Beta.

The idea for this thesis emerged from my senior design capstone project, A Wearable Threat Awareness System. A TFmini-S LiDAR sensor is used as one component of this system; the functionality of and signal processing behind this type of sensor are elucidated in this document. Conceptual implementations of the optical and digital stages of the signal processing is described in some detail. Following an introduction in which some general background knowledge about LiDAR is set forth, the body of the thesis is organized into two main sections. The first section focuses on optical processing to demodulate the received signal backscattered from the target object. This section describes the key steps in demodulation and illustrates them with computer simulation. A series of graphs capture the mathematical form of the signal as it progresses through the optical processing stages, ultimately yielding the baseband envelope which is converted to digital form for estimation of the leading edge of the pulse waveform using a digital algorithm. The next section is on range estimation. It describes the digital algorithm designed to estimate the arrival time of the leading edge of the optical pulse signal. This enables the pulse’s time of flight to be estimated, thus determining the distance between the LiDAR and the target. Performance of this algorithm is assessed with four different levels of noise. A calculation of the error in the leading-edge detection in terms of distance is also included to provide more insight into the algorithm’s accuracy.