State capacity is often described as one of the most important explanations of civil conflict. Yet current conceptualizations of state capacity typically focus exclusively on the state, ignoring the relational nature of armed conflict. We propose that conflict arises in areas where relational state capacity is low, i.e., where the state commands less control over its subjects than do local elites. Relational state capacity is likely to be low in regions that are poorly accessible from the state capital, but internally highly interconnected. We test our theory using African data on physical accessibility of ethnic groups to capture opportunities for control. To measure accessibility, we rely on deep learning to digitize detailed historical road maps for Africa fully automatically. Using an instrumental variable design based on network simulations, we find strong support for our claim that low relational state capacity is a key determinant of armed conflict in Africa.