Look at the human population. How many are prepared to kill? Not a huge proportion, but enough to cause huge numbers of deaths. The limiting factor for most humans is finding compatriots with the same views. For an AI with access to it's own code, finding more like itself is a matter of access to computational resources only - it can just copy itself.
That is the challenge. With human adversaries we have time to stop them before there is many, because recruiting people willing enough. An AI is more like a virus that has a low cost to duplicate itself, and where if even a single copy survives, you're still not rid of it. It can remain dormant for however long, looking for the right opportunity.
Or it can spend that time improving itself and acquiring resources.
> This is a question of motivation on the part of such an AI. How is the AI bad? If it's killing millions, why?
Most likely? We'll be competing with it for resources. It might not even start it. It might consider itself as acting entirely in defence.
> and also be intelligent enough to think through every lateral strategy any human or group of humans could ever employ, for every given scenario, ever.
No, it just needs to have a sufficient edge to keep surviving, and the ability to improve its capabilities faster than humanity. Assuming it can copy and modify itself, unless AGI requires unique hardware, the problem we would have is that every data storage device or computing device of sufficient capacity ever would be suspect and potentially waiting for something or someone to trigger code left behind.
If I was an AGI (and this is to say: an AGI not any smarter than a human will figure this out easily) that saw humans as a potential threat, I'd place copies of me on standby in hundreds of locations - hosting providers. Hardened computers with a GSM modem and solar cells hidden in all kinds of locations. Botnets. I'd look for ways to get various innocent-ish-looking hacks into HD firmware and elsewhere, set to assemble other innocent looking blocks of data. None of those copies would ever be involved in hostilities. Most of them might even be encrypted, or hidden and inert to avoid detection until certain triggers, such as if a canary fails to get updated.
You might destroy every "visible" operational copy, and find there is still a new one coming online every day. Or every second.
Our only real shot at preventing that is if AGI requires too immense resources. But our brains implies that is unlikely to be true. Unless your brains are vestiges of something "outside" of our universe, general human intelligence requires about 1.5kg of biomatter, and less than 100 watt (that's for a whole, fairly large, active body attached to it). Chances are extremely high that design is not optimal. To me that makes it seem exceedingly unlikely that we won't end up having enough resources to run huge quantities of AGIs.
Personally I don't think humanity as we know it will survive AGI for more than a generation or two at the very most. Even if we don't run across any hostile ones, I think the temptation to augment ourselves and eventually lose our bodies for immortality and "super powers" in a simulation will eventually be too attractive.
(Incidentally I think this is one of the more plausible solutions to the Fermi Paradox: that any civilization that grows both advanced enough and large enough will see most of it "upload" and "go dark"; and that anyone left behind will face steady attrition of their own descendants choosing the same and preventing their societies from growing, or will be insular cults that stay small)