Improve AI

[hamvocke]

Currently the AI plays random valid cards. This is the most trivial, non-predictable implementation but of course doesn't make sense for anyone seeking real fun and a challenging game.

We could implement different computer player personas that the human player can choose from. Each with a different approach of playing and therefore with a different difficulty.

Some ideas to approach implementation:

• heuristics-based, e.g. calculating Erwartungswert
• simulation-based (Monte Carlo) - calculate outcomes for all possible moves and pick the best one
• reinforcement learning - the most tricky one, but could be super fun. Train an AI with reinforcement learning

[lkoehl]

I want to spend some time trying to come up with an ai based on reinforcement learning. Never worked with Vue or AI before, which is a little of a road block but i want to look more into AI.
Another option would be using LSTMs but after some research it requires learning data which of right now, I don't have any. Combining LSTMs with Reinforcement Learning would be possible but I didn't find a library doing the heavy lifting.
Also I found a thesis on this topic combing the results of a Monte Carlo algorithm with the outcomes of the LSTM.

[hamvocke]

Amazing, that's super cool.

We're in the same boat here, I've never worked with reinforcement learning before and had to start from scratch, too.

This is going to be a long running investigation - it's likely that this will be incredibly fun, though.

When implementing the game, I made sure to keep a clear separation between vue.js (that is everything in frontend/src/components) and the logic it takes to play the game (that's everything in frontend/src/models). This should be helpful as it allows you to ignore everything related to presentation and vue.js when working on reinforcement learning or anything else that relates around implementing an AI of any sort.

For reference, the two very naive implementation for computer players are located in frontend/src/models/behaviors.js.

Feel free to dive into the subject head first. If you need any help or you want to share some thoughts, ideas or progress just let me know!

[hamvocke]

Oh, and when it comes to the issue of getting data: that's where the backend part of this repo is supposed to come into play. This is still very early and the backend doesn't do much at this point. The idea, however, is that the backend is going to collect how real-world human players play against different Doppelkopf AIs. I'm imagining something like coming up with something like [Chess notation] (https://en.m.wikipedia.org/wiki/Chess_notation) to record a Doppelkopf game. When finishing a game, the frontend will submit this data to the backend where it can be stored and analyzed later.

This should allow to investigate how well a certain AI is playing and how many games they win or lose. Thinking further, this data might be good input for machine learning efforts. Don't know if that would actually work 😄

[lkoehl]

Yes I already looked into your code and started a little bit with the implementation. Kudos for your code. You should be able to see the progress on the ai branch of the project, which I forked. I also implemented a very basic keyboard interaction. Is there a way to automatically start the next round after a trick is played? I saw the button is listening to a press to send the event. I didn't manage to start the next trick and end the round automatically. Right now I am triggering the events with button presses. Looking at your roadmap this could be a little refined and adapted.
I think these things need to be setup first to start a training. So it's also possible to see the AI playing against itself when it's learning.
Also I didn't manage to run the model just by itself without the frontend. Is this even possible with js and the files in the project?

The plans for the backend sounds great. I looked into it, but didn't quite got the hang of it. But thats something I don't need right now.

[hamvocke]

Yeah, you'll need to do some modifications in order to play without UI interaction.

A few things come to mind (this won't be all but it's all I can see while on the go):

When setting up the game (in game.js), make sure that all players are created as computer players, like this:

this.players = [
  new Player(randomNames[0], isComputer, "bottom", this),
  new Player(randomNames[1], isComputer, "left", this),
  new Player(randomNames[2], isComputer, "top", this),
  new Player(randomNames[3], isComputer, "right", this)
];

This should take care that nextMove() will be triggered automatically.

The only thing pausing the flow and waiting for human interaction is within nextMove() in round.js. With all computer players, this should be disabled. Now you "only" need to find a way to automatically start the first move (maybe calling nextMove()after the game has started, once) and triggering the next round (I suspect callingnextRound()ingame.js` somewhere within the loop would get you there).

Can look more into this tomorrow :)

[davidkaufmann]

I started working on an improved AI and I'm currently going for a basic rule based approach, which is obviously very opinionated and might reflect my type of playing style.

I believe this is the approach we should be going for, since right now the game is 'unplayable' in singleplayer.
I expect results much faster, going this way, although i do have some experience in ML.
Getting to a point where the AI knows with whom he plays and how to play, not in detail obviously, is mandatory to add value to the current game.
I honestly believe that we need to get there by taking small steps at a time, instead of coming up with somethign like AlphaGo for Doppelkopf.

I was able to implement a rule that triggers when a fehl is played, which behaves quite decent. Obviously it's not perfect, but it adds so much value to the play, knowing your opponent will trump you when he can with high value cards, trumping others too, to win the trick. Have look at Issue #42 for some more details.

[davidkaufmann]

It's time to let you know about some of the progress I've done over the past few months.
Although I do not agree to the term AI (behaviour is a way better term), let's stick to for simplicity.

At the current time I consider the basic game very playable. Obviously there still are flaws and things not working too well but at this time I do consider the rule based AI as quite mature and ahead of other AI's I've met playing similar games.

What is the AI able to do

• Starting rules. It will play blank aces first, then suits with aces having maximum 3 cards. Chances of winning the trick are definately there and this adds so much value since it's 30% of the game and around 40% of the points.
  • is able to detect thrown suites and won't play them, since chances it will get tricked are high
  • if teammate is known, will try to play suites your teammate hasn't
• Team detection. Announcements and queen of clubs will trigger affinity events which cause players to side in the future. My AI features additional affinity events such as tricking the queen of clubs and greasing the queen of clubs.
  • Adding other events such as detecting greasing in other rounds is very possible but imho rather sophisticated and something I don't want to implement right now, since I'm trying to build a reasonable AI and don't want to compete with humans.
• Greasing your teammate with high value cards like fox or ten of diamonds.
  • AI will grease with non trump aces too, trying to throw blank aces in order to have missing suites (chicane)
• Using memory. AI remembers all cards. It knows about the highest card left and if a trick can be won - or not.
• Positional play.
  • AI will grease if it's your teammates trick, or decide whether the trick is worth winning.
  • If you're on position 3 and your teammate following, AI will play fox in hope your teammate wins the trick, if highest card isn't really high
• Announcements, based on 'goodies'. Having blank aces, missing suites, both ten of hearts or the number of trumps may trigger an announcement.
  • I have decided against implementing expectation value since implementing it makes other AI moves necessary in order to acquire those points calculated.

Needless to say, many of these moves are very opinionated and represent my own, bold, gamestyle, but for starters I believe this AI works out really well. Disregarding the way I coded it, I believe it's very readable and therefore easy to adjust and expandable.

Whats missing or can be improved

This is definately an incomplete list

• This AI only works with the basic game, playings solo's isn't implemented right now
  • Although silent wedding is playable and implemented, chances AI will have a hard time is very likely
• Detailed team detection. Not greasing somebody who has clearly identified his team (announcement or queen of clubs)
• Players on turn 2 and 3 won't make good choices right now
• Strategies: You high, teammate low - vice <-> versa
• Special moves like playing ten of hearts after declaring party, making fox playable
  • obviously this would need a better team detection and counting foxes explicitly
• Other rulesets
  • ignores charly right now

Where are we heading

Right now I don't plan on adding much more complexity. As I already said, I believe this AI is very playable, though having it's flaws. I think this is a big success!
I might add a few special moves but I doubt I will spend the same amount of time on the AI much further - on the shortterm.
Next steps are implementing player personas, therefore I will probably keep touching the behaviour and changing the way it has been coded to a more mature and modular way, using some patterns. I'm thinking of some factory style player creation.
Obviously we need to implement solos at some point. This probably will be a major point of refactoring how the game interacts with the player, since we need to ask if you're healthy. Card order and static implementations need to be changed even before we change or add anything to the AI.

Long term thoughts

Although I was never really good at keeping up with long term projects, I am really looking forward doing small steps at a time on this one.
Im thinking of something like maiachess. TLDR: Deep learning AI based on ELO values of players.
So many things to implement at first, think #38 with ruleset etc. How to generate or acquire appropriate Data?! (Multiplayer was dropped). Simulating games might develop a decent AI, but my aim is to have multiple AI's based on human player ratings, think difficulty levels.
So exciting 🚀🚀🚀
For the sake of completeness, this is where every research about deep learning doppelkopf should start:
https://github.com/silvansievers/doko