Ten minute game jam!

Congrats! It’s very cool to see a project through to completion… Regardless as to the originality. That’s a whole other issue!

I am not going to tell you what to do but If you wanted to break down your thoughts about the chess game into smaller pieces you could always try implementing a very simple game like tic-tac-toe. It has the same kind of game state as chess (in that there are two players that can be human or AI, and they alternate turns). However, the game itself is much simpler. So you could use that as a project to work out all those concepts and then take that framework and use it on a more complex game like chess. Just a thought!

Thanks for the advice on chess. I probably should have followed your advice on tic-tac-toe, lol, but I didn’t see it before I went ahead and plunged into chess. It’s actually going well. I didn’t have any trouble implementing turn-taking, but I’m ignoring the team-picking problem for now, so the player is always white. That problem is more acute in chess than tic-tac-toe, because the black king and queen are reversed. Maybe checkers presents the same issue? Maybe once I get the player’s side choice, I choose which of two board states to initialize?

Apart from that, I’ve made a surprising amount of progress: I have coded most of the movement rules (except castling and en passant), I can move and capture pieces, and I now have an AI that plays random moves. All that took me about a day. Today I’m going to start evaluating moves to make the AI a tad smarter. And I might try to implement side-picking.

I can see that memory management could be a huge issue here. That simple list of 20-odd possible moves (a ds_list in GMS parlance) will be replicated a thousand times over as the AI has to consider the dozens of responses to each possible move, and responses to those responses.

Hey, you got to live your dream… Keep going!

My limited understanding with chess programs is that since the opening moves are very well understood, most programs use a fixed series of moves for the opening and After those moves are all played out they then use AI later (maybe exhaustive search of some sort?) to determine move into the mid and end game.

I just googled it and I believe they’re called gambits. And I’m sure there are aggressive, moderate, and conservative ones. And of course different ones for each color!

So I believe the standard approach is to have the AI choose a gambit… Depending on lots of parameters like how advanced your opponent is and whether they’re playing white or black or whatever. Then the computer player would simply move down the gambit and make each move on his turn until all the moves have been made (or I guess until the board state gets too weird to keep pursuing the gambit). And then it would switch to a more generalized AI that would use… I don’t know maybe some sort of depth first move analysis tree? And that would be used from the mid game through the end. Or maybe near endgame there are standard moves… not sure.

Anyway, that technique would give you a leg up on How the AI would play though it’s still going to be a very complex undertaking.

You usually want to use some sort of minimax tree traversal with pruning. You’ll have to decide the depth of the search. That’s where the exponential complexity arises.

https://www.chessprogramming.org/Minimax

Are there good and open evaluation functions for a chess board? I think that would be key for something slightly competent.

I would think of it this way: the minimax tree traversal takes care of short term tactics (finding movement when you take a piece or the opponent does) but the evaluation function (how good a board state is) is actually what will drive the longer term strategy.

Like Charlatan says a table of patterns (board state and follow up move) for openings is probably standard practice and expected by good chess players who will likely be doing the same.

Maybe you should watch this documentary: https://www.youtube.com/watch?v=NuGT_L13bQ8

crowdsourced chess!!

I’m liking all the enthusiasm! @JoshL, I watched that trailer – looks really fun!

Yep, but this only gets you so far – maybe the first dozen moves or so, if that. If the human player deviates from the standard opening dance, then the computer has to “think” for itself. As for gambits, those are mostly varieties of openings; queen’s gambit declined, say, offers a pawn at the start, and the other player declines it. It’s true there are set endgame patterns one also learns as a player. When I was a kid my dad taught me queen-and-king and rook-and-king, the two easy ones. One also learns pawn/king finishes, and computers can too.

Yep, that’s exactly what I’m working on. Pruning is going to be very difficult. I’m going to have my hands full managing all the branches on an unpruned tree, heh.

