Single-cell organisms and various cell types use a range of motility modes when following a chemical gradient, but it is unclear which mode is best suited for different gradients. Here, we model directional decision-making in chemotactic amoeboid cells as a stimulus-dependent actin recruitment contest. Pseudopods extending from the cell body compete for a finite actin pool to push the cell in their direction until one pseudopod wins and determines the direction of movement. Our minimal model provides a quantitative understanding of the strategies cells use to reach the physical limit of accurate chemotaxis, aligning with data without explicit gradient sensing or cellular memory for persistence. To generalize our model, we employ reinforcement learning optimization to study the effect of pseudopod suppression, a simple but effective cellular algorithm by which cells can suppress possible directions of movement. Different pseudopod-based chemotaxis strategies emerge naturally depending on the environment and its dynamics. For instance, in static gradients, cells can react faster at the cost of pseudopod accuracy, which is particularly useful in noisy, shallow gradients where it paradoxically increases chemotactic accuracy. In contrast, in dynamics gradients, cells form de novo pseudopods. Overall, our work demonstrates mechanical intelligence for high chemotaxis performance with minimal cellular regulation.