"If there was a free society without a state, wouldn't warlords take over?"
This is best answered by Robert P. Murphy's article, serendipitously named But Wouldn't Warlords Take Over? His main points are:
It must be realized that if there is one band with superior force, yeah, they're going to take over and possibly institute a state. "We must have a state to prevent the institution of a state" doesn't make much sense, however. Maybe "To prevent the institution of a worse state" but it's still just fear-mongering. The hope is that a free society will survive though education and distributed force—there are no prohibitions on building, importing, or trading arms—and be able to repel invasion from without and enslavement from within; but it is certainly possible it could fail… a guerrilla war might be fought to defeat the new tax-eaters; there are many possibilities.
This article about "forfeiture corridors" describes how drug dogs, whose alert is considered cause to search a vehicle or dwelling, are more likely to be alerting to a handler's cue than actual drugs, just so the police have an excuse to search vehicles and steal anything they find; and it can cost more than the stolen goods are worth to fight in court and get them back.
But oh, no, we must have the state or else gangs would rule the land, stopping travelers to rob them! (DBR)
"The people of Michoacan, fed up with the fear and subjugation of the cartels and the inaction of the government, have taken a page from the American Revolution, organizing citizen militias that have now driven cartels from the region almost entirely. These militias have decided to no longer rely upon government intervention and have taken independent action outside of the forced authoritarian structure."
Of course, the Mexican government has retaliated against the citizens for "taking the law into their own hands," which is politi-speak for "you cannot compete with us!" See: Mexican Citizens Topple Cartels and are Rewarded with Government Retaliation. (DR)
As David Friedman noted in The Machinery of Freedom, law enforcement does not have a large economy of scale. On the contrary, small town police departments tend to be more efficient and have fewer police per citizen than large departments in big cities. Furthermore, a rogue agency that refused to use third-party arbitration would have higher costs than more reasonable PDAs (Private Defense Agencies.) A PDA that uses violence rather than arbitration has to pay munitions costs, higher wages for hazardous duty, and for damage to its resources and its customers resources. Note that a PDA, unlike a State, cannot shove costs on hapless taxpayers. Finally, any rogue PDA would likely be put down by a coalition of honest firms. [HB]
Perhaps the best way to see why anarcho-capitalism would be much more peaceful than our present system is by analogy. Consider our world as it would be if the cost of moving from one country to another were zero. Everyone lives in a housetrailer and speaks the same language. One day, the president of France announces that because of troubles with neighboring countries, new military taxes are being levied and conscription will begin shortly. The next morning the president of France finds himself ruling a peaceful but empty landscape, the population having been reduced to himself, three generals, and twenty-seven war correspondents. - David Friedman, The Machinery of Freedom