General Category > Game Development

Chess (or other board game) AI. How to implement difficulty levels?

(1/2) > >>

Buttons840:
I've made an AI for the board game Pentago (not popular, but I really like it), and there are other abstract games I'm considering creating an AI for.  I use a simple minmax algorithm to find the best move, and then I store it in a transposition table.  I need to dumb down the AI, but I can't truly dumb it down because it stores it's moves in a database which is referred to in future games -- I can't allow stupid moves into this database, lest the AI make stupid moves when it should be playing at full strength.

Having created the program to play it's best at all times, it beats me every time.  I'm now considering how to implement difficulty levels.  I know X has some good blog posts about AI design, but his techniques don't apply to board games of perfect knowledge IMO.

x4000:
This is definitely always the challenge with certain kinds of games.  Especially games of skill, like FPS games or games of something like billiards.  I remember reading an article a few years back about how some billiards AI programmers had to figure out a way to make the AI not just run the table on every turn it had, since it was perfectly capable of precisely calculating everything.  The same is true of FPS opponents -- it's an illusion that they can't headshot you every time.

So anyway, you'll find a lot of info about games of skill and how the hardest part of the AI is to make them scaled down in difficulty in a way that seems realistic.

When it comes to board games, that's a different matter of course.  In a chess game, I think that one way to approach it is to only let the AI look so far ahead, or to only process so many decision points at a time.  That's part of what I did for the Tidalis AI, although since that's realtime the other big part was slowing the AI down so that it made moves at a more human pace.

I think that a database of stupid moves can also be quite effective for realism.  If you have a sliding scale of difficulty levels, say 1-10 or whatever else, then you can limit the various moves in your database to only being >= certain difficulties, and <= other difficulties.  That's also something I do heavily in AI War, and somewhat in Tidalis.

So if there are really stupid moves, only let those happen below a certain difficulty.  If there are really excellent moves, only above another certain difficulty.  And so on.  On the lowest AI War difficulties, the AI automatically attacks where it is most outnumbered, for instance. 

If you build in a weighted random factor so that the AI is more likely to pick from the stupid move set on the lowest difficulties, that can give you even more of a spread.  Or even just randomly move something without any thought at all on the lower difficulties, part of the time, can give a surprisingly good approximation of an unskilled player just fumbling about.

TechSY730:
Although coding in "reasonable stupidity" is a very tough task.
I do like the idea that the highest level AI would not being subject to that, and will not hold back. (Like it will not consult the "stupid moves" list; probability may be used, but not to model human error; the AI will take full advantage that it can do near perfect physics on the fly; etc.) That would not be cheating, as they don't get any extra resources, information, rule immunities, or whatever, that the player does not have. The only thing they are leveraging fully that they didn't on lower levels is their "M4D M4TH SK1L22"

Naturally, this would be somewhat annoying to play against, but hey, you asked for the hardest, so the AI will not hold back.

Buttons840:
I don't want to limit the AI's intelligence, but simply coerce it into make poor moves for the sake of the player.  I hope to see if I can "solve" these games I'm working with.  Checkers was solved a while ago and it was proven that a particular AI was unbeatable.  There was no longer any calculations required, the AI would simply consult a table and then make the given move, and by following the table the AI would either win or tie.

I'd like to build such a table which mean all processing power during playtime should be building up the master database, not a "stupid moves database" so to speak.  I also don't want to limit the depth the CPU will search.

x4000:
I think you'll find that when you limit your approach based on semantics, you'll get a limited success, but that's just my take.  For a game like AI War, I've had to blend together just about every kind of game-style AI (plus a few not all that often used in games at all) to get a good result.  Checkers is a solved game, as you mention, and so that's why that sort of no-processing master table works.  It also has a wildly finite number of board states compared to, say, Chess.

That said, from an AI standpoint there are only three ways to intentionally make a bad move that I can think of:
1. Choose from a bad move list.
2. Do something random (which has just as much a chance of being a good move, in the end).  I lump reducing the depth search into this, as that increases the random component of the move, at least.
3. Programmatically determine at runtime that X condition exists and that it would be wonderfully stupid to do Y.

In AI War, I used 2 and 3 off that list.  It sounds like you want a big move list database in general, which is why 1 off the list seemed a good solution for you.  Now I'm not quite sure what you're looking for, since you don't seem to want to handicap the AI while still having it play on a scale.  You can't "coerce" an AI to do anything, as it doesn't really think.  Remember, you're not making a true AI in the first place -- you're making a simulation of a true AI, like all the rest of us.  It's all just algorithms and math and randomness, and how you choose to apply those components to get a smart or a stupid result. 

It's easy to anthropomorphize the result, which is great, but one of my hugest lessons with AI War, and why the AI there seems better than most other games while being designed and coded in a fraction of the normal time, is this: It doesn't matter what the AI does, just what the player thinks the AI is doing.  Truly.  It's like being a stage magician, not like teaching bicentennial man to walk.

Navigation

[0] Message Index

[#] Next page