Private IronFire	Artificial Intelligence	2/10/06 5:51 PM
(mainly addressed to matt, but others welcome to respond) From the help: "The Rozz project was adopted because the game’s synchronous play offers interesting challenges for an AI player in general, and eventually for a sentience engine specifically. The game of chess had been a springboard for early work in AI, but now that brute force has conquered even the Grandmasters among us, we have reached conclusive ends which hamper further discovery and progress in the means" "The game of Rozz presents a new frontier for the development of Artificial Intelligence, because strong play requires a human-like anticipation of moves. It’s true that computers have conquered chess. However, do you know what Go is? You should if you don’t, as it’s the most popular game in the world (obviously not in America though, sadly). Its considered the greatest strategy of all time (created thousands of years ago). Its different than chess in many ways. There are tons of possible moves available each turn (for example you have 361 possible first moves) giving it much more possible depth than chess. Anyway, my point is computers totally suck at Go. No one has been able to create a computer program that beat even a moderate Go player. That?s pretty amazing. Interestingly, studies have shown that players mainly use their right brain when playing chess, but mainly use their left brain when playing Go. That may be why Go is so hard for computers. Expert Go players say that choosing a move is more like a "feeling" or an "intuition" than a logical deduction. Pretty cool if you ask me? Anyway, I’ve done a bit of AI programming myself. I programmed a rock-paper-scissors game than could beat humans by analyzing patterns in their play and predicting the next move (and won 4th place at state science fair). While doing my project I researched AI quite a bit (though I’m by no means an expert). I’ve also done some in-depth studies into game theory. At its core, the Rozz AI will be a prediction machine. Predict what the enemy will do, then counter it (well, it should use a cost/benefit counter method based on percentile prediction methods, so its not actually countering just one move - I’ll explain later). There are two things Rozz AI must analyze about players: 1. what moves does a player "like" to do; 2. what prediction algorithms do they use to determine what move to do. The only way Rozz AI can predict the first thing is to analyze players past moves from past games (This is necessary for a totally awesome AI. All information available to a normal player should be available to sengin!) Rozz AI can predict the second thing two ways, either from past games or from the current game. Analyzing prediction algorithms is most important, so I’ll focus on that for now. If Rozz AI doesn’t adapt based on whom it’s playing, it will never be any good (IMO). If sengin is designed to defeat players who use 1st level based prediction algorithms, players who use 0 level prediction algorithms (no prediction, in a way) will easily defeat it. And vice-versa. Sengin must be able to change based on who its playing. It must be able to determine its opponents prediction algorithms based on the current game (and/or past games). But anyway, it getting late and I fear I’m probably not making much sense. What prediction scheme are you currently using for sengin (if its not confidential)? If I had some idea of where you currently are, maybe I could give some advice as where to go next. BTW, you should check out: http://sirlin.net/ and read the ?Play to Win? articles?those articles transformed my gaming. Also, you could read the articles under multiplayer gaming if you want, especially ?Yomi Layer 3,? that relates most to prediction based games. Oh, and does "Grandmaster among us" imply some admin are chess grandmasters? And also, you might like this site: http://www.cs.ualberta.ca/~darse/rsbpc.html (the results page has the nice stuff: http://www.cs.ualberta.ca/~darse/rsb-results1.html (and no, I didn?t enter in this)) Sorry if I?m rambling on incoherently, its complicated, and I get excited about this type of stuff!!! Last edited by RozzManager, 11/29/12 10:33 PM
	Private Matt 2/10/06 7:02 PM Great post, IronFire! I’ve been interested in AI for a while, and I can’t say it ever gets boring. The actual sengin mission project might fall under what’s now called a Biologically-Inspired Cognitive Architecture (BICA), so it would actually be a giant leap to go from success on that end to an application as part of a game engine ... but the hope is that it might play some role at some point. The mission project ends up on the back burner a lot though, as do "sengin environment" projects like Rozz, since we pay the bills through consulting. Currently, the "sengin" player is just a traditional brute-force engine: different weightings and some recursion, with a random stopping point so you can’t be sure if it’s single-guessing, or double-guessing, or triple-guessing itself. Rozz does have Rock-Paper-Scissors RoShamBo characteristics, but the number of possible command choices can get astronomical pretty quickly. The next sengin version will first off need to have a better pruning algorithm, since it’s only looking at a random subset of possible commands in the minute (or minute and a half) I give it to think -- notice that it plays much better with the reduced inventory in Basic Training, since it has time to consider a greater percentage of moves. Another thing I intend to add is a "VENGEANCE" weighting, since part of human’s defense lies in an anticipated retaliation. Adapting its moves based on who it’s playing (and spanning multiple games) is taking this a few steps further, but I’ve had some musings along those lines also. For instance, it may be to a sengin’s long-term advantage to have an all-out kamikaze reaction, even if it’s going to cost it the game at hand. Or, take Mike’s move in a recent game, where he nuked Greko in retaliation for an earlier game they had played. I’m familiar with Go and the limited success at a Go program. One counter-argument is that Go hasn’t had the AI programming attention that chess has had; but overall I agree with you that the game presents unique programming difficulties. It’s a great game, no doubt. By "Grandmasters among us" I was alluding to mankind; I love chess and the history of the great chess players of past and present, but (for me, at least) computers will eventually take the magic out of it. OK, so there’s some counter-rambling. Matt Last edited by RozzManager, 11/29/12 10:36 PM Private Matt 2/11/06 5:35 AM Oh, another thing to fix with the sengins (when that time comes) is their defensive reasoning, which is quite relevant to your discussion here. Too often, the sengins allow decisive invasions of their HQ; ultimately, it would seem the solution would require understanding of the opponents’ play history. Let me elaborate ... Right now a sengin will choose a set of commands according to the following weighted-randomization: (1) An "appropriation" decision, whereby it looks for favorable commands at a search depth, but disregarding other players’ reponses. Under appropriation, for example, the sengin might purchase a LRNUKE if it sees it can destroy targets on the next move. (2) A "determined" decision, where it just finds its most favorable move -- similar to appropriation at a depth of 1, but with less emphasis on purchases. (3) An "anticipating" decision, where it finds its most favorable move, after assuming the opponents’ most favorable moves. Anticipation can go to (randomized) depth, so it might find it’s most favorable move after assuming the opponents’ most favorable moves, where each in turn are based on an assumption of THEIR opponents’ most favorable moves, etc. I said that the choice between these decisions is weighted because the sengins have APPROPRIATION, DETERMINATION, and ANTICIPATION weightings that affect the likelihood of one choice over another. Now, a sengin might leave it’s HQ open if it’s determined, or if it’s anticipating that opponents’ moves into the HQ would be unfavorable (after all, the sengin could buy ARMOR, so it anticipates further and decides it doesn’t need to buy ARMOR). One step toward fixing this is to pass a "critical flag" of some sort through the anticipation recursion algorithm, so extra weight can be given to defense. What it really needs, though, is to assess the likelihood of a particular opponent moving in to it’s HQ. After all, a human opponent will assess the likelihood of a sengin (or other opponent) leaving his HQ defenseless, and have an advantage in that regard. Of course, it extends to other situations as well: will he leave that cluster of INF as grind for my ARMOR, or buy a tank trap? (To the sengin’s advantage, it can be random, not to mention running out of time when considering command sets.) BTW, one self-imposed limitation on the sengin AI is that it cannot base evaluations on any particular item. It has to be able to come into any scenario, even one with a completely different item catalog, and make moves. Matt Last edited by RozzManager, 11/29/12 10:38 PM Private IronFire 2/11/06 12:23 PM I understand the problems your talking about with regards to defense. A "cost/benefit counter method based on percentile prediction" might be an answer (albeit a complicated one) to this problem. To it in one statement it’s this: Choose the best move assuming your predictions are true OR false (percentile predictions) in addition to weighing the cost/benefit of a move. To illustrate percentile predictions, suppose we’re playing RPS (rock-paper-scissors). After watching you play, I see that you play rock 40% of the time, Paper 50% of the time, and scissors 10%. We start a new game of RPS and I consider what to play. At first, it might look like I should play scissors to counter your likely paper. If I didn’t have percentile predictions and simply said, "He will most likely do paper" then scissors would be best. Looking at the big picture though, if I do scissors I have a 50% chance of winning (prediction worked), 10% chance of tying, and 40% of loosing (prediction failed). If I choose paper, my odds are 40% win (prediction worked), 50% tie, and 10% lose (prediction failed). In summary, scissors has a 5-4 win ratio while paper has a 4-1 win ration. Clearly paper is the better choice. Such an analysis is not possible without both percentile predictions and considering the possibility of a false prediction. Now for the second part, things get more complicated. This time we are playing a modified version of RPS. If you win with rock you get 1 points, if you win with paper you get 2 points, and if you win with scissors you get 3 point. After analysis, I see you do rock 40% of the time, paper 50% of the time, and scissors 10% of the time. The win ratio:%.%.gs.%.%.%:#039;s are same as before: 1-5 rock, 4-1 paper, and 5-4 scissors. However, this time points won or lost (cost/benefit) must be taken into consideration. With rock you win 1 point or lose 2 point, giving you a weighted 1-10 win/lose ratio. With paper you win 2 point or lose 3 points, giving you a weighted 8-3 win/lose ratio. With scissors you win 3 points or lose 1 point, giving you a weighted 15-4 win/lose ratio. So this time scissors is the best choice. So first you analyze the opponents previous moves and come up with percentile predictions of what they will do. Then you weigh the predictions using the cost/benefit (predetermined values) of each possible move to give you the best overall move. Anywho, you can probably see how this could apply to sengin. I gtg, maybe I’ll elaborate later. IronFire Last edited by RozzManager, 11/29/12 10:40 PM Private Matt 2/13/06 6:30 AM Very interesting, IronFire. It would be cool if I could provide a base Sengin class for programmers without exposing the entire game engine, but I’m not sure how useful such an interface would be without being able to resolve plays. I’ll have to think about that. I’ll definitely add some support for percentages in the somewhat-near future (short-term and long-term storage by opponent) which would be needed for your "cost/benefit counter method based on percentile prediction" solution, as well as any similar solution. Even the support for percentages will be tricky, though: it’s hard for the sengin to know, just based on the move, the player’s motivation for making it. My thought is first to compare an "expected" score of the position after moving with the actual score of the position, to provide a base value for success/failure of the strategy just played. Then, by applying this value to the search depth chosen for each player, the sengin might at least recognize those cases where the depth was successful. Eventually, that could lead to percentages such as PlayerX single-thinks 20%, double-thinks 40%, and triple-thinks 40% of the time. Matt Last edited by RozzManager, 11/29/12 10:41 PM Private Matt 2/13/06 9:28 AM Another option (perhaps the better one) is to have the sengins evaluate game histories as a process separate from game playing. In this side effort, they could evaluate players moves to see what (if any) search depths they coincide with. I suppose that’s more along the lines of what you had in mind? Last edited by RozzManager, 11/29/12 10:42 PM Private IronFire 2/13/06 10:39 AM You got it