search

PraxTube / chess-ai

A chess AI that uses alpha-beta to find the best move
MIT License
0 stars 1 forks source link

AI: Illegal moves when thinking in higher depths #23

Closed PraxTube closed 1 year ago

PraxTube commented 1 year ago

It seems like the AI generates illegal moves when it's thinking in higher depths. For example:

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1
Depth: 5
Moves:
g3 e6 Ng5 hxg5 a3

The third move is already illegal. It's not only illegal, it's just straigt up nonsense. This happens as early as depth = 4, possibly even earlier.

My supsicion is that the search algorithm is somehow breaking either the board of the GameState, or the engine is not working correctly.

Although the evaluation function #16 could potentially cover this up, this must be resolved.

Potential things to try:

PraxTube commented 1 year ago

There are many more examples, it's actually harder to find examples were there aren't any illegal moves

N-11:53 $ python benchmarks/benchmark_depths.py 

=========
Benchmark best move for depth 1, number of iterations 500
=========

Total: 0.61s, Average: 1.22ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1

=========
Benchmark best move for depth 1, number of iterations 500
=========

Total: 0.583s, Average: 1.17ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('Nh3', (20, [])), ('Nb4', (19, []))]

=========
Benchmark best move for depth 2, number of iterations 50
=========

Total: 1.0809s, Average: 21.62ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1

=========
Benchmark best move for depth 2, number of iterations 50
=========

Total: 1.2477s, Average: 24.95ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('Nh3', (420, ['Na6'])), ('Nb4', (493, ['Nxf7']))]

=========
Benchmark best move for depth 3, number of iterations 20
=========

Total: 5.6694s, Average: 283.47ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1

=========
Benchmark best move for depth 3, number of iterations 20
=========

Total: 6.7752s, Average: 338.76ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('Nh3', (1303, ['Na6', 'Ng5'])), ('Nb4', (1769, ['Nf3', 'Nxa2']))]

=========
Benchmark best move for depth 4, number of iterations 5
=========

Total: 5.3437s, Average: 1068.75ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1

=========
Benchmark best move for depth 4, number of iterations 5
=========

Total: 10.7925s, Average: 2158.5ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('Nh3', (12142, ['Na6', 'Ng5', 'hxg5'])), ('h6', (17890, ['a3', 'Nxa2', 'Rxa2']))]

=========
Benchmark best move for depth 5, number of iterations 1
=========

Total: 18.9705s, Average: 18970.51ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1

=========
Benchmark best move for depth 5, number of iterations 1
=========

Total: 18.9843s, Average: 18984.3ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('g3', (114863, ['e6', 'Ng5', 'hxg5', 'a3'])), ('h6', (94144, ['a3', 'Nxa2', 'Rxa2', 'Rb8']))]
PraxTube commented 1 year ago

Going to test to see if this is a problem with the engine or the AI. Using python-chess to determine if the AI is still pulling wrong moves or not.

PraxTube commented 1 year ago

Implementing the same AI (alpha-beta) with python-chess yields the following benchmark results

=========
Benchmark best move for depth 1, number of iterations 100
=========

Total: 0.9356s, Average: 9.36ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

=========
Benchmark best move for depth 1, number of iterations 100
=========

Total: 0.9233s, Average: 9.23ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('a2a4', (20, [])), ('b7b5', (19, []))]

=========
Benchmark best move for depth 2, number of iterations 10
=========

Total: 0.8222s, Average: 82.22ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

=========
Benchmark best move for depth 2, number of iterations 10
=========

Total: 0.8946s, Average: 89.46ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('a2a4', (420, ['g8h6'])), ('b7b5', (493, ['g5h7']))]

=========
Benchmark best move for depth 3, number of iterations 3
=========

Total: 3.0353s, Average: 1011.76ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

=========
Benchmark best move for depth 3, number of iterations 3
=========

Total: 3.1386s, Average: 1046.21ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('a2a3', (5470, ['g8h6', 'g1h3'])), ('a6b4', (6157, ['g5e4', 'g8h6']))]

=========
Benchmark best move for depth 4, number of iterations 1
=========

Total: 1.7045s, Average: 1704.49ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

=========
Benchmark best move for depth 4, number of iterations 1
=========

Total: 2.1978s, Average: 2197.81ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('g1h3', (9302, ['g8h6', 'h3g5', 'g8h6'])), ('g8h6', (12945, ['h1g1', 'h8g8', 'g5h7']))]

=========
Benchmark best move for depth 5, number of iterations 1
=========

Total: 38.4333s, Average: 38433.35ms - 20 - rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

=========
Benchmark best move for depth 5, number of iterations 1
=========

Total: 50.3976s, Average: 50397.57ms - 19 - r1bqkbnr/pppppppp/n7/6N1/8/8/PPPPPPPP/RNBQKB1R b - - 0 1
[('g1h3', (207804, ['h7h6', 'h3g5', 'g8h6', 'a4b5'])), ('g8h6', (283677, ['g5e4', 'h6g4', 'a4b5', 'a6b4']))]

Again, there are illegal moves. This shows that there are problems with the AI (i.e. with the move.py script) and not the engine.

PraxTube commented 1 year ago

This might actually correlate with #17.