# Tag Info

9

Assuming it is a turn-based game and, for each turn, there's an optimal choice that will lead to the winning state (zero-sum), you can basically simplify the question to "What is the optimal sequences of moves for me to win, considering the current situation that is presented on the board?". So you will need to perform your algorithm every turn as the ...

5

Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory performance, but there is a plethora of extensions/enhancements available. I don't have experience with the specific game you mentioned (Connect6), but from a quick look ...

4

The primary issue I see is that in the loop through time steps t in every training episode, you select actions for both players (who should have opposing goals to each other), but update a single q_table (which can only ever be correct for the "perspective" of one of your two players) on both of those actions, and updating both of them using a ...

3

Catan is actually a much more complicated game than the simple rules would suggest, and an exact solution is probably beyond the scope of current AI techniques. Monte Carlo Tree Search or Expectiminimax techniques seem like they could help, but are intended for games of perfect information. Catan is not a game of perfect information (the development cards ...

3

Using your app, I was able to find a (spoiler alert!) solution manually. At least now you know your puzzle is solvable and you did not waste your money :) It seems your app has a bug, though. I was unable to put the last piece, as shown in the picture. I was wondering if your solver, as it stands, will ever find a solution. Now the idea. It may be useful ...

3

First thing you're going to want to add is probably a Transposition Table, as also suggested by SmallChess. Afterwards, I'd look into Aspiration Search and/or Principal Variation Search (also see this page). Then I'd look into things like the Killer Move Heuristic, and maybe also see if you can simply implement existing parts of your engine more ...

2

The The Oxford Companion to Chess has entries on only 700 named openings, and lists another 1327 opening variations in the index, and I wouldn't be surprised if someone out there had them all memorized. For an algorithm, however, storing that number of openings is trivial, and Chess algorithms traditionally made use of high-quality "game books" which are ...

2

If you can remember everything and there's no randomisation in your outcome like chess, there is absolutely no reason not to do that. Anybody who can remember all the possible board configurations in chess, by definition plays perfect chess. A perfect player would never lose. Unfortunately, most practical problems can't be solved by brute-force, and that ...

2

You can take a look at this paper that solving your problem with a neural network. You can use the pytorch implementation of the satnet layer : satnet layer API. In this supervised setup the layer also learn the boolean constraints of your model. You can find an example of a sodoku solver in the github repo.

2

I think it is the wrong way to frame sudoku as a regression problem in neural networks. Firstly, you have to understand what regression is. "Regression" is when you predict a value given certain parameters, where the parameters are related to the value you have to predict. This happens because at the core neural networks are "function approximators", they ...

2

It's possible for an AI to learn chess without even knowing how to move the pieces. Google's AlphaZero didn't do that as their programmers coded the chess rules, but it's possible. One can learn the rules from human played chess games. Once the rules are known, we could use reinforcement learning to improve playing strength (and other board games).

2

The $Q$-learning rule that you have implemented updates $Q(S_t, A_t)$ estimates as follows, after executing an action $A_t$ in a state $S_t$, observing a reward $R_t$, and reaching a state $S_{t+1}$ as a result: $$Q(S_t, A_t) \gets (1 - \alpha) Q(S_t, A_t) + \alpha (R_t + \gamma \max_a Q(S_{t+1}, a))$$ The implementation seems to be correct for the ...

2

Nice question! I think there are a couple of issues at work here. Is the historical weakness of GOFAI in relation to non-trivial combinatorial games partly a function of the structure of the games studied, where game states and token values cannot be precisely quantified? I think the short answer is yes. The real issue is in the last part: ...

2

There is actually a github project about 'solving' Nim that implements certain type of Q-learning reinforcement algorithm (described in undergraduate thesis of Erik Jarleberg (Royal Institute of Technology) entitled "Reinforcement learning on the combinatorial game of Nim") that supposedly finds that optimal strategy lying down there inside in the game that ...

2

Historically, the non-ML approach would be an expert system. This is typically a rules-based decision system, falling under the umbrella of symbolic AI. These systems can have strong utility in limited contexts, but are generally "brittle" in that parameters not previously defined or accounted will produce no-compute or weak utility. Because the rules of ...

1

I would say a good way to make a good agent would be making it play against itself. As you go through several episodes, with a good exploration and exploitation balance, both will gradually learn and converge to Q*(s,a).´ So will this hold true if the same RL algo, with its learned values are used to play some other lesser perfect players? As long as ...

1

Chapter 1 of Sutton & Barto, doesn't introduce the full version Q learning, and you are probably not expected to explain the full distribution of values at that stage. Probably what you are expected to notice is that the maximum Q values out of possible next states - after training/convergence - should represent the agent's best choice of move. What the ...

1

If you have the best combination of distance between the stones, you should choose the best move to win. In this case, you have to be close to where your opponent plays. It is best to do this by surrounding your opponent's stones. You should always put the first stone in middle or corner of the table.

1

Try cache or transposition table. Without it, your search tree might explode.

1

To make boost iterative deepening with alpha-beta pruning you can use the SSS* Search algorithm, its a best first strategy algorithm. The SSS* Algorithm can improve the time efficiency of the overall algorithm but it increases the space complexity. I am linking the wiki to it https://en.wikipedia.org/wiki/SSS* I will update the answer as soon as i get a ...

1

The core of the question seems to really be: "how to approach thinking about this", where "this" is the input of an AI player. Modern attempts at game playing AI players try to replace a human player "as is". No advantage whatsoever. This implies that we want to feed the same "raw input" to the software player and to the human player. For a video game, the ...

1

To make an AI opponent, you'll need to create a sub-routine that considers the current state of the board and chooses a move, just like the player would. Now, how does this subroutine choose what move to make? You need to take the current board and calculate its value. Then consider every possible move you could make. Then consider, for each of those, ...

1

MCTS only need to "see" states in respect of reward. All game mechanics is abstarcted away from MCTS and MCTS only access actions and rewards. MCTS player don't access states itself, it's only choose action according to backpropagated reward. For partially observed MCTS player can't even access rewards of states, but instead access only expected reward over ...

1

All the methods in the GameState class that is used to represent state, are stubs, and without these, the MCTS algorithm won't do anything at all. In particular, the DoMove method just changes who's turn it is, without actually taking any action. Probably the reason the players can't see each other's cards is that this is not a completed implementation. ...

Only top voted, non community-wiki answers of a minimum length are eligible