Deterministic agents without memory or access to randomness. You also don't need free will to implement a 'mixed' strategy rather than a 'pure' strategy, as that problem calls for.
Given what leplen appears to mean by “free-will”, I wouldn't call any agent with access to randomness “deterministic” in this context.
Given the spike in free-will debates on LW recently (blame Scott Aaronson), and the usual potentially answerable meta-question "Why do we think we have free will?", I am intrigued by a sub-question, "what would it feel like to have/not have free will?". The positive version of this question is not very interesting, almost everyone feels they have free will most all the time. The negative version is more interesting and I expect the answers to be more diverse. Here are a few off the top of my head, not necessarily mutually exclusive:
Epistemic:
Psychological:
Physical:
For me personally some of these are close to the feeling of "no free will" than others, but I am not sure if any single one crosses the boundary.
I am sure that there are different takes on the answers and on how to categorize them. I think it would be useful to collect some perspectives and maybe have a poll or several after.