At this stage my AI is now able to move its pawns, knights, and king. Randomly, heh.
It makes for some funny positions. The AI king actually respects the rules of check, to some extent, so it doesn’t take pieces that are guarded by other pieces. I’m working on ensuring it can’t move into check either. After that, I’ll do the rook (not too hard), the bishop (harder), and queen (not so bad once the bishop and rook are done). I hope to have that work done today so that I can start making the AI smarter tomorrow. I’m thinking I’ll try teaching it one opening, then dive into minmax.

I made Tic Tac Toe in Python (just in-terminal with keyboard prompts for controls, very 1976), which didn’t seem too hard, but checkers was a lot more complex and I didn’t get it 100% finished. Never tried chess, nor did I even attempt AI.

I’m currently pretty excited that I’ve finally managed to implement some kind of A-Star pathfinding on the fly in my retro CRPG NPCs. Now if only I had more than an hour a week to work on it…

It’s not chess, but I maintain an engine for the hnefatafl games, which I’ve had a fascination with for some time. Pruning and depth of search are the most important factors in a classical board game AI, in my experience.

I cribbed heavily from a series of blog posts about a chess engine written in Java as a learning exercise, but I’m having a hard time finding it now.

I wrote a checkers game a couple decades ago and didn’t finish it either. Chess is more fun!

Wow, that is extremely cool! I’ve never played that family of games, but they look fun – and plenty complicated to code.

Incidentally, I like that Game Maker Studio 2 provides easy integration with Git and Github. It’s nice having web-based backup even for a solo project.

For now my chess game still qualifies as a “10 minute” game, as my AI is still rudimentary, and I can beat it in about 2 minutes. But it’s getting better! I’ve taught it one variation of the Sicilian Defense, and I’ll teach it more today. More importantly, today I start in earnest the “minmax” AI – the “thinking” the game does when it’s not following a scripted opening. I’m having lots of fun with this.

I look forward to the day when I can purchase it on Steam!

lol, don’t open your wallet just yet. :)

I’'m making progress. The AI now takes the most valuable piece it can, which is not great chess but an improvement over a pure random AI. Now I’m implementing piece-square boards for all the pieces – weighted scores for each spot on the board to encourage the AI to avoid the sides and corners in the early and mid-game. After that, I’ll implement the second level of search – the algorithm seeking to minimize the human’s response to the AI’s proposed move.

So right now I’m thinking minimax, rather than Negamax, which puts a negative sign in front of the “minimize” score assigned to the human’s response, so that one is always dealing with the same score-scale. I may try to implement Negamax if it doesn’t confuse me too much. Either way, I will eventually alpha-beta pruning (an algorithm to bypass tree branches that are definitely suboptimal).

I don’t plan to use the Monte Carlo tree search (MCTS), which has the AI play out thousands of games to conclusion using random moves! It then adds up which games are winners and which are losers, then choose a move based on that data. That sounds awesome, especially since my AI is already exceptionally good at random moves. :) But even experts have trouble applying MCTS to chess; it’s something I’d like to experiment with in a different game.

If anyone has thoughts on all this, I’m all ears.

Piece-square tables make a big difference to an AI’s sense of position and control there…over.

In terms of innovations over pure minimax that made my tafl AI better, they go in about this order:

  1. Alpha-beta pruning. You search orders of magnitude fewer nodes for a given depth. Note, however, that the efficiency of A/B pruning depends on the applicability of your evaluation function. The more your evaluation function diverges from the ideal, the more likely you are to prune branches that are actually promising.
  2. Zobrist tables. My evaluation function is relatively heavyweight, though, so there are large savings in analyzing positions only once.
  3. Killer move tables, and move ordering generally. Searching the most promising moves first yields earlier alpha-beta cutoffs, which increases your effective search depth.
  4. (Dishonorable mention.) The history heuristic (‘this move was good in the past’) actually made my AI play worse, because of the added overhead.

MCTS gets harder the more open your game is. Go fits it well, because every game ends after a few hundred moves, tops. It’s much less clear how to make your ‘random’ playouts approach the end of the game in chess. (Tafl may be a middle ground there. I’ve been doing some work on a Monte Carlo AI, but haven’t gotten anywhere close to finishing.)

