GNOME Bugzilla – Bug 152722
"Level One" is strong enough to force a player into a draw.
Last modified: 2014-06-18 18:22:54 UTC
Four-in-a-row is a solved game, in that it is possible for a player to force a win by starting the first move of the game in the middle column. In my opinion, play against AI "Level One" could easily be labeled "Difficult". I think "Level three" means that the velena engine will run perfect play. While it is significantly stronger than the other levels, it is possible to set up a L1 vs L3 game, let L1 make the first move, then watch L1 force L3 into a draw. I think this happens only about 10% of the the time, and about another 20% other games are won when only one or two spots are left unfilled.... However, I think this is an indication that AI for L1 and L2 needs to be dumbed down a bit. (Perhaps L1 should be forced to start on any column except for the middle three... however, this may break the ability to use the opining book, I'm not sure.)
I think everyone has a great deal of difficulty against level one, although most who comment on it assume that they just aren't very good. I'll look into it.
*** Bug 451540 has been marked as a duplicate of this bug. ***
I agree, level one is almost impossible to beat. Four-in-a-row should be a game that the kids can play (and win). Also, sometimes adult users, too, just want to kill 2 minutes while a web page loads, etc., they don't really want to invest serious thought and strategy into a quick game of four in a row. A simple solution would be to just make the level one AI moves completely random, (so very young children can play it, and for adults who just want to make patterns with the pretty marbles) keep level 3 where it's at and make level 2 what 1 is at now (or in my opinion even a lot easier).
This has been fixed for a while now. or at least, I can beat level 1, and I used to not be able to.
Bryan, are you sure you didn't develop mad connect four skills? I've never even come close to winning on Easy.
Created attachment 268121 [details] [review] Reduce the depth of the AI search Instead of searching to depth 4, let's do 1/2/3 on easy/normal/hard, respectively. This is completely insufficient; we'll need much more drastic steps as well.
Michael, Apparently I had a moment of really good connect 4 skills. Playing again, I've won one out of about 7 attempts on easy... clearly not easy enough...
*** Bug 722879 has been marked as a duplicate of this bug. ***
Review of attachment 268121 [details] [review]: The AI is being rewritten as a GSoC project.
Created attachment 278094 [details] [review] Patch for a new AI PFA a patch of a new easier AI that scales appropriately with the difficult levels. This patch is part of my GSoC project for 2014. Thanks.
Review of attachment 278094 [details] [review]: So, first of all: for me, obviousness is really important. Either we do something in an obvious fashion or we comment on what we do. We don't write nice code for the compiler. It doesn't care. We write nice code for other people to read. ::: src/ai.vala @@ +1,1 @@ +/*Here NEG_INF is supposed to be the lowest possible int value. int.MIN In this file are more than 30 whitespace errors. Please fix them. There are scripts that can do it or if you use git gui for yor commits, you see them marked in red. @@ +3,3 @@ +It is returned when AI wins. -1*MAX_HEURIST_VALUE is returned when Human wins +MAX_HEURIST_VALUE < NEG_INF/plies*/ +//FIXME int.MIN gives error FIXME @@ +11,3 @@ +enum Difficulty {EASY, MEDIUM, HARD;} + +int playgame (string fixme) This parameter should have a nicer name. @@ +21,3 @@ + /* to mantain the status of the board, to be used by the heuristic function, the top left cell is 0,0 */ + private Player[,] board = new Player [BOARD_ROWS, BOARD_COLUMNS]; + /* plies determine how deep would the tree be */ Nothing is determined here. It is set. So the comment should read "plies - depth of decision tree" or something like that. Same in the following comments. A method can determine something. A value can not. @@ +23,3 @@ + /* plies determine how deep would the tree be */ + private int plies = 8; + /* determines who made the last move, AI = 1 , human = -1 */ This is no longer an int, so the numbers do not correspond and also are of no interest. @@ +24,3 @@ + private int plies = 8; + /* determines who made the last move, AI = 1 , human = -1 */ + private Player last_move = Player.NONE; could be renamed to last_moving_player to make it clearer. Rename the other variables of the same type similarily. @@ +128,3 @@ + /* returns MAX_HEURIST_VALUE if AI has won as a result of the last move made, NEG_INF if HUMAN has won, 0 if no one has won the game yet + The argument i is the column in which the last move was made. */ + private int is_victor (int i) Please rename is_victor to something that does not imply a boolean. @@ +133,3 @@ + /* board[cell,i] would now be the cell on which the last move was made */ +/* for (cell = BOARD_ROWS - 1; cell >= 0 && board[cell,i] != 0; cell -= 1); + cell = cell + 1;*/ This code is commented out. Does it need to be removed? @@ +312,3 @@ + + /* check for immediate win of AI/HUMAN */ + private int immediate_win (Player p) Why is that int? Shouldn't that be bool? We never care about other cases that -1, do we? @@ +342,3 @@ + } + + public int playgame (string vstr) Please document what specific return values mean. @@ +358,3 @@ + return temp + 1; + + negamax(plies, NEG_INF, -1 * NEG_INF); -1 * NEG_INF is the reason why int.min throws the error. Every int can have an even number of states. Because 0 is included on the positive side, the positive side only goes up to -1 * NEG_INF - 1. But you also can't just do that because the expression -1 * NEG_INF always leads to overflow. You might want to set negative infinity to int.max*(-1) at the head and see how that goes. @@ +435,3 @@ + } + + private bool all_adjacent_empty (int i, int j) Please add some whitespaces in this method between the operators. It may also be nicer to have a nested loop from from x = -1 to 1 and y = -1 to 1 leaving out x=y=0. Then you have the out-of-bounds-check in one line and it should be clean and clear. @@ +495,3 @@ + return temp + 1; + + negamax(plies, NEG_INF, -1 * NEG_INF); I wrote about that one above. ::: src/main.c @@ +374,3 @@ { g_random_set_seed ((guint) time (NULL)); +// vboard = veleng_init (); Why is this a comment? Does this need to be removed? @@ +433,3 @@ game_free (void) { +// veleng_free (vboard); Why is this a comment? Does this need to be removed? ::: src/test-ai.vala @@ +19,3 @@ + * along with Four-in-a-row. If not, see <http://www.gnu.org/licenses/>. + */ + Please add a comment here, what specifically you are testing. It is not at all obvious what the returning numbers mean and what exactly you're testing. @@ +23,3 @@ +{ + assert (playgame ("a1727370") == 4); + assert (playgame ("a7315651311324420") == 6); Whitespace error @@ +68,3 @@ + assert (playgame ("a1445662644751711370") == 7); + assert (playgame ("a43442235372115113340") == 4); + assert (playgame ("a4143525567766443543125411170") == 7); If we do "avoid", shouldn't we be testing that a specific move is *not* taken? @@ +69,3 @@ + assert (playgame ("a43442235372115113340") == 4); + assert (playgame ("a4143525567766443543125411170") == 7); + Whitespace error @@ +78,3 @@ + assert (playgame ("a4141311525513520") == 2); + assert (playgame ("a1445662644751711377553330") == 3); + Whitespace error @@ +107,3 @@ + x = playgame ("a24357315461711177416622623350"); + assert (x >= 1 && x <= 7); + Whitespace error @@ +116,3 @@ + int easy = 0; + int draw = 0; + int hard = 0; please rename to easier_wins and harder_wins. @@ +118,3 @@ + int hard = 0; + + for (int i = 0; i< 5;i++) Please extract the 5 into a constant and use less or equal this constant divided by two. So if we want to increase the number of played games, we do it at a single point. @@ +126,3 @@ + m.append(harder); + + int count = 0; is there a reason you count the moves? @@ +174,3 @@ + int easy_wins = test_ai_vs_ai ("a0","b0"); + + assert (easy_wins < 3); See above. < 3 replace by <= the constant divided by two.
This is a lot right now. Please fix these issues and anything like that you come across and then I am going to look at the other stuff. I don't like how all these numbers are handled. Either it needs many more comments what specifically those numbers mean or we have to think of something simpler. Yeah, adding more comments on the meaning of the values could be nice.
Created attachment 278158 [details] [review] Amended after making changes I've tried to implement all the fixes suggested by you. I hope I haven't missed any. I have heavily commented the files which should hopefully make it easier to understand.
Review of attachment 278158 [details] [review]: There's a saying in Germany: not nice but rare. It's not very elegant but I think it will mostly do. There are some minor issues remaining. I am not sure this is correct but it looks like, whenever you call playgame from the game, we subtract 1. While we add one from the return of the ai. Can't we simply have the ai's return-values zero-based and ommit the -1 in the main file or are there issues preventing this?
I wanted to avoid making any changes to main.c until and unless I was changing the complete file. If main.c initially expected the AI to return one-based indexing, I had AI return in one-based indexing. So, if anyone looked at main.c before the new AI and after the new AI, he should find little difference.
Alright, thats fine.
Somehow that didn't get saved but you made whitespace changes in files you actually didn't touch. Please remove them from your commit and resubmit.
Created attachment 278258 [details] [review] Removed the files I did not edit from the commit Hopefully, this commit should be fine. For some reason it wasn't including file configure.ac. It's there after a few tweaks.
Review of attachment 278258 [details] [review]: After a bit of playtesting I think we take that as it is. Distcheck also works fine. I think the hard AI takes quite a bit of time thogh. Much longer than the last one. I was waiting about 4 seconds for a move. During that I stumbled over https://bugzilla.gnome.org/show_bug.cgi?id=731529 Hasn't that been an issue for you? Maybe you can take a look. In the meantime,
> I think the hard AI takes quite a bit of time thogh. Much longer than the last > one. I was waiting about 4 seconds for a move. Ok, agreed, 4 seconds is a lot. It did not seem to take so much on my machine though. And the longest time it took, it took only for a couple of moves. The other moves happened in less than a second. Was the 4 second wait occurring too often for you? I suggested we could try some methods (move ordering maybe) but Michael suggested if the AI was too fast, we'd have to separately add time delay so that the human is not overwhelmed by AI's speed. One quick way to bring down the time, if necessary, is to reduce plies of Normal and Hard from 8 to 7. That should make it faster, though it will also bring down the difficulty of the levels.
(In reply to comment #20) > I suggested we could try some methods (move ordering maybe) but Michael > suggested if the AI was too fast, we'd have to separately add time delay so > that the human is not overwhelmed by AI's speed. Hm, if the AI plays after less than a second, that is too fast, but four seconds is too long. (In reply to comment #20) > One quick way to bring down the time, if necessary, is to reduce plies of > Normal and Hard from 8 to 7. That should make it faster, though it will also > bring down the difficulty of the levels. Yes, let's change this. That should be twice as fast.
Created attachment 278702 [details] [review] Faster AI Reduced the number of plies from 8 to 7. I wasn't sure if a new bug needs to be created for this or was the patch to be submitted to this bug itself.
Here is good. It'd be better if these were constants, but as they're not, this is the correct minimal patch. Thanks! I think that was the last remaining issue, so time to close this bug.