Most efficient way to make scrabble AI?

Help Programming
1

Godot 4.3

I’m using TileMapLayers to form a board for a scrabble-like game. The AI can already determine what valid words it can form, but I’m trying to figure out the best way for the AI to use those valid words to search the board for a place that they can be played (i.e. adjacent to an already played word). I was thinking about having the AI scan every space on the board, then check if the word fits, then check adjacent tiles to the planned placement to see if any are occupied by already played tiles, but I would like to find a more efficient solution so that the AI doesn’t have to look at every possible word placement. Any suggestions would be greatly appreciated!

2

Does your solution cause performance issues?

3

First, take @nutlike4693 's advice. If your solution works “good enough” then your solution is the best solution. You’re making a Scrabble game, not a research project. …Or, are you? If so, I have no advice on Scrabble AI.

I do, however, have advice on optimizing long-running AI processes for video games.

I’m making a Sudoku game as a project to really “dive into” Godot and encountered this issue. For creating Sudoku puzzles on the fly, it took about 0.3 seconds of C++ on my Android (dev mode, though.)

If you’re using a brute-force method like that and utilizing backtracking, your best bet isn’t going to be optimizing it any further. Instead, background the task. Use a thread. If your code is optimized enough, you can then add some Game Design Magic to hide the fact that there’s a wait. For instance, if it would normally freeze your game by about a tenth of a second, try this:

  1. Player makes the choice.
  2. Start the thread to decide the next move.
  3. Play an animation of the player’s tile being placed down, that is designed to take only a little longer than the expected delay.
  4. If the thread hasn’t finished, don’t update the screen for a bit. To handle the worst case, you may even need to add a “Thinking…” spinning logo. Hopefully not.
  5. Get the result of the thread and apply it. Keep the thread around, stopped, for next time.
1 Like
4

It doesn’t cause performance issues. But since I’m an amateur coder, sometimes there are much better ways of doing things that I’m not aware of :slight_smile: I’ll just go with my initial plan. Thanks~

5

You may already know this, but when you get to performance issues, use tools like the profiler to find where the actual issue is.

6

Popular board games are also popular programmer targets; ie this has been done more than once.
It is helpful to see how others have done it.
Here is one persons summary of how he did it.
For sure there are others.

1 Like