Anarchism
Every anarchy in existence in history and in the world today result in a bunch of warlords fighting for domination, those petty warlords are either plain dictators, communist dictators, or theocrat dictators.
Nobody else gains any traction, and the absolute worst of things happen to people.
that being said, unlike the communist utopia (which is a nightmare), an AnCap society would be a true utopia if it manages to exist. But for it to exist human nature itself has to change... or perhaps a pseudo religion based on it has to occur with very zealous followers, enough so that they will spontaneously form into volunteer armies to crush threats against their society.
I think you're confused; you both refer to a point in time where there were no hierarchical relationships, while referring to people who were very into dominance through violence. Does this sound like a non-hierarchical situation to you? No? Then don't bother me, or anyone for that matter, with this fallacy again, thank you. I apologize if I seem blunt, but I hear this over and over again, so much so I'm honestly surprised you didn't mention Somalia somewhere. Anarchism stems from secular rationalism; the warlords you mention are not rational, for they primarily operate through abusing your sense of fear, not through exposing the truth, and work only to increase their own control over the people they dominate, such as installing a state and controlling the currency and keeping the illusion of democracy going and making up boogeymen etc. etc.
Now, onward to your second point: the argument of human nature. This is countered simply:
List all the relationships you've had with people that didn't occur at the barrel of a gun. You have a lot of them, yes? People whose company you enjoy, who you and they benefit from your existing in each other's presence. Now list all the relationships you've had with people that did. Not as many as previously, but still there. We can now assert that having voluntary relationships and involuntary relationships are within human nature. Precisely where, then, does the argument of "human nature must change" stem from, with regards to voluntary interaction, when human nature readily includes this observable, and certainly not new, phenomenon? This seems like the type of response I'd get from a hermit but to anyone who has had actual relationships with other people, it sounds alien to assume that voluntary interaction in the name of self-interest would be nearly impossible without some kind of brainwashing:
in the real world, this happens daily, spontaneously, in every nation and by every ethnicity, in emergencies, outside of emergencies, for whatever reason you could think of.People naturally participate with other people, especially, but not limited to, when they both benefit from each other's time and energy. I don't know where you're from that this doesn't happen but at least you have enough freedom to exercise your ability to pick and choose with whom you associate on the Internet, another one of those anarchic areas where the state is abhorred from touching. Strange that most people aren't actively attacking each other's websites; you'd almost think they were acting in mutual self-interest...how unnatural!