The French in Algiers viewed with concern the success of a Muslim government and the rapid growth of a viable territorial state that barred the extension of European settlement. Abd al Qadir fought running battles across Algeria with French forces, which included units of the Foreign Legion, organized in 1831 for Algerian service. Although his forces were defeated by the French under General Thomas Bugeaud in 1836, Abd al Qadir negotiated a favorable peace treaty the next year. The treaty of Tafna gained conditional recognition for Abd al Qadir's regime by defining the territory under its control and salvaged his prestige among the tribes just as the shaykhs were about to desert him. To provoke new hostilities, the French deliberately broke the treaty in 1839 by occupying Constantine. Abd al Qadir took up the holy war again, destroyed the French settlements on the Mitidja Plain, and at one point advanced to the outskirts of Algiers itself. He struck where the French were weakest and retreated when they advanced against him in greater strength. The government moved from camp to camp with the amir and his army. Gradually, however, superior French resources and manpower and the defection of tribal chieftains took their toll. Reinforcements poured into Algeria after 1840 until Bugeaud had at his disposal 108,000 men, one-third of the French army.