Heuristics take time.

You could also blank the display and periodically change the background color while it is calculating. I'll bet you could speed up the calculation by close to an order of magnitude if you do this, since you could run everything in a tight loop without any need to render a screen.

Or just write a mini-kernel that has maybe 10 lines that say "Thinking" and have a progress bar beside it made out of playfield pixels. Wouldn't be quite as fast, but you could blank the screen right after 10 scanlines and resume calculations. Should still give a good increase in speed, at least 4-5x.

batari, on Sun Dec 11, 2005 6:16 PM, said:

Depending upon the nature of your 'thinking' loops, the mini-kernel idea may be a good one. Within your loop, just have:

  bit INTIM
  bmi .1
  sta somewhere; If needed
  jsr KERNEL_V
  lda somewhere; if sta'ed
.1

My kernels usually preserve X and Y but not the accumulator or status register. They wait for INTIM to reach some value (typically around 124) and then do the necessary kernel stuff. The smaller you make the target value, the more time you can have between kernel checks, but the more time will be wasted in the kernel itself.

batari, on Sun Dec 11, 2005 6:16 PM, said:

If your program knows its progress state, and you don't want to have any sort of kernel while it's thinking, I'd suggest doing something like the Supercharger "barn door" effect. It's quick and easy, and will give a nice progress indication, at least on older television sets (newer ones, unfortunately, may blank the screen if they don't get VSync).

Thanks for the suggestions. I do plan to show something besides a blank screen while the computer is planning a move, unless I can reduce the thinking time to very short. I want to hone the AI before focusing on cosmetic concerns.

John, I think I'll be able to calculate the heuristic more efficiently if I use the technique we discussed in PM's. I can reserve a byte for each possible four-in-a-row and keep track of how many pieces are there. It will take a while to overhaul things, but I'll keep you all posted.

This is a little off-topic...but, in case you missed it, I thought I'd mention that the 2600 High Score Club game this week is Othello. Speaking of games that frequently lose sync to think...

The lengthy delay in this version makes the game nearly unplayable for me. Personally, I found the previous version to be quite difficult already I wonder if you would not be better just introducing some randomness into the system when there is no obvious move, rather than implementing detailed heuristics? As you probably know, random techniques often outperform detailed rules in such systems.

Chris

cd-w, on Wed Dec 14, 2005 5:27 PM, said:

Both Connect-4 and Othello are somewhat difficult games to write good heuristics for, because the key to effective strategy lies not in the number of pieces you have or their position, but rather with moves that become available as a result of other moves. It is common on Connect-4 for a situation to arise in which the next person to play in a column will lose. The game from that point revolves around exhausting the supply of other moves in such a fashion that the opponent is the one who has to make the losing play. I would suggest finding and reading articles about the game; they'll probably provide some insight.

Heuristics can count for a lot, but multi-ply analysis is important as well. I have won quite handily at Othello at a game I should have lost, because the computer made a bad play 11 moves from the end. Multi-play analysis would have caught that (indeed, the bad play was the computer's last, since I made all 10 remaining moves without leaving the computer any other entry).

supercat, on Wed Dec 14, 2005 6:37 PM, said:

Yeah, Four-Play AI is more difficult than I anticipated. I thought it would be simple to do a search because there are only 7 moves. But as John points out long term strategy is important. After playing a while, I learned that a game between two experienced players usually finishes in the last open column, but the winning position is started early in the game. The current heuristic tries to anticipate these positions.

Quote

I will continue to use multi-ply analysis. That is primarily why the AI takes so long now, because the heuristic measures multiple positions at the leaves of the search tree.

Quote

I have found an excellent paper on 7x6 Connect Four, and it is not hard to adapt to 7x7 Four-Play. I've begun to appreciate subtle differences between an odd and even number of rows. The current heuristic uses basic ideas from that paper, but it looks like I'll have to get deeper into it.

cd-w, on Wed Dec 14, 2005 5:27 PM, said:

Interesting. This is news to me. Can you elaborate?