I thought HALO had good AI, and there was a writeup somewhere (IDK where) by Bungie devs about how they implemented complex seeming behaviour with some relatively simple/dumb rules.
Combining route finding, goals & priorities, situational awareness, and also adding in some flakiness so it's not perfect can give a really good and usable approximation to AI from the human players perspective.
The computer player needs to have rules and knowledge in place about the game such as how to get around the maps and how to shoot / evade the enemy all without being too good.
I remember the first time I played HALO and the guys talked to each other, and it wasn't just random sound effects they actually did the thing they were talking about. If the Elite guy said to "flank him" they would try to flank you or whatever, it was very cool.