Fatalism is widespread, but not nearly universal enough that we can say it was the norm 15000 years ago.

For that matter, people who were pretty fatalist were still capable of using chance for purposes of fairness. The democrats in ancient Athens come to mind. I'm also pretty sure the (Christian) apostles' use of chance was also more about avoiding a human making the decision, than about divination.