Design challenge: An AI for CEO
I have some crowns and I wanted to make a bounty that was easy/fun to think about, but potentially very hard to do well, here it is.
How would you design a chess engine that works well on a game with as many possibilities chess evolved online? As I see it there are 2 ways to approach this: first, you can manually determine the value of attack squares and build in a lot of heuristics. If you want to go this approach, perhaps describe how you would make heuristics for a nonempty subset of all the possible moves, and explain how you can design the system such that it wouldn't become a massive, unmaintainable mess of code. Second, you can try doing some possibility search or even machine learning to automatically adjust to new possibilities. Make sure that your algorithm is reasonably fast, and explain how you will get and use training data if applicable. Of course, you may try some combination of these ideas or something completely different if you are big brained.
I have something like 90 rp to go to people with answers I like. If you don't know anything about coding/algorithm design, and still comment with a decent effort, you get 10rp guaranteed (say you haven't coded before in your post).
I have no coding experience but I imagine that it would be near impossible to design a "good" engine for CEO without super-intelligent machine learning, on the basis that every army faced is going to be massively different. Engines for things like go and chess have the benefit of a pre-defined starting position of each and every game, as well as only having to assess a select few pieces. With CEO, however, I guess you would have to find a way for it to be able to evaluate the opposing army on its own as well as its strengths and weaknesses in relation to the pieces it is using... which would be a lot in and of itself, and the game hasn't even started yet lol
If you could find a way to do that, though, then I think that the best approach would be letting it figure out which pieces it likes the best on its own. Once it was able to determine that, it would hopefully have assessed the entire base of pieces well enough in order to be able to start playing itself to learn. I do not believe it to be possible for us as humans to assign number values to every move and ability-set within the game and how they correlate with eachother, so allowing the engine to figure this out for itself is almost assuredly going to be best. Letting it learn most tactical, strategic and positional ideas also would probably be the best way of going about it as well. I could not theoretically see a human being able to list each and every tactical motif and pattern possible and allow it to learn from these in this game like has happened with chess, as the rules of this game are much more complicated, as well as the piece potential.
Some things you probably could program it to be aware of, however, (and this is probably just obvious to a programmer, but alas I will say it anyway) are the basic rules, (uses of morale, morale drain past move 50, promotion, etc.) the basic chess tactics (skewers, pins, double attacks, overloaded pieces, discovered attacks, zwischenzug, zugzwang, interferece, etc.) the value of the center, the base value of pieces as well as their potential opening, middlegame, and endgame value, potential positional value, (eg; a Crusader+ in the e4, d4, e5, d5 squares is going to have the same board presence and effective range as a Rook but with additional benefits) counter-piece value, (eg; Antimage versus a lot of ranged and magic champions) importance of king safety, the value of minions being able to move backward, as well as synergies between pieces and just what does and doesn't work well together. There's probably a whole host of other things that could go here that I am not thinking of at the moment, too.
Once all that was done I guess it would need to play against itself many thousands of times against and with many different armies and strategies and develop a solid understanding of how everything works before it was able to effectively be of use to any human in assessing a position. Even after all of this, though, I still feel like it would have a terribly difficult time of accurately assessing the starting positions of every game because of the sheer immensity of calculation that this would require. I think for the time being, human intuition will always be better at this than a computer can ever hope to be only because time is a pretty big factor in this game. Give a supercomputer an hour to play its first move and sure, it will do better than human intuition but 5 minutes just isn't enough. As far as middlegame and endgames go, it would probably be substantially better than a human in assessment as tactics would be able to dominate the game and stalling techniques could be employed once ahead on morale.
Umm yeah that's about all I've got. Pretty fun stuff to think about! This post has inspired me to gather and sort my own collection of every piece in the game based on cost so I am able assess them better and gain a better understanding of the game myself. So thanks for that!
Thanks for the response, glad to hear this opinion! (+39 rp) Basically you seem to be suggesting to have a lot of heuristics to check between situations, then using some machine learning on top of it, which seems like it could be a pretty good strategy, though 'using some machine learning' is vague enough that it's a bit unclear. I think that if you can get a decent way to measure how good a position is with basic chess tactics, then you can just do a simpler search with alpha-beta pruning (just checking say 3 moves deep and seeing which one results in the best outcome according to your metric on how good a position is, if both players use that metric). Though, even if you give a supercomputer an hour to compute vs a minute, in my opinion it won't have that much benefit, 60x more operations isn't too much when a minute already allows for 10^10 operations or so... of course it can help but the base algorithm is much more important.
Sorry I couldn't be of more help but I am quite technologically illiterate lol I just know that using engines in standard chess usually requires a substantial amount of time for them to work things out deeply in complicated positions, and I figured that any individual game of CEO would be exponentially more complicated than even some of the most complicated chess games.
Much appreciated for the RP! I'd be happy to help test any future engines and give my 2 cents if you don't mind hearing my layman's opinion again. More than happy, I would be honoured :D
I have only very basic coding experience, but I think the best way to design an AI for CEO would be to create an index of different types of attacks/moves, and then a separate index of all of the units. Since it would only need images of what attacks/moves each unit has and only a brief understanding of what each move does this wouldn't take up too many lines of code even considering how many units/moves we do have. I would then also use some kind of capturing software that would allow the AI to look at the whole screen each turn by taking a picture of the board (This is assuming that you're not talking about the AI that already exists, and ofc the image would be deleted later to save space). After taking a picture of the board I would have it scan all the units quickly, preferably it would send them to 3 or 4 different computers where each one would be in charge of scanning one section of the board, then they'd all reply back telling the AI which moves are possible by the enemy and the AI. This amount would probably not take that much coding as it is already done on a slightly smaller scale for many other games including other chess variants.
Next for deciding its move I'd preferably want it to run a short simulation where it makes a move and then it decides what move it thinks the opponent is going to make and looks to see if it is in a better position then it was before and if not runs a separate simulation for other moves. I would understand if this isn't feasible though as it would require quite a bit of computing power to do quickly.
As far as giving the AI a base to work with it depends on if you want the AI to learn or not. If you don't want the AI to learn just tell it to make sure it doesn't run out of morale and upload a collection of strategies to it. If you do want it to learn tell it to not run out of Morale and give it a good chunk for memory. It should use that memory to store the past 5 defeats and a bar graph showing how many times it has won and lost to each army. There are two ways it can learn from here:
I don't know if what I said was already said, I didn't read the other response so if it's just a rephrasing of what Kristiansen said then I'm sorry it wasn't intentional.
This post has received a 33.97 % upvote from @boomerang.