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

[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.

[gamerman]

I like the way you put that, x4000. I read the earlier post and it didn't occur to me that a random move has the chance to be bad or good with the same equality. But making a bad move list could be confusing, since each move would only be bad or good based on your strategy in addition to your opponents. You'd almost have to play multiple games with another person and map out all the possible strategies or find them in some sort of online Chess digest. I like your approach though. I wouldn't have thought of it.

[zebramatt]

Let me see if I understand what you're asking.

1. You want the AI to, at any given point in the game, consult the database of best possible moves and then either find one fit for the particular situation or, if none are found, calculate the best possible moves for that situation and store them in said database.

2. You also want, however, for the player to be able to beat the AI from time to time, certainly on lower difficulty levels - rather than establishing an inevitable lose/draw scenario.

3. I'm also taking it as given that the AI will be able to choose from a variety of 'best' moves at any given time, so as not to become overly predictable - although I can see that, in terms of achieving 1, this isn't altogether necessary.


Assuming my interpretation is correct, it would seem to me that reconciling 1 and 2 requires the AI consult the db and either find a best move or calculate same and then, based on some difficulty factor, either play that move or do something else. At difficulty 6, for example, it might have a 40% chance of playing a move which is not one of the best moves from the db. Presumably that move would just be any allowable move chosen at random, excluding those on the db.

Of course, that does mean dedicating some processing power to calculating random sub-optimal moves on the fly - but only after the best moves have been calculated. It's just about disconnecting what the AI actually does from what it knows it should do. (Of course, if it were to store the randomly calculated sub-optimal moves in a db and then be allowed in future lower-difficulty scenarios to simply chose from amongst them (rather than from amongst the optimal moves) that would reduce the CPU footprint for those difficulties going forward - but it sounds like you don't want to compromise the content of your 'best moves db' to that end.)

There's no guarantee of difficulty in this solution, however. Just because a randomly selected sub-optimal move isn't by definition a 'best' move doesn't mean it's not a 'good' move. You might end up with a low end difficulty randomly selecting lots of quite good suboptimal moves 90% of the time and still beating players at that skill level.

Is any of that helpful?

[mindloss]

I realize this is far too late to be useful to you, but I'll just leave this here anyway because it's an interesting question and I thought about it for a few minutes so now I feel compelled to do a mini core dump.

I would say the answers above are undoubtedly best in terms of dev-time-to-measured-success ratio: limiting search depth or including a randomization factor. However, if you wanted to get fancy and be able to adjust the granularity of the difficulty really well, I would think you could modify your minimax a bit and make it a "lesstomore" algorithm, to coin an ugly term. I realize this is somewhat incompatible with relying on a persistent minimax database, but if you're able to support the calculation for it at runtime, you could tweak a minimax to purposely choose, say, the second best move in every situation, or the moves that over the course of the game most closely approach some percentage of what the optimum eval score (as determined by your actual minimax database) would be for that point, or artificially inflate the value of branches where the human player has a bunch of bad moves and one good move (that one seems especially good for (human) training purposes), etc... there are plenty of similar options to play with there. I'm sure if this is a viable approach, people have already formalized it, perfected it and written about it to a great extent, i.e. it'll be easily googleable.