The mind of the chimpanzee poses something of a paradox. In captivity, chimpanzees show cognitive abilities which seem only rarely used in the wild. The contention of this thesis is that the added complexity which a fission-fusion social system imposes on a Machiavellian primate requires complex decision-making, and that it is in making these decisions that wild chimpanzees use their cognitive abilities. The extent of social complexity in the relationships between male chimpanzees was investigated in an unprovisioned community in the Budongo Forest, Uganda. Statistical modelling and the construction of mutually exclusive hypotheses were used to determine the extent of tactical behaviour and decision-making in the social lives of these animals. Male chimpanzees were found to live in a highly dynamic social milieu, showing complex patterns of associations which appeared to be tactical. Chimpanzee males changed their associates frequently every day, and it is argued that each change represents a decision. In pursuit of association strategies, each decision is tactical, and requires cognitive representations of strategic goals and the relationships between individuals. Individual males appeared to deliberately select their association partners. Over time, the tendency a dyad had to associate changed, as individuals sought to alter their relationships, in pursuit of association, and broader social, strategies. Two such association strategies were distinguished; one in which individuals maintained an even level of association with other males, another where males concentrated on associating with only a few others. Individuals switched from one strategy to another as their social status changed, although both strategies could lead to increased status. A preference for higher status males as nearest neighbours lead to competition for proximity partners, and individuals, particularly the middle to high status males, appeared to use proximity tactically. In choosing between grooming partners, male chimpanzees appeared to to select the individual with whom they had the stronger association relationship. This implied a cognitive comparison of the value of each relationship. Male ranging patterns were examined, and the majority of time was spent within small core areas which were both partially overlapping and distinct. Each male?s core area had a similar habitat composition, and overlap between core areas was positively related to dyadic association tendencies. It is hypothesised that these core areas function to enable the location of individuals to be predicted by other members of the community. The cognitive demands of decision-making by wild chimpanzees is discussed in relation to the demonstrated abilities of captive individuals, as are the implications for an understanding of the evolution of the chimpanzee mind