🔒 my minimax algorithm is pretty slow

[unborn pewter]

i implemented alpha-beta pruning and it can run depth 5 blazingly fast. tenths of seconds. but the problem with this is that it doesnt see any decent end position at the end of its search, so it'll return a value of 0 for the end of the search. it's also wrong.

for example, in this given position: py board = [ [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [2, 0, 2, 1, 0, 0, 0] ]
you'd expect it to return that column 4 is the best. nope. it returns column 3 is the best for yellow to play, even though it clearly isn't because red is about to win on column 4.

(it returns these evaluations for the following columns by the way) ```py
-600 0
-600 1
-800 2
-600 3
-600 4
-600 5
-600 6

Time taken: 5.88s to 6.12s

i'm also not sure how to tackle the overarching issue of a static evaluation. i found one online from [here](https://github.com/mukeshmk/connect-4/blob/master/bots/evaluation.py) and i went through to translate it to my code but it only increased the processing time from around 6 seconds to around 11 seconds, which was the opposite of what i wanted to do, and it didnt even return a concrete analysis. ![sadge](https://cdn.discordapp.com/emojis/772299984099999806.webp?size=128 "sadge")

i also had help from @tidal brook with this project, which i greatly appreciate. but me and him had different interpretations of what the board should look like. i preferred a traditional 2D matrix of size 7 by 6, but in his version of the code he shared with me, which i am currently using, he proposed the (strange to me) idea of using a list of columns and then to place counters, just append to the list after checking it's less than 6 in length.

this works good and all, but i had to build translating functions to translate between his and i's methods, which i'd like to remove and convert fully to my format so i can say that i made it from top to bottom by myself, and of course give credit to @tidal brook for everything he's helped me with. an absolute legend. ![catcheer](https://cdn.discordapp.com/emojis/1088935962496745492.webp?size=128 "catcheer") 

do let me know what you think. any help would be appreciated as always.
my code can be found [here](https://paste.pythondiscord.com/OFCQ) and im amazingly grateful for anybody that helps me with this project. ![prettythumbsup](https://cdn.discordapp.com/emojis/806390638044119050.webp?size=128 "prettythumbsup") 

|| (this also is gonna be cross-posted to the dpy server, so if you see it there, dont be alarmed. it's simply because they have longer expiration times and it can reach more people.) ||

apologies for the long help post. something i'm passionate about working on. ![blobthumbsup](https://cdn.discordapp.com/emojis/430550023311458325.webp?size=128 "blobthumbsup")

[steel holly]

@unborn pewter

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[hollow river]

I have no clue what you are doing, but it looks interesting.

Is it something that helps you search matricies faster or something?

[pseudo sand]

Column 3 as in “the third column” or “index 3”

[unborn pewter]

the 3rd column

[unborn pewter]

idk

the columns in the evaluation scores are 0 indexed, but i speak human so ima use 1-indexing

[fiery flax]

This is a great question, but I can't really think through it right now... can you cross-post to #algos-and-data-structs ?

(maybe just link to this post)

[unborn pewter]

lmao good idea. better than copy pasting the whole thing 😭

[safe sedge]

no way i literally just made a connect4 to try ap pruning

[unborn pewter]

the goat is hereee 🗣️

[safe sedge]

im also leaving because it 3:40 am

[unborn pewter]

currently 11:10pm for me, but same type of feeling

[midnight flint]

Are you asking for help improving the quality or performance of the algorithm? Or both?

[unborn pewter]

my mum left me alone in the house and said to be in bed by the time shes back so im cosntantly looking over my shoulder at the driveway

[unborn pewter]

both, but performance is a good start

is there a faster way to check for wins?

[midnight flint]

I'm already seeing a lot of little microoptimizations like:

• Avoid calling .count() so many times. Just call it once and store the result
• Instead of making a bunch of copies of the board's "windows", just iterate over the indices and count the pieces
• several of these loops are duplicated and can be consolidated

very micro:

• store constants like board.WINDOW_LENGTH in local variables WINDOW_LENGTH = board.WINDOW_LENGTH or hard-code them 4 since your repository is already named connect-4
• don't call board.get_board() so many times, store the result in a local variable

and you're doing a lot of window evaluations, I'm pretty sure you could cache a lot of your work by using a sliding window technique

you'll probably be able to 10x your performance by switching to a compiled language or a different interpreter like pypi (you could just implement the Evaluator class in C++ and leave everything else in Python)

these kinds of "brute force giant for loops" are notoriously slow in cpython; a huge amount of time is wasted dealing with control flow

[midnight flint]

in fact you could use a sliding 4x4 kernel with numpy to quite efficiently sum up the important pieces in each 4x4 region

[unborn pewter]

ah ok i see now

[midnight flint]

Just btw this is a good resource for auto-validating your algorithm: https://tromp.github.io/c4/c4.html

[unborn pewter]

idk, its something i pulled off of github that runs with python. i changed the stuff like get_board() to just self.board and WINDOW_LENGTH as just 4

[unborn pewter]

what does that do?

[unborn pewter]

2 things:

1. how would i use pypi as an interpreter?
2. how would i implement C++ classes into python? theres this guy called pascal pons with a crazy algorithm i'd love to use

[midnight flint]

Connect 4 is a solved game, the starting player can force a win. That page includes some details about how.

[midnight flint]

Oh, so you didn't write this code?

[midnight flint]

oops I meant pypy, pypi is a different thing
https://www.pypy.org/

[midnight flint]

2. it's pretty simple, I've had great success with pybind11

[umbral flicker]

!pip pybind11

[steel holly]

pybind11 v2.12.0

Seamless operability between C++11 and Python

Released on <t:1711583465:D>.

[umbral flicker]

:O

@midnight flint thanks for that

[unborn pewter]

in what parts?

im not sure where exactly to look

[midnight flint]

I was gonna link my github which I thought had an example of using pybind to implement Chess in C++.... but apparently I didn't track that project with git?? shit

goodbye weeks of work

[umbral flicker]

life is ephemeral

joy is fleeting

suffering is eternal

[midnight flint]

here's the complete thesis https://github.com/tromp/tromp.github.io/blob/master/c4/connect4_thesis.pdf

I haven't read it so idk what it's like, but it does look like there is some accompanying code

[midnight flint]

damn it, I found the compiled .pyd file but not the source code

[unborn pewter]

91 pages

[unborn pewter]

await interaction.response.send_message(life, ephemeral = True)```

my dumbass thought ctx.send had ephemeral responses

[midnight flint]

that's actually so annoying I can't believe I deleted the .cpp for some reason

[unborn pewter]

the evaluation is abstracted to work with my code but yes, its not entirely my code

[unborn pewter]

oh

[unborn pewter]

yeah, i was almost certain pypi was for packages

hold on lemme go upstairs rq

[umbral flicker]

I did two weeks of work on Rijndael in C++ before I scrapped the entire thing and switched to Java. I sympathize.

[unborn pewter]

im back

[midnight flint]

im actually furious, the binary still works great

I literally just lost the source code

[umbral flicker]

F

[midnight flint]

ok sorry I'll stop complaining this isn't my thread 😭

[umbral flicker]

is it backed up somewhere

[midnight flint]

this is the backup

[umbral flicker]

Just reimplement it.

[umbral flicker]

.

[silver totem]

@unborn pewter Are your initial values for alpha and beta the wrong way around? ```py
score = cls.minimax(new_board, depth, float('inf'), float('-inf'), -player)

[unborn pewter]

wait what

i aint even notice 😭

they're defo the right way around

[silver totem]

If you're following the pseudocode on Wikipedia, it starts with alpha = -inf and beta = +inf: https://en.wikipedia.org/wiki/Alpha–beta_pruning#Pseudocode

[unborn pewter]

my computer nearly exploded

[unborn pewter]

takes 4.17s with the arrangement i have now and it makes my pc louder with the other way around

i think i know which one is correct

my pc is heating up

i quit the terminal

wait would it be ideal to delete everything and rewrite everything?

[silver totem]

But if alpha starts with the value +inf, then this line of code will not have any effect: ```py
alpha = max(alpha, value)

[unborn pewter]

it clearly works, idk how

oh wait i fixed it

its because the player was backwards

wait no im dumb

[silver totem]

Not necessarily. You've done some good work, although the code could be organised a little bit more optimally.

[unborn pewter]

yeah thats what i was thinking

i honestly just need a tablebase for the first possible 5 moves and im set

the algorithm doesnt kick in until then

i dont know why

oh wait i forgot the algorithm is also wrong

thats another thing that needs fixing

[silver totem]

One thing I'd do is put all of the game logic into its own class. You can implement minimax search in a way that is independent of the game being played. Take a look at the AIMA sample code for inspiration: https://github.com/aimacode/aima-python/blob/master/games.py

[unborn pewter]

im done for

gtg hold on

[steel holly]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.