Hey, thanks for that very helpful reply. I had not heard of Zobrist tables, so I’m glad I know of them now. I am vaguely familiar with killer-move tables; I’ll learn more about them.

I’ve now implemented most of my piece-square tables, and the AI is notably smarter – but still rudimentary. I’m almost ready to start implementing minimax.

So I’ve implemented one level of minmax – meaning the AI will now look ahead one whole move, lol. Still, that small change has made a drastic improvement in its intelligence. If I let it play a scripted opening (e.g., Sicilian defense), it gives me a pretty good game until the late midgame. Occasionally it pulls ahead of me in material, as it never makes boneheaded errors, and if I’m tired or lazy I do. But inevitably I get the win, because I haven’t taught it enough about endgames or checkmate.

For now, my plan is to deepen its search pattern to four or five moves ahead, if processing speed permits it. Then I’ll expand on scripted openings for both sides. Then maybe some work on endgame scripts, depending on how much patience I have. At that point I’ll probably declare victory and move on. Already I’m getting depressed at the thought that my own creation may soon be better at chess than I am…

Sounds like some good progress. And I’m curious… Is the AI working in a separate thread? Just curious.

Having you talk about the AI reminded me of back in the day when the Atari 800 computer was just released (fall 1980). There was a wargame called Eastern Front that had been released. I think it was done by Chris Crawford who was a big Atari dev back then, and a smart guy to boot. Back then of course, you would be used to alternating turns with the AI and having the AI take some time to determine its move. So you would move, then the AI would think and then move and so forth. So there would be a little delay during the computers turn while it figured out what it should do.

However, Eastern Front was not like this. When you hit End Turn the AI moved instantly… there was no delay at all. At some point I read an article describing how he accomplished this. The way Crawford implemented the search was to hook a callback routine into the vertical blank interrupt of the TV refresh, so that every time the CRT gun finished drawing a frame, while it was traveling back to the top of the screen to draw the next frame (30 times a second), the AI would do a teeny bit of work planning it’s moves. And whenever the player ended their turn, the AI went with whatever its current best move was. So I assume the longer you sat there on your turn, the longer the AI had to plan its move. It struck me as an ingenious way to Implement the AI.

So when are you going to start working on 3D Chess, Spock?
image

Of course! Right now I’m stuck with irrational human opponents. Although Captain Kirk’s illogical approach to chess does have its advantages.

That does sound ingenious. I played one of Crawford’s games back in the day – a Battle of the Bulge Game, I think. I enjoyed it a lot, and I remember being embarrassed when I made a silly criticism (about replayability) on a forum somewhere and he responded personally!

I have no idea how to implement thinking while the AI is thinking, or using a separate thread, or any such. I sure could use it! Processing time is now my #1 issue.

I have the minmax algorithm working smoothly: it sees ahead 2-plus moves and now plays as well as me through much ot the midgame. (Only the endgame salvages my pride, and if I have the patience, I’ll give it some endgame scripts to fix that.) It sometimes gets me on the ropes, in fact, but then it lets me off the hook. E.g., just now it seemed to have won my bishop, but it insisted on attacking my queen instead of just taking the prize, and I eventually wriggled away.

Anyway, with even just two moves ahead, it takes 10-30 seconds a move in the early and midgame. It does get quicker in the endgame. And I have not yet implemented alpha-beta pruning, which can drastically cut down on time spent evaluating useless moves. (I want to make sure my minmax is solid first.) Also, I am still churning out a ridiculous number of debug messages to myself, which may be slowing things down. And I have not yet tried compiling an executable that runs directly on Windows, rather than on the Game Maker Virtual Machine. So, lots of stuff to try.

For a while I also had a memory leak, but I think I’ve fixed that now, though I’m still testing. Game Maker Studiio lets you create flexible “list” data structures, which I use to populate my move lists, but you have to be careful to clean them up when done. I’m still not sure I’m doing that optimally.

This is a very fun project, but I’m starting to wonder how far I want to go with it. Do the lessons I’m learning here (minmax, pruning) have any bearing on AI for more complex board states, as in 4X games, wargames, or card games like Hearthstone, say?